重点关注3个相关领域的背景知识：信息检索（Information Retrieval，IR）、最优化（optimization）和机器学习（Machine Learning，ML）

一、信息检索

    计算广告采用的是类搜索的技术框架，即检索加排序两段的决策过程。

1、倒排索引

    其核心目的是将从大量文档中查找包含某些词的文档集合这一任务，用O(1)或O(logn)的时间复杂度完成，其中n为索引中的文档数目。也就是说，利用倒排索引技术，可以实现与文档集大小基本无关的检索复杂度，这一点对于海量内容的检索来说至关重要。

更详细的可查看搜索引擎系列知识中的—索引系统（搜索引擎核心技术—索引系统）

    倒排索引最基本的操作有两项：一是向索引中加入一个新文 档；二是给定一个由多个关键词组成的查询时，返回对应的文档集合。

2、向量空间模型

    如果说倒排索引技术是大规模信息检索的基石，那么向量空间模型（vector space model,VSM）则是信息检索中最基础且最重要的文档相似度度量方法之一。VSM的核心有两点，文档的表示方法和相似度计算方法。

更详细的可查看搜索引擎系列知识中的—检索模型（搜索引擎核心技术—检索模型与搜索排序）

    在离线索引阶段，需要对文档集合分词，并按照BoW模型表示得到每个文档的TF-IDF矢量，对分词后的文档集合建立倒排索引。当在线的查询到来时，也进行分词，从倒排索引中查出所有符合要求的文档候选，并对其中的每个候选评价其与查询的余弦距离，按距离由小到大进行排序。这样的一个基本框架，同样适用于广告这一大规模数据挖掘问题

二、最优化方法

    最优化讨论的是在给定一个数学上明确表达的优化目标后，如何用系统性的方法和思路找到该目标的最优解。最优化问题讨论的是，给定某个确定的目标函数（objectivefunction），以及该函数自变量的一些    约束条件，求解该函数的最大或最小值的问题。

    根据约束条件以及目标函数的性质不同，最优化问题求解的思路也有很大的不同。其中无约束优化问题的方法是基础，而带约束优化问题则在一定条件下可以转化为无约束优化问题来求解，这涉及下面将要谈到的拉格朗日法和凸优化问题。

1、拉格朗日法与凸优化

    在实际工程中，带约束优化非常常见，如后面将提到的广告合约量约束下的优化问题。带约束优化最重要的方法就是拉格朗日法。通过拉格朗日方法，我们可以将一个带约束优化问题转化为不带约束的基本优化问题来解决。

2、下降单纯形法

    在有些问题中，f不可导或者工程上求导代价极大这种情形下，假设函数值是连续的，我们有一种自然的思路，那就是采用不断试探的方法：在自变量为一维的情况下，给定一个初始区间，假设区间内有唯一的最小值，可以按照黄金分割的方法不断缩小区间以得到最小值。

    上面的方法也可以推广到自变量是高维的情形，对应的算法称为下降单纯形法（downhill simplex method）。这一方法有一个更直观的称呼，即阿米巴（Ameoba）变形虫法。简单地讲，将一维空间上用两个点限制的区间不断变形的思路加以推广，在D维空间中，可以选择一个D+1个点张成的超多面体，或称为单纯形（simplex），然后对这一单纯形不断变形以收敛到函数值的最小点。

3、梯度下降法

    当f可以比较容易地求导时，基于梯度的方法是首要选择。梯度的几何意义是f在x点函数值上升最快的方向，因此它是一个与x维数相等的矢量。而利用梯度的优化方法，概念上就是每次都沿着梯度的相反方向按某步长前进一小步，这样的方法称为梯度下降法（gradient descent）

4、拟牛顿法

    为了解决批处理梯度下降法收敛速度慢的问题，假设函数值呈近似的二次曲面状，那么很自然的思路就是引入二阶导数信息，以迅速探索到函数值的谷底。同时利用梯度和二阶导数做优化，相当于在当前点处进行二阶的泰勒展开，并找到此二次曲面的极小值点，这样的方法称为牛顿法。拟牛顿的一种常见方法是由Broyden、Fletcher、Goldfarb、Shanno这4位学者创造的方法，称为BFGS方法

三、统计机器学习

    机器学习是近年来得到快速发展和广泛应用的研究领域，它研究的是用数据或先验知识优化计算机算法的效果。从机器学习的方法可以分为统计方法和非统计方法。非统计的方法种类很多，并且往往最后都归结于一个具体的优化问题，可以通过深入掌握优化理论和算法，比较有效地把握各种非统计类方法。而统计类机器学习方法，虽然也用到最优化方法，但是还有一些在概率框架下系统性的思路。

1、最大熵与指数族分布

    统计机器学习中，指数族形式的分布由于求解的方便性，有非常重要的工程地位。

    指数族分布虽然数学上使用方便，但其实际的描述能力是有限的，并不适合于表达多种因素并存的随机变量。

