買ってよかったもの 2010秋 - DO++
寒くなってきましたね。 日々働いております。 今年、私が衝動買いしたもので、今でも使っているよかったものを気分転換に紹介してみます。 純粋にオススメしたい＆面倒なのでリンクありません。 電気製品 * amazon kindle 3 -- 非常に良い。読みやすい。薄い。軽い。バッテリー１ヶ月ぐらい持つ -- でも現在基本洋書しかないので洋書読めない人はまだ待ちかも。洋書読める人にとっては本が欲しいとおもって５分後には手元で読めるこの改善はすごい。今まで１ヶ月とか待っていたのに。 -- 通勤中にたくさん本読めました * ipad -- 家ではもとからPCは殆ど使わなかったが、ipadが来て家では殆どipad使ってる -- pdfとか読むのにこれ使う。私はaoe3のプレイ動画とか見てる -- 周りの評判は半々。PCのヘビーユーザーは使わないかも。 * torne -- PS3持っていて、HDDレ
オンライン最適化とRegret最小化 - DO++
大量のデータから、何か有益な情報を求める問題の多くは最適化問題を解くことに帰着されます． 最適化問題とは与えられた関数fの値を最小（最大）にするような変数xを探すといった問題です。 例えば、機械学習（これを利用する自然言語処理、情報検索など）、画像処理、AI(ロボットの経路制御）、 など多くの分野で最適化問題は登場します。 その中でもオンライン最適化（機械学習の文脈でいえばオンライン学習）と呼ばれる最適化手法は 実用性の高さと実装のしやすさから多く利用されるようになってきました。 このオンライン最適化は近年Regret（後悔）最小化というゲーム理論などで使われていた枠組みで 解析されることが多くなってきました。 今回はこのRegret最小化について簡単に解説してみようと思います。 （機械学習が詳しい人向けに補足すると、VC次元など他の機械学習を解析する手法と比べてRegret最適化の面白い
博士生活振り返り - DO++
ずっとドタバタしていたのですが、ようやく新しい生活のリズムがでてきました。 無事、情報理工学の博士号を取得して卒業し、4月からPreferred Infrastructureでフルタイムで働いています。 研究方面からのお誘いもいろいろあったのですが、会社一本に専念しております。 ただ、研究活動はこれからも会社のバックアップのもとしていきます。 また、3月に結婚もしました。 年明けから博士卒業、結婚の二本柱に加えてNLPチュートリアル、会社の仕事とテンパってました。 なんとか体を壊さず乗り越えられたのはみなさんの助けです。 しかし、喉元過ぎると熱さ忘れるという言葉通り、「これはもうだめだろう」と追い詰められていた時の気持ちを既に忘れつつあります。 誰かの参考になるかもしれませんので、この時の気持ちも含め博士３年過ごして感じたことや、研究の話とかを思い出せる範囲で書いてみます。 --- 私が修
行列分解ライブラリredsvdを公開しました - DO++
大規模疎行列向けの行列分解ライブラリredsvdを公開しました． redsvd 大規模疎行列向けの特異値分解や主成分分析，固有値分解を行うライブラリredsvdを公開しました． 修正BSDライセンスで公開しており，コマンドラインから使える他，C++ライブラリが用意されています． 例えば，行と列数がそれぞれ10万，非零の要素が1000万からなる疎行列に対する上位20位までの特異値分解を約2秒で処理します． 特異値分解とか，使っている技術の詳細とか応用事例を以下に簡単に紹介しましたので，興味のある方は参考にしてください． 特異値分解とは まず行列を適当に復習します．行列Xの転置をX^tと表すことにします．またIを単位行列とし，Oを全ての成分が0である零行列とします．また，行列XX^t=IであるようなXを直交行列と呼びます．Xが直交行列の時，Xvはベクトルvを長さを変えずに回転させます．ここでは
NLP2010 言語処理学会チュートリアル - DO++
今日から開催されている言語処理学会のチュートリアルで ”超高速テキスト処理のためのアルゴリズムとデータ構造” というタイトルで発表させていただきました。 チュートリアル資料はこちら(pdf)です。（出典などは適宜追加します） 今までいろいろなところで話してきた、オンライン学習、文字列、疎ベクトルデータ構造を最新の話を追加して、さらに乱択化（Hash Kernel, 乱択化SVD)を解説しています。 発表自体は途中でブルースクリーンが出るということもありましたが、なんとか終えられてよかったです。 これに付随していろいろツールを公開する予定だったがまにあわなかった。そのうち公開します
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+
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（データマイニング系の学会の最高
NAACL/HLT 2009報告 - DO++
コロラド・ボルドーで開催されたNAACL/HLT 2009に行ってきました。 NAACLは自分の中での分類では自然言語処理の学会で統計的な手法とかが多い学会に思える（それに対しヨーロッパではEACLでは文法とか言語理論とかが多い）。比較的自分にあう学会。 開催地となったコロラド大ボルダー校はとてもきれいなキャンパスで（、「全米で最も美しいキャンパス」の4位にランキング）、宇宙飛行士をたくさん輩出してたり、ノーベル物理学賞を４名輩出するなど、研究レベルも高いそうです。 で、学会は適当に休みながらまったり聞いていたのですが全体的に教師無学習に関する話が多かったような気がします。教師有学習による言語処理がある程度成熟してきているのに対し、教師無の方はまだまだ伸びしろが多いので研究がしやすいのでしょう。教師無に利用するモデルも、単純な混合分布から、様々な分布が入り乱れる複雑なグラフィカルモデルにな
貪欲な変数選択による最適化 - DO++
最適化問題において、最適化対象の変数を最初は空に初期化して、関数値にもっとも効きそうな変数から順に最適化対象にGreedyに加えていく方法は変数の数が非常に多い場合（全ての部分文字列に特徴が対応するなど、そもそも列挙できないくらい多い場合など）に有効です。 詳細な中身は違いますが、grafting, column generation, cutting planeとかがこの枠組みに当てはまルと思います。 ここでのポイントは「効きそうな変数」を効率的に求めることができたら、圧倒的に速く最適化できるようになることです。別分野でデータマイニングの手法だとか、上限/下限だとかデータ構造とか何か技を持っている人は、ぜひチャレンジしてみてください。 で、私もやってます。という宣伝 ・特徴（変数）が文書中の全ての部分文字列に対応する場合 "Text Categorization with All Sub
ohmm（オンラインEMによるHMM学習）をリリースしました - DO++
Ohmm-0.01をリリースしました [Ohmm 日本語] [Ohmm English] これは、以前のブログで書いた、オンラインEM法をそのまま素直に隠れマルコフモデル(HMM)に対し適用したライブラリです。 使う場合は、単語（アクセス履歴とかなんでもよい）に分けられているテキストを入力として与えれば、HMMによる学習を行い、結果を出力します。他で利用できるように、パラメータを出力したり、単語のクラスタリング結果を出力します。 HMM自体は、言語情報やアクセス履歴、生物情報（ＤＮＡ）といったシーケンス情報において、前後の情報を用いて各要素をクラスタリングしたい場合に用います。 本ライブラリの特徴はオンラインEMの特徴通り、従来のEMよりも速く収束します。一応標準的な最適化手法（スケーリング、スパースな期待値情報の管理）もいれているので、そこそこ高速に動きます 速度的には100万語、隠れ状
オンラインEMアルゴリズム - DO++
EMアルゴリズム（Expectation Maximizationアルゴリズム、期待値最大化法、以下EMと呼ぶ）は、データに観測できない隠れ変数（潜在変数）がある場合のパラメータ推定を行う時に有用な手法である。 EMは何それという人のために簡単な説明を下の方に書いたので読んでみてください。 EMのきちんとした説明なら持橋さんによる解説「自然言語処理のための変分ベイズ法」や「計算統計 I―確率計算の新しい手法 統計科学のフロンティア 11」が丁寧でわかりやすい。 EMは教師無学習では中心的な手法であり、何か観測できない変数を含めた確率モデルを作ってその確率モデルの尤度を最大化するという枠組みで、観測できなかった変数はなんだったのかを推定する場合に用いられる。 例えば自然言語処理に限っていえば文書や単語クラスタリングから、文法推定、形態素解析、機械翻訳における単語アライメントなどで使われる。
web+db レコメンド特集 サンプルコード - DO++
- WEB+DBプレスの「[速習]レコメンドエンジン」のサンプルプログラムを訂正してみる にあったように、WEB+DB PRESS 49号 レコメンド特集での誌上のサンプルプログラムに誤植があり、そのまま書くとコンパイルできないという問題がありました。 サンプルコードの修正をぎりぎりにお願いして、ゴミが残ってしまったのが原因です。 ご迷惑をみなさんにおかけしました。すいません。 WEB+DB PRESS Vol.49サポートページ ここから、動かせるサンプルコード（Part3用のサンプルコードというところ）をダウンロードできるので、買った方も（そうでない方も？）参考にしてみてください。 以後、気を付けます。
レコメンド, LSH, Spectral Hashing - DO++
WEB+DB press vol.49にレコメンド特集の記事をtkngさんと書きました。 内容は最初は、協調フィルタリングやコンテンツマッチの簡単な話から、特徴量をどのように表すか、大規模データをどのように処理するかにいき、特異値分解などの低ランク行列分解によるレコメンドやRestricted Boltzmann Machineといった最近のnetflix prizeの上位の手法など、かなり突っ込んだ議論もしてます。 個人的には三章でLocality Sensitive Hash(LSH)について扱っているあたりがお勧めです。 レコメンドの内部の問題を極言すると、データというのは疎な高次元の数値ベクトル（数百万次元とか）で表され、クエリでベクトルが与えられた時、これと似たようなベクトルを探してこいという問題になります。”似たような”を数学的にいえば、クエリのベクトルとの内積（各ベクトルは長
昨年の論文をふりかえる - DO++
新年すっかりあけてました。 今年もよろしくお願いします。 年末年始はドタバタして昨年を振り返られなかったのですが、せっかくなので2008年に読んだ論文で私個人のベスト５を以下に列挙してみます。 D. Sontag, et. al. "Tightening LP Relaxations for MAP using Message Passing", UAI 2008 [pdf] Graphical ModelのMAP推定問題で従来解けなかった規模の複雑さの問題を高速にしかも最大であるという保障付きで解けるようにした。書いたメンバーはこの問題に関するオールスターのような感じ。解く問題は、n個の頂点からなるグラフで、各頂点には変数x1...xnがついていて、各頂点と各枝に対し関数gi(xi)、gij(xi,xj)が与えられた時、∑i gi(xi) + ∑ij gij(xi,xj)が最大となるよう
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++ : suffix arraysやいろいろ
suffix arraysの話は半年置きぐらいに書いているのかなぁ。 (ココログ全文検索機能無くて、不便ですね・・以前どこに書いたのか分からない。） 私が以前書いたSuffix Arraysの構築方法の記事が古くなってきたので（分かりにくいし）、近いうちにライブラリと一緒に内容も更新しようかなと。今回は、忘れないうちにメモも兼ねてSuffix Arraysの高速な構築方法について。 構築で今一番速いのは、msufsortとimproved two-stage (プログラム名はdivsufsort）(its)法だと思います。これらはデータサイズに対して線形時間で構築できる方法では無いのですが、大抵のデータでは線形時間の方法より高速に構築することが可能です。 msufsortはsuffix arrays:SAを直接構築するのではなく、その逆の値であるinverted suffix arrays
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
私達のNグラムはすべてあなたに属するある - DO++
現実的な圧縮付全文索引 (PDF)