データストリーム環境におけるオンライン学習アルゴリズムの研究

数据流环境下在线学习算法研究

• 批准号: 11J03668
• 负责人: 松島 慎
• 金额: $ 0.83万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2012
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-11J03668/
• 关键词: 大規模データ; 機械学習; 最適化法; アルゴリズム; サポートベクターマシン(SVM); 双対座標勾配法; 高速化

実用的な機械学習をRAM容量を超える数10GB単位のデータに対して適用する場合はメモリスワップにより効率が著しく低下する問題があった。そこで我々は特にサポートベクターマシン(SVM)の機械学習において、現在汎用的に利用可能なマルチコアプロセッサおよびメモリ階層構造の特長を利用し、RAM容量を超えるデータを用いたSVM学習を高速に行うアルゴリズム、StreamSVMを提案した。提案アルゴリズムはDual Cached Loopsという提案スキームの上で動作する。Dual Cached Loopsは2つのスレッドが非同期的に動作する。Reading threadとよばれるスレッドはハードディスク(HDD)に連続アクセスし、繰り返しデータをHDDからRAMへ読み込む。一方のTraining ThreadとよばれるスレッドはRAMに転送されたデータにのみアクセスするため、HDDからの読み込みのオーバーヘッドを被ることなく、かつ途中で停止することなくデータアクセスが可能である。RAMへのアクセスはHDDからの読み込みに比べ高速であるため、Readingthreadが一度データを読み込む間に何回もデータにアクセスすることが可能であり、高速なパラメータ更新が可能となる。評価実験により、提案手法は既存手法に比べて非常に高速に学習が可能であることを確認した。さらに、この提案スキームを用いて他の機械学習の問題であるロジスティック回帰やサポートベクター回帰に対するアルゴリズムを開発した。また、複数のモデルを同時に学習する手法も開発することができた。これによってストリームデータをHDDに記憶させながら、それらを無駄にすることなく、またオンライン学習アルゴリズムの効率の良さを保ちながらバッチ学習を行うことができる。このアルゴリズムおよび方法論によって、当初の目的であったデータストリーム環境における制限を克服しながら今までの方法と匹敵する高い精度を達成することが可能になったと言える。

当实用的机器学习将超过RAM容量的数十GB单位的数据应用于数据时，记忆掉期会导致一个大大降低效率的问题。因此，我们提出了使用超过RAM容量的数据的算法，尤其是在支持向量机器（SVMS）的机器学习中，它利用当前通用的多核处理器和内存层次结构的功能，使用超过RAM容量的数据来快速训练SVM。所提出的算法对所提出的方案进行了工作，称为双缓存循环。双缓存循环具有两个不同步的线程。一个称为读取线程的线程连续访问硬盘（HDD），并从HDD重复读取数据中的数据。另一方面，一个称为训练线程的线程仅访问传输到RAM的数据，因此可以访问数据而无需从HDD读取的开销，而无需停止中间。访问RAM比从HDD阅读的速度快，因此可以在阅读线读取数据时多次访问数据，从而可以进行高速参数更新。我们证实，通过评估实验，与现有方法相比，可以很快学习提出的方法。此外，使用此建议的方案，我们开发了用于物流和支持向量回归的算法，其他机器学习问题。我们还开发了一种同时学习多个模型的方法。这允许在HDD上存储流数据而不会浪费它，并保持在线学习算法的效率时，可以在HDD上存储流数据时进行批处理学习。这种算法和方法使我们能够克服最初意图的数据流环境中的局限性，并实现与以前的方法相当的高精度。

项目成果

Linear support vector machines via dual cached loops

• DOI: 10.1145/2339530.2339559
• 发表时间: 2012-08
• 作者: Shin Matsushima;S. Vishwanathan;Alex Smola