私のブックマーク
オンライン学習（Online Learning）
大岩秀和（（株）リクルートホールディングス）
はじめに
オンライン学習は，機械学習における学習の枠組みの一つである．オンライン学習の枠組みでは，全データを一度に用いること無く，データが一つ（あるいは全データの一部）与えられるたびに，与えられたデータ のみを用いて逐次的にモデルを改良する． そのデータのみを用いて逐次的にモデルを改良する．このデータ処理方式の性質から，メモリやキャッシュに全データが乗らない規模のデータ解析や永続的にデータが生成される環境下での学習が効率化できる．インフラ基盤やセンサー／ネットワーク技術の進歩によるデータの大規模化や機械学習技術を用いた継続的なサービス運用が一般的となるにつれて，オンライン学習分野の研究開発も促進された．
機械学習分野の論文ではこれらの枠組みを単にオンライン学習 (Online Learning) と表現する事が多い．しかし，オンライン学習という用語は一般的に，大学講義などの教育系コンテンツをウェブ上で受講できる仕組みを指す．機械学習用語としてのオンライン学習と教育用語としてのオンライン学習を区別するため，機械学習用語の側をオンライン機械学習 (Online Machine Learning) と呼ぶこともある．
本稿では，オンライン学習の導入から発展的話題を得るための情報源とオンライン学習に関連するソフトウェアを以下に紹介する．今回本稿を執筆するにつき，オンライン学習に関する幾多の情報源を網羅的に紹介するのではなく，個人的に重要と思う論文や資料を選択して紹介する形式とした．オンライン学習は機械学習の枠組みの一つであり，あくまで手段の一つである．また，固有のタスクや目的に特化した枠組みではない．そのため，タスクによって効果的な適用方法が異なり，またオンライン学習以外の代替的な枠組みを適用すべき問題設定も多く存在する．これらの理由から，個々のアルゴリズムや応用事例を幅広く紹介するよりも，基本的な概念や長所／限界を理解するための情報源をまとめたほうが読者にとって有益となると考えたためである．
オンライン学習のサーベイ／チュートリアル
本節では，オンライン学習分野の概要を学ぶための書籍やサーベイ論文／チュートリアル資料を紹介する．また，オンライン学習はバンディット問題や確率的最適化・ゲーム理論などの研究分野とも関係が深いため，これら隣接分野との関係性を説明した情報源も紹介する．
- Online Learning Methods for Big Data Analytics [1]
- Steven C.H. HoiとPeilin Zhaoによるオンライン学習を用いたビッグデータ解析に関するチュートリアル資料．このチュートリアルでは，大規模データ分析でのオンライン学習の有効性と,オンライン学習の代表的なアルゴリズム・応用例が 紹介されている． 応用例が紹介されている．スライド内で紹介されているように，著者らのチームは分類学習 [2]，AUC最大化 [3]，転移学習 [4] など，様々なタスクに対するオンライン学習手法を提案している．
- Online Learning and Online Convex Optimization [5]
- Shai Shalev-Shwartzによるオンライン学習とオンライン凸最適化のサーベイ論文．オンライン凸最適化とは，凸関数の最適化をオンライン学習の枠組みで解析する分野である．分類問題や回帰問題などのさまざまな問題設定のもと，オンライン学習アルゴリズムの解析がされている．この論文では，代表的なアルゴリズムの導出方法とその理論解析が順序立てて説明されており，さらに確率的最適化との関係やバンディット問題への拡張も紹介されている．
- Introduction to Online Convex Optimization [6]
- Elad Hazanによるオンライン凸最適化のサーベイ原稿（原稿執筆時点ではドラフト版）．前出のサーベイ論文よりもカバー範囲が広く，second-order methods/projection-free methodsなど，より様々な問題設定でのアルゴリズムや理論解析の解説がなされている．この原稿をベースにした講義資料スライドも公開されている．
- Prediction, Learning, and Games [7]
- データの生成メカニズムに確率的な仮定を置かない問題設定での，系列のオンライン予測に関する研究をまとめた書籍．オンライン学習でしばしば理論解析に用いられるリグレット解析は，データの生成分布に仮定を原則置かない解析方法である．これらの理論解析は本書の議論をベースにしているものが多い．本書の議論は繰り返しゲームやエキスパートシステムなどでも用いられる．
- Learning Methods for Online Prediction Problems
- Peter BartlettによるMLSS Canberra 2010でのオンライン予測問題に対する機械学習の講義資料．講義ビデオも公開されている．
- オンライン機械学習 (機械学習プロフェッショナルシリーズ) [8]
- オンライン学習の概要を日本語でまとめた書籍．日本語でのオンライン学習分野の貴重な解説書の一つである．分類問題に対するオンライン学習手法を中心に，実装の観点やオンライン分散学習の説明も紹介されている．
オンライン学習に関連する国際会議／論文誌
オンライン学習をはじめとする機械学習分野では，最新の研究報告は国際会議や論文誌でなされている．そのため，最新の技術動向や最先端の議論を把握するには，これらに採択されている論文を調査することが必須となる．機械学習やその周辺分野ではオープンアクセスのプロシーディングスや論文誌が多く，プレプリント版がarXivや著者のホームページで公開されている論文も多数あり，ウェブ上で当該の論文を読むことが可能な場合が多い．以下では，オンライン学習に関する論文が採択される主要な国際会議や論文誌を紹介する．
- Neural Information Processing System (NIPS)
- International Conference on Machine Learning (ICML)
- 機械学習に関する国際会議．オンライン学習のアルゴリズム提案や理論解析の論文が数多く採択されている．例として，オンライン凸最適化の代表的なアルゴリズムであるOnline Gradient Descentの理論解析を行った“Online Convex Programming and Generalized Infinitesimal Gradient Ascent” [9]，大規模データかつ計算リソースが十分で無いときにオンライン学習がバッチ学習よりも有効となることを示した“Large Scale Online Learning” [10] などがこれらの国際会議で採択されている．その他にも，機械学習や統計に関連した人工知能系の国際会議であるAISTATSやUAIでもオンライン学習に関連した理論解析とアルゴリズム提案の論文が採択されることがある．
- Conference On Learing Theory (COLT)
- 学習理論に関する国際会議．オンライン学習の理論解析に関する論文が数多く採択されており，解析結果から導出されるアルゴリズムの提案も行われている．例として，データ空間の幾何に適応的なアルゴリズムであるAdaGradを提案した“Adaptive Subgradient Methods for Online Learning and Stochastic Optimization” [11] などが採択されている．
- Journal of Machine Learing Research (JMLR)
- 機械学習分野に関連する研究の論文誌．ICML/NIPS/COLTなど，機械学習系国際会議で採択された論文のジャーナル版が採択されることも多い．例として，前出のAdaGrad提案論文のジャーナル版 [12] などが採択されている．また，JMLRにはOpen Source Software用のトラックもあり，オンライン学習を含む機械学習関連の様々なオープンソース・ソフトウェアの論文が採択されている．
- Knowledge Discovery and Data Mining (KDD)
- IEEE International Conference on Data Mining (ICDM)
- データマイニングに関する国際会議．オンライン学習を用いたデータマイニングやデータ分析の応用事例に関する論文が採択されている．継続的な大規模データ処理にオンライン学習が適用されている例として，広告のClick-Through-Rate予測 (“Ad click prediction: a view from the trenches” [13]) やニュースサイトに付随するユーザ投稿型掲示板のスパム判定 (“Unbiased Online Active Learning in Data Streams” [14]) などがこれらの国際会議に採択されている．
また，人工知能 (AAAI, IJCAI) や言語処理 (NAACL, EMNLP) などの応用領域の国際会議においても，オンライン学習の特性を活かしたアルゴリズムの提案や理論解析に関する論文が採択されることがある．さらに，ウェブやビッグデータ領域の国際会議 (WSDM, IEEE on BigData) でもデータを解析するためのオンライン学習基盤や分析方法の提案に関する論文が採択されている．論文レポジトリarXivでは，stat.MLやcs.LGのカテゴリで，オンライン学習に関連するプレプリント版の論文が投稿されることが多い．
オンライン学習アルゴリズムの実装
この節では，オンライン学習の実装について紹介する．オンライン学習アルゴリズムの実装の簡易性や実用性の高さから，様々なソフトウェアやライブラリが開発されている．以下ではこれらの代表的な実装について紹介するとともに，その他にも様々なライブラリやソフトウェアが開発されているため，これらの情報が集まっているレポジトリやフォーラムについても紹介する．
- Vowpal Wabbit
- メモリに載りきらない大規模データを効率的に解析する様々な技術を取り込んだオープンソース機械学習ライブラリ．分類学習や行列分解／LDAの学習やAllReduceベースの並列計算も可能．Yahoo! Researchの研究者が中心となって開発が行われていたが，中心研究開発メンバーの所属変更に伴い，現在はMicrosoft Researchがスポンサーとなっている．Vowpal Wabbitによる大規模データ解析システムの概要と，テラスケールデータの短時間での解析を実証した実験結果に関する論文 [15] も採択されている．
- LIBOL – A Library for Online Learning Algorithms
- オンライン学習でよく用いられる分類学習アルゴリズムをパッケージ化したオープンソースライブラリ．チュートリアルの節でも紹介したSteven C.H. Hoiを中心とするメンバーが開発している．ソフトウェアの概要や性能比較実験結果などを掲載した論文 [16] も採択されている．
- Jubatus
- 分散学習機構Mixに基づく分散オンライン機械学習ライブラリ．Preferred NetworksとNTTソフトウェアイノベーションセンターによって共同開発されている．分類／回帰学習／推薦／異常値検出やグラフ分析もサポートしている．本ライブラリの概要を記載した論文 [17] も掲載されている．
- Hivemall
- Hive上で動作するスケーラブルな機械学習ライブラリ．様々なオンライン学習アルゴリズムが実装されており，HiveQLで並列計算での学習や予測が行える．
また，オンライン学習関連のソフトウェアやライブラリが集まるレポジトリやフォーラムとして以下を挙げる．
- mloss.org
- 機械学習に関連するオープンソースライブラリのためのフォーラム．各ライブラリの概要や動作環境／更新情報などが一目で確認したり，検索したりできる．
- GitHub
- オンラインでGitレポジトリを管理するサービス．上に紹介したライブラリの多くは，GitHubを用いてライブラリ公開と開発を行っている他，個人から企業まで多様なコミュニティが開発したオンライン学習のライブラリが提供されている．
おわりに
本稿では，オンライン学習に関する情報源を紹介した．
オンライン学習は，大規模データ解析や機械学習技術を用いた継続的なサービスに有効的な枠組みであり，様々な応用事例やオープンソースソフトウェアが公開されている．
オンライン学習の特性や長所／限界を理解し，オンライン学習の研究開発や応用タスクへ適用する一助となる情報が提供できれば幸いである．