2、混合模型和EM算法

    由于指数族分布是单模态的，因而不适用于分布比较复杂的数据建模。为了解决这个问题，同时又能充分利用到指数族分布的一些方便的性质，工程领域产生了采用多个指数族分布叠加的部分来建模的实用方法，即混合模型（mixture model）。

    指数族混合分布的EM算法只是EM算法的一种较简单的特殊情况，这一算法广泛应用于各种隐变量存在的统计模型训练中

3、贝叶斯学习

    最大似然准则，是把模型的参数看成固定的，然后找到使得训练数据上似然值最大的参数，这是一种参数点估计（pointestimation）的方法。这样的点估计方法，在实际中如果遇到数据样本不足的情形，往往会产生比较大的估计偏差。对此，工程上常常用到贝叶斯学习（Bayesian learning）的方法论。

    在贝叶斯体系下，模型参数θ不再被认为是固定不变的量，而是服从一定分布的随机变量。

四、统计模型分布式优化框架

    对于大规模数据上的许多机器学习计算问题，MapReduce是一个可行的选择：因为在机器之间交换的数据只是统计量或者充分统计量，其空间复杂度只与模型的参数数目有关，与数据的多少并无直接关系。

    当算法需要多次迭代才能完成的时候，由于需要在每次map过程中重新加载数据，使得整个过程的I/O负担变得较重，从而降低整个计算过程的效率。在Hadoop新一代的调度器YARN的基础上，Spark可以直接架设在Hadoop底层的分布式存储HDFS上，这使得数据可以直接在Spark的计算过程中复用，并没有在不同集群之间大量传递数据的开销。

五、深度学习

    所谓神经网络，指的是将简单的感知神经元连接在一起，从而模拟各种函数的灵活框架。以比较典型的全连接多层感知机（Multi-Layer Perceptron，MLP）

    这是深度神经网络较为一般的一种结构形式，很多情况下直接套用这种形式并不能高效地对问题进行建模。因此，根据具体问题的数据特点，产生了卷积神经网络（CNN）、递归神经网络（RNN）等丰富的结构形式。

    深度学习与大数据有着天然的密切联系：由于计算技术和计算能力的快速发展，我们目前已经能够处理越来越复杂的网络结构。但要让复杂的网络结构发挥优势，一定要有大量的数据才行。因此，深度学习最有可能在那些数据丰富的领域发挥巨大的作用。

1、深度神经网络优化方法

    深度神经网络的另一个优势是各种结构的模型优化方法相对一致。目前，反向传播算法（back propagation）是最常用且最有效的算法，其基本原理如下。

（1）将训练数据输入到深度神经网络的输入层，经过隐藏层，最后达到输出层并输出结果，这是前向传播过程。

（2）由于输出值与标注值之间存在误差，计算该误差，并将其从输出层向隐藏层反向传播，直至传播到输入层。

（3）在反向传播的过程中，根据误差调整各个参数的值，并不断迭代上述过程，直至训练过程收敛。

    神经网络的优化方法与其模型结构并没有太大的关系，这使得开发一个较为通用的神经网络表达和优化工具成为可能。目前，开源的神经网络工具软件主要有TensorFlow[1]、Caffe[56]、Mxnet等。

2、卷积神经网络（CNN）

    卷积神经网络（Convolutional Neural Network，CNN）是一种常见的深度神经网络结构，主要用于图像处理领域。在人脸识别等图像处理任务中，是将原始图像张量作为输入，经过多层的非线性变换，一层层得到更高级的语音信息，最终完成识别其中物体的任务。显然，图像处理有两个重要的领域特点。

（1）局部感知。在图像上提取边缘、发现物体等操作，往往只需要聚焦在图上的一个局部范围中。

（2）参数共享。视觉元素的特征与位置无关，因此，在同一层中的不同神经元，可以共享一样的输入变量的权重。如果输入变量整理成张量的形式，这一组在局部范围图像上的变换权重称为一个卷积核。将一幅图像利用卷积核做变换的过程，如图所示。卷积神经网络训练的目的就是得到各卷积核上的各个权重。

    卷积神经网络交替采用采样和卷积对原图像进行变换，从而获得越来越抽象的图像理解能力。

3、递归神经网络（RNN）

    另一种常见的深度学习模型是递归神经网络（RecursiveNeural Network，RNN），它主要用于处理时间序列数据的建模，典型的例子是语音识别和机器翻译。RNN要解决的问题是p({y1,…,yt}}|{x1,…,xt}})这种建模问题。

4、生成对抗网络（GAN）

    Szegedy在研究神经网络的性质时发现，针对一个已经训练好的分类模型，将训练集中的样本做一些细微的改变会导致模型给出一个错误的分类结果。这种虽然发生扰动但人眼可能识别不出来且会导致误分类的样本称为对抗样本，他们利用这样的样本发明了对抗训练（adversarial training），模型既训练正常的样本也训练这种自己造的对抗样本，从而改进模型的泛化能力。

    GAN受博弈论中的二人零和博弈的启发，它采用一种非常巧妙的思想给出了用深度神经网络实现生成模型的一般思路

    虽然从概念上说，GAN是一种有前景的用深度学习解决生成问题乃至无监督训练问题的方案，不过其优化过程还有很多问题没有解决，包括模型训练的收敛性和细节的把握方面都存在很多的问题。