Algorithmic Aspects of Machine Learning
本书通过探索理论计算机科学与机器学习之间可以互相借鉴的内容，将两者联系起来。着重于对那些灵活、易处理的模型的需求，这些模型更好地捕捉到了那些使机器学习变得容易而不是困难的因素。理论计算机科学家会见识到机器学习中的各种重要模型以及这个领域中的主要问题。而机器学习研究者会无障碍地见识到到前沿研究，并熟悉一种现代的算法工具包，其中包括矩量法（method of moments）、张量分解（tensor decompositions）以及凸规划的松弛（convex programming relaxations）。
书中的处理超越了最糟糕情况分析（worst-case analysis），构建了对实际在用方法的一种严谨的理解，有助于发现解决那些长期存在问题的激动人心的新方法。
引言
机器学习开始在我们生活的许多方面接管了决策，包括：
（a）在我们日常通勤乘坐自动驾驶汽车途中确保我们的安全；
（b）基于我们的症状及病史做出准确的诊断；
（c）定价、交易复杂证券；
（d）发现新的科学，例如各种疾病的基因基础。
但一个令人吃惊的事实是，这些算法在运行时对其表现会如何没有任何可证明的保证。当面对一个优化问题时，它们真的能够找到最优解吗？或者即使是一个相当好的解也可以。当它们假设一个概率模型时，能够从真实的后验分布中纳入新的证据和样本吗？机器学习在实践中效果非常好，但这并不意味着我们理解了为什么它效果这么好。
如果你上过传统的算法课程，你接触到的考虑算法的通用方法是最糟糕情况分析。比如一个排序算法，你会在最糟糕的可能输入下，基于它所需要的操作（operations）次数来度量它的执行时间。这是一种方便的界定形式，因为这意味着你能说出关于你的算法耗时的有意义的东西，而不需要担心你通常给它的输入类型。
但使得机器学习算法，尤其是最新的那些算法的分析变得如此具有挑战性的原因在于，在最糟糕情况的输入下，它们试图解决的问题的类型真的是 NP 难的。当你将寻找在数据上拟合得最好的参数的问题视为一个优化问题时，会有一些实例在寻找好的拟合时是 NP 难的。当你假设一个概率模型并想用其执行推断时，在一些实例上也是 NP 难的。
在本书中，我们会通过试图为我们的数据找到更真实的模型，来解决为机器学习提供可证明保证的问题。在很多应用中，我们会根据问题出现的背景做一些合理的假设。这些假设可以让我们避开那些最糟糕情况的阻碍，允许我们严谨地分析实践中使用的启发式方法 heuristic，同时设计从根本上解决机器学习中一些核心的反复出现的问题的新方法。
退一步说，就如理论计算机科学本身一样，超越最糟糕情况分析的想法是陈旧的。实际上，理解在“典型”实例上算法的表现如何有很多不同的意味：
（a）你的输入的概率模型，甚至是混合模型（其中组合了最糟糕情况的部分以及平均情况的分析，比如半随机模型 semi-random model，抑或平滑分析 smoothed analysis）；
（b）度量你的问题复杂度，以及寻求在简单输入上的快速算法的方法，如参数化的复杂度一样；
（c）稳定性的概念，即试图阐明你的问题中的哪些实例具有有意义的答案，并且是你真正想要解决的
这绝不是主题或参考文献的详尽列表。不管怎样，在本书中，我们将通过这些关于应付棘手问题的见解，来解决机器学习问题。
最后，我们希望理论计算机科学和机器学习之间还能有很多可以互相借鉴的东西。对理论计算机科学来说，理解在实践中启发式方法（如期望最大化 expectation- maximization，非凸函数上的梯度下降 gradient descent）效果为何如此好是一个巨大的挑战。但要在这些问题上取得进展，我们需要理解哪些类型的模型和假设在机器学习的背景下是有意义的。另一方面，如果我们在这些难题上有了进展，或是对启发式方法为何效果如此好有了新的见解，我们就有望把它们改造得更好。甚至有望发现解决一些机器学习重大问题的新方法，尤其是通过在我们的算法工具包中利用现代工具后。
本书覆盖以下主题：
（a）非负矩阵分解 Nonnegative matrix factorization
（b）主题模型 Topic modeling
（c）张量分解 Tensor decompositions
（d）稀疏复原 Sparse recovery
（e）稀疏编码 Sparse coding
（f）混合学习模型 Learning mixtures models
（g）矩阵补全 Matrix completion
随着领域的发展以及新的发现，我希望在之后的版本中能够添加更多章节。
