罗 霖

（中国人民解放军73232部队 舟山 316200）

1 引言

近年来，随着数据采集手段的飞速发展以及数据来源的日益丰富，尤其是互联网的大规模使用，我们所能获得的数据规模已经从十年前的数万、数十万到今天的动辄上千万、甚至是数亿，知识量成“爆炸式”增长，如文本分类数据库达到107样本个数，109样本维数。如何学习和处理这些大规模海量数据是当前值得关注而又亟需解决的问题。

目前，机器学习（Machine Learning）已经被公认是处理和学习这些数据最为有效的手段之一。将机器学习问题的求解归结为优化问题是当前机器学习界主流的做法。实际上，优化理论已经成为机器学习研究的核心内容之一，可以用经验风险最小化、最大似然、最大熵和最小描述长度等方法来表示，它是机器学习算法设计的根本依据。批处理（Batch）方法是优化理论早期的算法形式，如梯度下降法、（拟）牛顿法和内点法等，其每一步迭代都要遍历所有的样本信息甚至需要处理海森（Hesse）矩阵。如果处理规模较小的数据，可以直接用经典的批处理优化方法很容易对其求解，但是如果面临的是大规模海量数据，整个求解过程就发生了重大转变。以文本分类的数据库为例（规模为107个数，109维数），光存储数据本身所需要的内存空间为107×109×4Byte＝4×107GB，当前64位计算机的内存总量也就是264Byte＝16GB，即便全部拿来存储数据，其容量还是杯水车薪，更不要说去处理和分析数据。虽然这些年来计算机硬件也相应地有着快速发展，但仍跟不上数据集规模增大所带来的计算需求爆炸式增长的步伐。……