（一）有监督学习的模块
新年决定写一些关于如何写机器学习代码的科普文，总结一下多年写代码的经验。这一篇讲有监督机器学习的模块。
这是一篇总结讲的东西可以用来回答这样一个问题概括： “如何用最短的代码来实现L1/L2 regularized logistic/linear regression”。这里面包含了机器学习基础课上面常见的几种模型，线性回归(ridge regression)，lasso， logisticregression和sparse logisticregression。问题是如何用最简短的代码来实现这种模型。如果，在开始阅读前不妨想一想，如果你知道答案，或许不需要读这篇文章。
一般说我实现了某个机器学习的算法，大家会说我实现了一个线性回归，我有一个关于lasso的代码。我实现了一个GBDT用来做分类，或者是搞了一个LambdaMART。每一个机器学习的算法在这些名词里面是一个整体，但是实际上，每一个机器学习的算法都可以被拆分成几个相互独立的元素，而在实现上，它们就对应了不同的模块。
一般而言，一个有监督机器学习算法包含了下面几个元素： 模型(model) , 目标(objective), 正则化项(regularization)。常见的神经网络，GBDT，LR都是如此。
模型和预测：机器学习的模型一般指给定输入特征，如何给出输出的预测，在这里并没有涉及到学习算法的区别。比如线性回归，和linear SVM在计算输出的时候都是用y = w^T x +b 这样一个线性函数来进行预测，在这个意义上，linear SVM, logistic regression和linear regression都是属于线性模型。另外一个常见相同模型的例子是random forest和boostedtree，在模型上面，这两者没有差别，都可以看成是把各个tree的预测结果加起来的tree ensemble。对于模型而言，最常见的一个共同函数就是预测，给定x，如何预测得到y。而这样一个Predict函数就基本上成了所有模型必备的一个函数了。
目标函数和梯度：Linear SVM, logistic regression在目标上面没有差别，其实两者唯一的差别是在于目标函数不同。Linear SVM优化的是hingeloss，而logistic regression优化的是logistic loss。这两种差别在早期的机器学习论文里面就是两篇不同的文章，但是在实现上面的差别可能就在几行代码上了。不同的学习算法可能需要计算不同的统计量，但是其中最常见的统计量要属梯度。
一般来说一个目标函数可以写成是\sum_i l(y_i)，其中y_i是第i个样本的模型预测，l是目标函数，可以是hinge loss或者是logistic loss。如果要对于这样一个做梯度下降或者随机梯度下降，我们唯一需要知道的东西就是l’(y_i)，对于具体weight的梯度都可以通过这个量来用chain rule推导出来。对于更加复杂的目标如排序，或者神经网络，都是如此。因此目标函数和梯度计算往往也应该是机器学习程序中一个相对独立的模块。对于其它一些算法，如gradient boosting或者proximal gradient，我们还需要知道二阶梯度。
正则化项和统计量：正则化项也是另外一个常见可以被拆分的模块。这一般也取决于算法，比如如果是coordinate descent, 常见的接口是一个thre-sholding函数，获得梯度的和以及二阶梯度的和，返回更新的结果。而这样一个给定输入统计量来计算更新权值的函数也自然变成了一个常见的模块。
代码参考
XGBoost是去年我们实现的一个快速gradient boosting的库。支持了排序，分类，回归，线性模型以及树模型，L1/L2 regularization其中各个部分都有对应：
目标函数:https://github.com/tqchen/xgboost/blob/master/src/learner/objective.h
模型和预测以及更新：https://github.com/tqchen/xgboost/blob/master/src/gbm/gbm.h
正则化项：https://github.com/tqchen/xgboost/blob/master/src/gbm/gblinear-inl.hpp#L197
以上总结了机器学习程序里面常见的几个模块，当然这不代表这是机器学习程序的全部可能拆分额。根据不同的学习算法还有可能抽象出其它一些常用的模块出来。不过总结起来，这些模块之所以可以被拆分，是因为它们提供或者依赖了一些重要的统计量，比如梯度，梯度和以及二阶梯度。当一部分机器学习逻辑仅仅依赖于少数常见的统计量的时候，一般意味着这可以是一个独立的模块，这些统计量也常常对应于统计里面充分统计量的概念。
合理地理解机器学习算法的各个部分有利于我们写出可以复用的代码，使得一份代码做多样事情成为可能。
习题 最后留下一个问题：如何利用实现一个可以让每个样本带权值的线性回归算法？也就是说每一个样本有不同的重要程度，我们需要在优化的时候考虑样本权值。带权值这个要素应该放在哪一个模块中呢？如果你可以回答这个问题，应该就表明你基本明白这篇文章说的东西了。
（二）迭代器，流水处理
很多机器学习程序涉及从外存的数据读取以及预处理。常见的例子比如深度的神经网络，或者是基于外存计算的一些算法如VW还有我很早之前写过的SVDFeature。在这类问题中，一个常见的优化是采用一个单独的线程来进行数据的预读或者预处理，而用另外一个线程进行计算。
现在有这样一个问题：假设我们可以从硬盘文本格式，jpg以及各种格式来进行读入，而读入的实现多种多样，并且包含一些可能的预处理。但是我们自己又不想每次写各种多线程代码，怎么样才可以抽象出一个通用的模块解决这一个问题。
这里提供了一个解决方案，迭代器。迭代器(iterator)是设计模式中最常见的模式之一，它特别适用于在线更新的机器学习算法。一般常见的迭代器的接口如下
DataIterator {
void Reset();
bool Next();
DataBatch GetBatch();
};
我们通过Next移动迭代器，GetBatch拿到当前的数据块，Reset恢复迭代器到数据起始位置。一般一个常见的在线更新算法可以拿到一个迭代器，并且做如下操作
while (iter.Next()) {
Update(iter.GetBatch());
}
对于不同的数据，我们只需要实现各个格式的迭代器即可。这样对于机器学习的部分不需要关心数据的读入逻辑，就可以进行统一的计算。迭代器的抽象一大优势是可嵌套，一个迭代器的实现可以以另外一个迭代器作为输入。比如我们在读入图片的时候要对图片进行随机旋转，那我们可以设计一个随机旋转迭代器，每一次Next的时候从输入迭代器拿到一个图片，进行随机旋转，返回给使用者。大概的代码如下：
RandomProcIter : publicDataIterator {
DataIterator base;
DataBatch out;
bool Next() {
if (!base.Next()) return false;
out = rotate(iter.GetBatch());
}
DataBatch GetData() {
return out;
}
}
这样的好处是我们可以把预处理代码和读入代码分开，对于不同格式的数据读入我们都可以嵌一个处理迭代器来进行处理。但是现在的问题是，如何支持采用一个独立的线程来做预读。答案很简单，设计一个线程缓冲迭代器(thread buffer iterator)。
想法如下，设计一个迭代器以其它任意迭代器作为输入，在这个迭代器内部开启一个独立的线程，来主动地把输入迭代器的数据读入到内部的一个缓冲里面去。在caller调用Next和GetData的时候，只要直接返回缓冲里面已有的结果就好了。
这样设计的好处是所有的读入接口只是迭代器，并没有多线程的痕迹，而我们也只需要实现一次线程缓冲迭代器的代码。整个读入像是一个迭代器的chain，我们可以任意地引入线程缓冲迭代器让一个单独的线程来做前面这部分数据的预读，比如一个可能的迭代器链可以是：
JPegIterator->ThreadBuffer->ResizeRotationCrop->ThreadBuffer
这样的话有一个独立的线程去预读取jpeg图片，采用另外一个线程来进行图片的旋转等预处理。比起专门写多线程代码来的更加灵活地多。这类处理方式一般称为流水线（pipeline）
值得一提的是这类思想来源于数据库领域，在一般数据库的query execution就是用迭代器的嵌套组合来实现的。
（三）模板，张量库
机器学习代码的很大一个特点是依赖于矩阵和向量操作，这在神经网络和矩阵分解类模型里面尤其明显。从神经网络里面的backprop到矩阵分解模型里面的更新法则都可以以向量和矩阵甚至张量的形式出现。
写机器学习程序有两类心态，一种是最大化代码运行效率的程序员，另外一种是最求实现简单少写代码的程序员。比较常见的是前者写C++,CUDA， 后者写matlab, python。我个人属于前者，希望可以对代码有最大的控制，提前分配好内存，运行中不进行内存的动态分配，如果用GPU的时候让所有的数据都呆在显卡上面不要出来等等。
当然，提到优化，最需要注意的是阿姆达法则（Amdahl’slaw），即如果你优化了占运行效率的1%的部分，再怎么优化也无济于事。很多时候数据边界检查和必要的assert尽量加上其实很多时候不会影响效率。
现在的问题是，对于极度最求效率的C++程序员，是否可以写出最求简洁明快的matlab python程序员一样的代码呢。答案是肯定的，常见的c++库Eigen和支持CUDA的mshadow就一定程度上提供了这样的功能。使用张量矩阵库的好处是可以写出简洁的代码，但是这样一来，和写pythonmatlab又有什么样的区别呢？
区别是存在的，利用c++ 的模板技术，写矩阵向量代码可以和手写C++的函数来的一样高效。这一类模板编程技术称作expressiontemplate。
具体的原因可以考虑如下问题，假设A,B,C是三个向量。 应该如何实现A = B + C这样一个操作。对于一般的矩阵库，常见的实现是重载+这个操作，分配一个新的临时空间用以储存结果，然后把B+ C的结果存到那个临时的储存空间里面去。同样的情况可以对应于其它各类操作如矩阵乘法。如果是在乎效率的C++程序员不会希望有这样的临时空间的分配，因此会直接写类似以下代码来解决问题:
for(int i = 0; i < A.len; ++i) {
A[ i ] = B[ i ]+ C[ i ];
}
问题是我们需要写很多这样的函数来对付各种的情况。而且代码也不再像A=B+C这样简洁了。利用expressiontemplate的技术，可以解决这一问题。方案如下，我们还是重载operator+这个操作，但是这个操作不进行计算，而是返回一个抽象语法表达式BinaryAddExp。然后再重载等号这个操作operator=，在等号操作的似乎我们已经拿到了目标A以及B, C。可以把实现直接写成上面的样子。这样我们可以高效地写A=B+C， 并且还是对我们的内存分配有最大的控制。样例代码见https://github.com/tqchen/mshadow/blob/master/example/exp-template/exp_lazy.cpp
当然这样的方案只能解决A=B+C，还有其它的问题如A = B+C+D或者W =gradient * eta + W 这样的更新公式。这一类更长的表达式需要抽象语法表达式的嵌套，也可以通过模板来实现。具体教程见https://github.com/tqchen/mshadow/wiki/Expression-Template。
总结下来，最重要的一点是因为这些模板展开都是在编译时执行的，使得这些复杂的组合实际上没有消耗运行时的效率。机器学习代码也可以既简洁有高效，这样的特性也只有C++模板才可以做到。对于其他语言，相对的反而不是那么自然了。
当然底层的模板库也有一些自身的缺陷，比如不可以做远距离的依赖分析，以及并行优化等。更加高层的张量库如Minerva就可以完成这些事情。但是作为一个在极度追求效率和对于资源控制的C++机器学习程序里面，基于模板的矩阵库依然是一个必不可少的组成部分。即使是最最求效率可以写公式而不是直接调用blas函数。并使得C++的机器学习代码也可以优雅高效。这相比于java也是一个重要的优势。
文章出处：@陈天奇怪