ここしばらく、部分文字列の統計量を利用した機械学習やデータマイニングをやっている。そこの話からちょっと抜粋。 長さnの文字列T[1,...,n]が与えられた時、T中に出現する部分文字列T[i...j] (1≦i≦j≦n）の数はn個の中からiとjの2箇所を選ぶのでO(n^2)個ある。例えば、n=10^6(1MB)だったら、部分文字列の数は約10^12個(1T)と非常に大きい。 しかし、これらの部分文字列の出現位置は同じである場合が多い。例えばT="abracadabra"であれば、"abra"と"abr"の出現場所は1番目と8番目であり、全く同じである。 では出現位置（部分文字列の左端を出現位置とする）が全く同じであるような部分文字列をまとめてグループにした場合、グループの数はいくつになるのだろうか。 これは接尾辞木（wikipedia 授業の資料）を知っているなら簡単に説明できる。 Tに対

「乱択アルゴリズム」が共立出版から出ているので読んでいます 乱択アルゴリズム(wikipedia)（ランダマイズドアルゴリズムの方が一般的かもしれない）はアルゴリズムの中に（擬似）乱数が含まれており、動作が決定的ではなく、乱数に依存して動きます。 有名な例では、クイックソートのアルゴリズム中にピボットを選択するところがあるのですが、そこを決定的に最初や真ん中の値ではなく、適当に乱数でランダムに選んだ場合がそれに当たります。 クイックソートは最悪計算量が要素数がnの時、O(n^2)かかってしまう問題点がありますが、ランダムにピボットを選んだ場合、かなり高い確率でO(nlogn)で動作することが言えます。もっとはっきりいうと、比較の回数がαnlogn（αは5よりちょっと大きいぐらい）より大きくなる確率は1/(n^2)以下だということが言えます。つまりnが大きい場合は殆ど間違いなくO(nlogn

プログラミング言語の学会に触発された作った。私視点で書いたので、間違ってたりしたら突っ込んでください。 自然言語処理は、情報検索、ウェブ、機械学習とかとの境界領域だったりするのですが、そういうのは除いてます。 大体の学会情報はACL wiki 論文はACL anthology から得られると思います ACL The Association for Computational Linguistics ACL2008 自然言語処理の一番でかい会議。理論からアプリケーションまで何でも集まるが、強いて言えば 機械翻訳、構文解析が多い。いろいろなワークショップ（１０ぐらい）も併設される。 EMNLP Conference on Empirical Methods in Natural Language Processing EMNLP2008 言語情報から統計的な情報を取り出して機械学習を使って自然

寒くなってきましたね。 日々働いております。 今年、私が衝動買いしたもので、今でも使っているよかったものを気分転換に紹介してみます。 純粋にオススメしたい＆面倒なのでリンクありません。 電気製品 * amazon kindle 3 -- 非常に良い。読みやすい。薄い。軽い。バッテリー１ヶ月ぐらい持つ -- でも現在基本洋書しかないので洋書読めない人はまだ待ちかも。洋書読める人にとっては本が欲しいとおもって５分後には手元で読めるこの改善はすごい。今まで１ヶ月とか待っていたのに。 -- 通勤中にたくさん本読めました * ipad -- 家ではもとからPCは殆ど使わなかったが、ipadが来て家では殆どipad使ってる -- pdfとか読むのにこれ使う。私はaoe3のプレイ動画とか見てる -- 周りの評判は半々。PCのヘビーユーザーは使わないかも。 * torne -- PS3持っていて、HDDレ

大量のデータから、何か有益な情報を求める問題の多くは最適化問題を解くことに帰着されます． 最適化問題とは与えられた関数fの値を最小（最大）にするような変数xを探すといった問題です。 例えば、機械学習（これを利用する自然言語処理、情報検索など）、画像処理、AI(ロボットの経路制御）、 など多くの分野で最適化問題は登場します。 その中でもオンライン最適化（機械学習の文脈でいえばオンライン学習）と呼ばれる最適化手法は 実用性の高さと実装のしやすさから多く利用されるようになってきました。 このオンライン最適化は近年Regret（後悔）最小化というゲーム理論などで使われていた枠組みで 解析されることが多くなってきました。 今回はこのRegret最小化について簡単に解説してみようと思います。 （機械学習が詳しい人向けに補足すると、VC次元など他の機械学習を解析する手法と比べてRegret最適化の面白い

フルタイムで働きはじめて4ヶ月。 いろんなことがありました。 今日はインターンが来ているということもあり日頃のC++コーディングライフの中で大変重用しているツールを紹介します。といってもどれも有名なツールでググれば解説がでてくるとは思いますので、一言ずつだけ紹介してみます。みなさんも何かよさげなライブラリ・ツールがありましたら教えてください。 - valgrind/callgrind/cachegrind プログラムの実行結果を解析するツール群。まぁ、王道であえて紹介する必要はないかもしいませんが.。valgrindはプログラムのどこかでメモリが漏れているかどうかのチェックに使います．コードのどの部分で確保した領域がどこで漏れているかまで追跡することができます valgrind --leak-check=full command プログラムのどのが計算量的にボトルネックになっているかを調べ

ずっとドタバタしていたのですが、ようやく新しい生活のリズムがでてきました。 無事、情報理工学の博士号を取得して卒業し、4月からPreferred Infrastructureでフルタイムで働いています。 研究方面からのお誘いもいろいろあったのですが、会社一本に専念しております。 ただ、研究活動はこれからも会社のバックアップのもとしていきます。 また、3月に結婚もしました。 年明けから博士卒業、結婚の二本柱に加えてNLPチュートリアル、会社の仕事とテンパってました。 なんとか体を壊さず乗り越えられたのはみなさんの助けです。 しかし、喉元過ぎると熱さ忘れるという言葉通り、「これはもうだめだろう」と追い詰められていた時の気持ちを既に忘れつつあります。 誰かの参考になるかもしれませんので、この時の気持ちも含め博士３年過ごして感じたことや、研究の話とかを思い出せる範囲で書いてみます。 --- 私が修

昨晩、学部時代に入っていたサークルのOB会がありました。 OB会といっても、集まった中で、私達の代が一番上の世代で、若い人達から非常にエネルギッシュなパワーをもらいました。 ふと、私が学部１年の時に博士課程の人がたまに来ていたのを思い出しました。 とても面白い人で漠然と博士課程とはこういうものなのかぁと思ってましたが、逆の立場になるとは。 その場で唯一博士課程に進んでいた私に対し、博士課程について、いろいろな質問をもらいました。進学するかどうかを迷っている人もいて、ちょっと酔ってましたが、真面目に答えました。 現在、巷で氾濫している博士課程の情報はかなり悲観的な状況のようです。 （例えば、博士課程で検索すると、就職、行方、お金などなどいろいろ悲観的な情報で氾濫しています。博士１００人の村とかも有名ですね） 私が置かれている状況（コンピュータ系の研究、個人で研究できる、研究室はそこそこ大きい

様々なオンライン学習手法をサポートしたライブラリ「OLL (Online-Learning Library)」をリリースしました。 プロジェクトページ 日本語詳細ページ 学習、推定を行なう単体プログラムと、C++ライブラリからなります。（C++ライブラリ解説はまだ）。 New BSDライセンス上で自由に使えます。使った場合は感想や苦情などいただけると幸いです。 オンライン学習とは、一つずつ訓練データを見てパラメータを更新していく手法で、訓練データをまとめて見てから学習するバッチ学習（SVMs, 最大エントロピー法）と比べて非常に効率良く学習を行なうことができます。それでいながらSVMs, やMEsに匹敵する精度が出ます。 学習するデータの性質にもよりますが、例えば、英語の文書分類タスクで、15000訓練例、130万種類の素性の訓練データに対する学習が1秒未満で終わります（SVMsだと実装に