天気予報から機械学習、金融工学まで - DO++
もう随分経ちますが，先日CompView秋の学校というのに行き，2泊3日みっちり機会学習を勉強してきました．講師陣は豪華でどの話も面白かったのですが特にElad Hazanによる"Prediction in the dark: the multi-armed bandit problem"が非常に面白かったです． その話を説明するために，まず簡単ながら驚くべき性能を達成するアルゴリズムを紹介しましょう． 解きたい問題は，毎日，次の日の天気が晴れか雨かを予想する問題です．t日目が晴れの場合 y(t)=1, 雨の場合 y(t)=0と表すことにしましょう．t日目にy(t+1)を予想するわけです． さて、自分は天気の専門家ではないので，自分で予報せずに，専門家に頼ることにしてみます．M人の天気予報士がいて，それぞれが独自に次の日の天気を予想しています．i人目の天気予報士のt日目の予報をp(i,t)
DO++ : 線形識別器チュートリアル
ワークショップ中の夕食で話したのですが、今のところ日本で（素性関数ベース＆線形識別器）機械学習のいろいろな手法をまとめて体系的に教えてる資料などがあまりないなぁという話をしていました。 で、探すと、このあたりの大部分をまとめて説明しているいいチュートリアル（英語）がありました。 夏の学校資料[pdf] その他のコードやリンク ちょっとだけ解説 現在自然言語処理の多くで使われている学習器は線形識別器です。 入力x（例：単語、文、文書）から出力y（例：品詞、品詞列、文書のトピック）を予測したいという場合は、(x,y)のペアからいろいろな値を取り出し（x,yのペアから値を取り出す関数を素性関数と呼ぶ）、その値を並べたベクトルを素性ベクトルと呼び、f(x,y)とかきます。そして、その素性ベクトルf(x,y)と同じ次元数を持つ重みベクトルwとの内積を測って、その値が正か負か、または大きいか小さいかを
OLL: オンライン機械学習ライブラリをリリースしました。 - DO++
様々なオンライン学習手法をサポートしたライブラリ「OLL (Online-Learning Library)」をリリースしました。 プロジェクトページ 日本語詳細ページ 学習、推定を行なう単体プログラムと、C++ライブラリからなります。（C++ライブラリ解説はまだ）。 New BSDライセンス上で自由に使えます。使った場合は感想や苦情などいただけると幸いです。 オンライン学習とは、一つずつ訓練データを見てパラメータを更新していく手法で、訓練データをまとめて見てから学習するバッチ学習（SVMs, 最大エントロピー法）と比べて非常に効率良く学習を行なうことができます。それでいながらSVMs, やMEsに匹敵する精度が出ます。 学習するデータの性質にもよりますが、例えば、英語の文書分類タスクで、15000訓練例、130万種類の素性の訓練データに対する学習が1秒未満で終わります（SVMsだと実装に
行列分解ライブラリredsvdを公開しました - DO++
大規模疎行列向けの行列分解ライブラリredsvdを公開しました． redsvd 大規模疎行列向けの特異値分解や主成分分析，固有値分解を行うライブラリredsvdを公開しました． 修正BSDライセンスで公開しており，コマンドラインから使える他，C++ライブラリが用意されています． 例えば，行と列数がそれぞれ10万，非零の要素が1000万からなる疎行列に対する上位20位までの特異値分解を約2秒で処理します． 特異値分解とか，使っている技術の詳細とか応用事例を以下に簡単に紹介しましたので，興味のある方は参考にしてください． 特異値分解とは まず行列を適当に復習します．行列Xの転置をX^tと表すことにします．またIを単位行列とし，Oを全ての成分が0である零行列とします．また，行列XX^t=IであるようなXを直交行列と呼びます．Xが直交行列の時，Xvはベクトルvを長さを変えずに回転させます．ここでは
オンラインEMアルゴリズム - DO++
EMアルゴリズム（Expectation Maximizationアルゴリズム、期待値最大化法、以下EMと呼ぶ）は、データに観測できない隠れ変数（潜在変数）がある場合のパラメータ推定を行う時に有用な手法である。 EMは何それという人のために簡単な説明を下の方に書いたので読んでみてください。 EMのきちんとした説明なら持橋さんによる解説「自然言語処理のための変分ベイズ法」や「計算統計 I―確率計算の新しい手法 統計科学のフロンティア 11」が丁寧でわかりやすい。 EMは教師無学習では中心的な手法であり、何か観測できない変数を含めた確率モデルを作ってその確率モデルの尤度を最大化するという枠組みで、観測できなかった変数はなんだったのかを推定する場合に用いられる。 例えば自然言語処理に限っていえば文書や単語クラスタリングから、文法推定、形態素解析、機械翻訳における単語アライメントなどで使われる。
PFIセミナー資料: 研究開発2009 - DO++
昨日ありました、PFIでのセミナーでの発表資料です。 研究開発のチームの紹介の後に、2009年サーベイした論文の中で面白かった論文を 機械学習、データ構造、画像処理で紹介してます 紹介した話は - Multi-class CW (Multi-class Confidence Weighted Learning,) - AROW (Adaptive Regularization Of Weight Vector) - Online-EM algorithm - 全備簡潔木 (Fully-functional Succinct Tree) - 圧縮連想配列 (compressed function) - PatchMatch です。 ＃資料中の簡潔木の表現方法のDFUDSの紹介でtxも使用と書いてあるのは、公開しているtxでは、 LOUDSのみをつかっていますので正確ではありませんでした。これ
全文検索エンジン Miniseをリリース + WEB+DBで全文検索の特集記事 - DO++
全文検索エンジンの Minise: MIni Search Engineをリリースしました． このエンジンは全文検索の基本的な機能をサポートしたもので，索引手法は逐次検索（索引無），N-gram，転置ファイル，接尾辞配列をサポートしており，そこそこ最適化を行ってます．Wikipedia日本語版を実験で使ったもので20万文書で構築時間が500秒前後，検索時間が一クエリあたり数msとなっています． BSDライセンスで公開しています． 割りきって，機能を絞ってシンプルな構成にしていますので改造したりしやすいようになっています。まだ、ドキュメントはないですが、C++ APIとして利用しやすいようにもなっていますので、研究用途などで新しい索引やランキングとかでの利用も想定しています（実際に研究用で使ってます）． --- 今回の全文検索ライブラリを開発する機会になったのが，私が担当した今月号のWEB+
SPIRE2009 - DO++
フィンランドのサーリセルカという場所で開催されたSPIRE2009で発表してきました。 サーリセルカは北極圏で、百夜ではなかったですが夜暗くなったのは４時間ぐらいでした。天候が悪く残念ながらオーロラはみれませんでした。トナカイを見て、トナカイを食べてきました。 エクスカーションでイナリというところにいき、またワークショップの後に山にハイキングに行きました（ハイキングといっても６時間ぐらい歩く結構本格的なもの）。誰も声を出さないと耳がおかしくなるくらいの無音になるとにかく静かなところでした。冬に行くとクロスカントリーとかが楽しいらしい。 聞いたメモ - "Novel and Generalized Sort-based Transform for Lossless Data Compression", Kazumasa Inagaki, Yoshihiro Tomizawa, and Hid
Burrows-Wheeler変換の線形時間アルゴリズム - DO++
研究紹介です。今夏のSPIRE 2009という学会で "A Linear-Time Burrows-Wheeler Transform using Induced Sorting", D. Okanohara, K. Sadakane, SPIRE 2009 pdf(draft) というのを発表します。これは与えられた文字列に対し接尾辞配列を経ないでBurrows-Wheeler変換を直接行うというもので、アルファベットサイズによらず入力長に対して線形時間で行えます。基本的なアイディアは昨年のInduced Sortingによる接尾辞配列の線形時間構築アルゴリズム（いわゆるSAIS）を接尾辞配列を使わないでシミュレートするものです。pushとpop操作だけからなり、そのまま外部記憶上での構築とかにも対応できるようになっています。 Burrows-Wheeler変換（BWT, Block S
netflix prize is over, 時間経過による嗜好性の変化 - DO++
米国のオンラインDVDレンタルサービス「Netflix」が、現在利用しているレコメンデーションシステムの性能をはじめに10%改善したチームに100万ドルの賞金を与えるという触れ込みで始まったnetflix prizeは当初の予想よりも時間がかかったが、つい最近最初からトップを走り続けていたbellkorと、上位陣のコラボレーションのチームが10%の壁を破った（leaderboard）。 彼らの手法は「非常に多くの様々な種類のレコメンデーションシステムの結果を混ぜ合わせる」という愚直だがいかにも精度が出そうだという方法を採用している（、と昨年度の結果からは思われる。近々詳細は出るだろう。） 実際に使ってとどめになったかどうかは分からないが、彼らのチームの主要メンバーがKDDで新しい手法を発表しており、単一の手法による最高精度を達成している。ちなみに今年のKDD（データマイニング系の学会の最高
大規模データを基にした自然言語処理 - DO++
人工知能基本問題研究会 (SIG-FPAI)でタイトルの題目で一時間ほど話してきました。 発表資料 [pptx] [pdf] 話した内容は - 自然言語処理における特徴ベクトルの作り方と、性質 - オンライン学習, Perceptron, Passive Agressive (PA), Confidence Weighted Learning (CW) 確率的勾配降下法 (SGD) - L1正則化, FOLOS - 索引を用いた効率化, 全ての部分文字列を利用した文書分類 で、スライドで70枚ぐらい。今までの発表とかぶっていないのはPA CW SGD FOLOSあたりでしょうか オンライン学習、L1正則化の話がメインになっていて、その両方の最終形の 確率的勾配降下法 + FOLOSの組み合わせは任意の損失関数に対してL1/L2正則化をかけながらオンライン学習をとても簡単にできるという一昔前
web+db レコメンド特集 サンプルコード - DO++
- WEB+DBプレスの「[速習]レコメンドエンジン」のサンプルプログラムを訂正してみる にあったように、WEB+DB PRESS 49号 レコメンド特集での誌上のサンプルプログラムに誤植があり、そのまま書くとコンパイルできないという問題がありました。 サンプルコードの修正をぎりぎりにお願いして、ゴミが残ってしまったのが原因です。 ご迷惑をみなさんにおかけしました。すいません。 WEB+DB PRESS Vol.49サポートページ ここから、動かせるサンプルコード（Part3用のサンプルコードというところ）をダウンロードできるので、買った方も（そうでない方も？）参考にしてみてください。 以後、気を付けます。
DO++: 教師あり学習の比較
ICML2006に興味深い論文がありました。 "An Empirical Comparison of Supervised Learning Algorithm", Rich Caruana caruana and Alexandru Niculescu-Mizil [link] 90年代初め以降、数多くの画期的な教師あり学習が提案されてきましたが、どれがいいかを包括的に比較したことはあまりありませんでした （文書分類などでは、SVMとAda-boosting 強いねということだったのですが Sebastiani@ACM Survey 2002） 決着をつけようじゃないかということで、11の問題に対してハイパーパラメータも完璧にチューニングして、いろいろな分類器を比較しているみたいです。比較内容は精度や再現率やクロスエントロピーなど様々で、確率を直接出さないやつはsigmoid関数など単調
DO++: 機械学習のチュートリアル (ICML2008)
今年のICML2008はUAIとCOLTの共催と大規模で行なわれたようです。いろいろな方の話を伺うと楽しかったようで。 私は適当にお勧めされた論文やらを読み漁ってます。 個人的に印象深かったのはいくつかのmulti-armed bandit problemの話かな。特にこれとか。 bandit problemは強化学習の中にでてくるような問題の一つで、元々は複数のスロットマシンがあって、これから収益を最大化したいという問題。この時、やらなければいけないことは、現在持っている結果を元に各スロットのモデルを予想するとともに、自分からちょっとリスクを冒してでも他のスロットを試しにいかないといけない。スロットAが今のところ調子いいんだけど、もしかしたらさっきは出なかったスロットBの方がすごい調子がいいかもしれない。探索と最適化がまざったような話ですね。 コンピュータ囲碁で今一番強いモンテカルロ法と
DO++: 機械学習による自然言語処理チュートリアル
自然言語処理のときに使う機械学習手法のテクニックをざーっと２時間程度で紹介してほしいとのことだったので今日話してきました。基本的に、そんなに頑張らなくても効果が大きいものを中心に説明（特にパーセプトロンとか）を説明してます。 紹介した手法はパーセプトロン、最大エントロピー、正則化、多クラス分類、系列分類（CRF, Structured Perceptron）などなどです。どれも一かじりする感じで網羅的に見る方を優先してます。個々の詳しい話はそれぞれの文献や実装などを当たってみてください。 スライド [ppt] [pdf] ここで話しているのは線形識別モデルの教師有り学習が中心で教師無し学習（クラスタリングなど）など他の自然言語処理を支える技術は省いてます。 こういうのを使って（使わなくてもいいけど）どんどんアプリケーション作らないといかんね。 Tarot is not used to ma
DO++: いろんな学会
ICML/UAI/COLTのaccepted paperが出揃い、ざーっと面白そうなのを片っ端から読んでみました。 ICMLの読んでみた、読んでみたいリスト そのうちピックアップします。 ICMLは強化学習系が多くなっているなぁという気もしたのですがそうでもないかな。 ついでに、私が興味を持ってみている機械学習の学会（と一個ジャーナル）紹介を。これも境界領域なので他の学会で面白い話が発表されたりすることも多いです。 機械学習系 JMLR Journal of Machine Learning Research 機械学習の一番メジャーなジャーナルで出るスピードも速い（その年に学会発表されたものがその年のうちに出てくることも珍しくない）。全部web上からタダで論文を落とせる。よいですね ICML International Conference on Machine Learning 機械学習
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
大規模文字列解 析の理論と実践＠IBISML - DO++