前回の記事は長くなりすぎたので、長文を読みたくない人のために、まず三行であらすじをまとめる。 ソフトマージンSVMがマージン最大化してるって言うけど、ちゃんと理解するの結構難しくない？ なんか自分の中で議論を進めると、正則化項つきパーセプトロンもマージン最大化に分類されるんだけど大丈夫？ こうなったらもう、正則化項つきパーセプトロンを実装して、実験してみるしかない…次回に続く という話であった。 さて、前回の落ち穂ひろいから始めよう。前回「マージン最大化はSVMの特権ではなく、MIRAとかAveraged Perceptronとか、ラージマージン分類器と呼ばれる分類器はいくつもある」と書いたが、ここでは、「マージン最大化」という概念と、「ラージマージン」という、似たようだが違うかもしれない概念が混同して提示されている。どうも、この二つの用語は分けて考えた方が良さそうに思える。 その観点から

SVMの説明というと、よく出てくるのはマージンの最大化である。しかし、実装を行う場合には、どちらかというと目的関数をどうやって最小化しようかな、というところの方が重要（注：主形式を勾配法で最適化する場合の話です）で、この間にある微妙なギャップを超えるのは微妙ながらも大変なような気がしている。このギャップをどうやったら埋められるのかというところを考えてみたい。考えながら書いてきちんと推敲しておりませんのでご注意ください。 SVMってなに、という説明でよくあるパターンは、線形識別器（というか、SVM）の学習というのはパラメーターをいじって分離(超)平面をいい感じに引くことですよ、というところから始まり、いい感じってなんだろうか、マージンが最大化されるように引くといいっぽいよね、けど分離不可能な場合はマージンの値が負になることがあるよね、そこでソフトマージンというものを定義して、マージンが負にな

現在のウェブアプリはHTMLとJavaScriptで構成される。一般的なデスクトップアプリで言うツールキットの部分に相当するのがHTMLである。しかし、この組み合わせでは、デスクトップアプリと比べて取れないイベントが多く、setIntervalで定期的にハンドラを呼び出して状態をチェックする、というテクニックがよく使われる。 ウェブアプリ側からは自分が今バックグランドタブにいるのか、フォアグラウンドタブにいるのかはわからないため、setIntervalは常に呼ばれている。タブを数十個開いた状態では、バックグラウンドで使いもしないウェブアプリのハンドラが恐ろしい回数呼び出されて、それがCPUを浪費してしまう、という事が起こり得る。 しかし、この状況はFirefox 5によって変わるかもしれない。ふとどこかで見つけたのだが、FirefoxのFlight Trackingというページを眺めていた

新年明けましておめでとうございます、というのもはばかられるような時期になってしまいましたが、今年もこんな感じでのんびりとやっていきたいと思います。よろしくお願いします。 会社ブログの方で、劣微分を使った最適化手法として、FOBOSを紹介しました。線形識別器とは、というところから話を始めたら、実際の論文紹介にたどり着くまでに4回もかかってしまいましたが、何も知らないところからFOBOSでSVMが書けるというところまで、早足ですが一応一通り紹介したつもりなので、FOBOSに興味があるけどまだ論文読んでない、という人はぜひチェックしてもらえればと思います。使えるカーネルは線形カーネルか多項式カーネルぐらいに制限されてしまいますが、実用的なSVMが簡単に作れるというのは結構大きいですよ。ちなみに、FOBOSのところではSVMしか説明していませんが、第2回ではロジスティック回帰をSGDで最適化、とい

しばらく日記書いてなかったら、また文体忘れて敬体で書いちゃったよ…。でも常体に書き換えるのもめんどくさいのでこのままうpします。 単語分割器を作ったので、githubで公開しました。→http://github.com/tkng/micter 名前は単純にMIC segmenTERでmicterにしました。作ってから気づいたのですが、segmentという単語のうち、最後のtしか名前に入っていません。今更名前を変えるのも面倒なのでこのままにしておきますが、微妙に失敗した感がありますね…。 形態素解析器としては既にmecabやらchasenやらjumanやらがありますし、最近では単語分割&読み推定のkyteaもあります。そんなにいろいろある中でまた似たようなツールを書いたのは、自分のパッケージに取りこめる小さな単語分割器が欲しかったのが理由です。文章を単語に分割する機能だけあればいいんだけど、

TSFのメモとMozcのコード読みメモを比較すると、書くのにかかった時間は4,5倍は違う（TSFの方が大変だった）のに、ブックマーク数は逆転どころか桁が2桁違う事になりそうだなぁ、と、あらためてGoogleの人気のすごさを体感した。小町さんは こんなに日本語入力って注目されるんだと嬉しい気持ち と書いておられるが、個人的な感触としては、日本語入力が注目されているというよりはGoogleが注目されている、というあたりが悲しい現実なのではないかと思う。とは言え、自分もChaSenのコードとか読んだことない（mecabは少しだけ読んだ事があるけど）ので、あんまり人の事は言えないが。 さて、週末にバイグラムコストの保存方法についても現実逃避で読んでしまったので、ついでに解説を試みる。 前のメモにも書いたが、Google日本語入力のコストモデルは「品詞バイグラム+単語ユニグラム」という構成になってい

Google日本語入力がOSS化されたということで、気になっていたところをいくつか確認してみた。 変換アルゴリズムはどんな感じか？ twitterの工藤さんの発言にも「わりと古典的な最小コスト法」とあるけれど、まさにそんな感じ。人名の処理とかでちょっと特別なコードが入ったりもしているが、ほぼ基本的な統計的かな漢字変換のモデル。係り受けの情報とかは使っていない。Viterbiでベストパスを求めて、品詞ベースで文節にまとめあげている。コストモデルは接続コストが品詞対品詞で、単語コストの方は単語毎に設定されているっぽい。 src/converter/immutable_converter.ccのImmutableConverterImpl::ViterbiがViterbiアルゴリズムの部分で、その後にMakeSegmentsで文節にまとめている。読むならImmutableConverterImp

KyTea(京都テキスト解析ツールキット)は京大のGraham Neubigさんが中心となって開発している単語分割&発音推定ツールである。 私はかな漢字変換用の学習データを作るのにこれまではmecabを使っていたのだが、mecab-ipadicのデータには、そもそも読み推定に力が入ってない、という問題があった。形態素解析は文章を単語に区切ることと品詞を推定する事が主目的な感じなのでそこを期待するのはそもそも筋違いなのだが。 かといって自分で作ろうにも、こういうものは学習用コーパスが必要なので、コードだけで簡単にどうにかできる問題ではない。コーパス作りはとても手間のかかる作業なので、気軽に週末に作れるようなものでもない。というわけで、根本的な解決は棚上げして、これまではmecabの解析結果を後付けで適当に確率的に揺らしてみたりとかしながら使ってきたのである。 そこに新しくKyTeaが現れた。

転職するまでskypeチャットは使ったことが無かったのだが、skypeチャットにはいろいろと魅力がある。 通信が暗号化されている 中国版は中国政府が検閲できるという話もないではないが… 自分がログインしてなかった期間のチャットログもログインすると適当に流れてくる どういうタイミングで送られてくるのかよくわからないが、ログインしてしばらくすると、ログアウトしていた期間のログが送られてくる サーバにはログが残らない 秘密のお話もしやすいね！ skypeのチャットログはチャットルームに参加した人のみが閲覧でき、参加していなかった間のログも送られてくる。そして挙動からしておそらくサーバではログは保存していない。こういう仕様を実現しようとすると、P2Pに成らざるを得ないのかなぁ。考えてみれば、skype以外には、こういった仕様のクライアントは見たことがない。ただ、skypeはバージョンが上がるたびに

本当は三が日中にまともなエントリを1本ぐらいは書く予定だったのだが、ちょっと無理だった。というわけで、実質的に新年一本目のエントリです。Large Scale Learning to Rank (D. Sculley, NIPS Workshop on Advances in Ranking, 2009) (pdf) を読んだので、1本目のエントリとしてこの論文を紹介したい。 では早速本題に入ろう。順位学習において、Pairwise Learningを単純に行うと、n^2の学習コストがかかる。これは計算時間としては厳しい部類に入る。そもそも順位学習ってなに、という人は、WWW2009のチュートリアル(pdf)とかを参照してください。 Bottouらは、SGDの一般化能力はデータセットのサイズに依らず、どれだけのstochastic stepを実行したかで決まると言う事を示した。そこで、Sc

ディレクトリの中にある大量のファイルを高速に読み込む方法が知りたかったので、実験してみた。想定しているシチュエーションは、一つ一つのファイルは数KB程度だが数が多い、という場合である。適当な順番でアクセスすると、ランダムアクセスになってしまいとても時間がかかる。個々のファイルを読み込む順番はどうでも良く、すべてのファイルを処理することさえできればいいので、原理的にはシーケンシャルアクセスで処理できてしかるべきである。 まず、ファイルシステムについて。HDDやSSDなどのハードウェアにアクセスする際には、ファイル名などという概念はもちろん存在しない。ファイル名と実際のディスク上の対応を管理するのがファイルシステムの主な役割である。ファイルシステムは、ファイル名からそのファイルに対応するブロック番号（メモリアドレスみたいなもんだな）を調べて、そのブロック番号を指定してHDDやSSDにアクセスす

sshにはダイナミック転送という機能がある。この機能を使うと、sshはアプリケーション側にはSOCKSプロクシとして振る舞うが、そこからsshの接続先までは暗号化された状態で通信が行われる。 これだけだと通常のトンネリングとどう違うのかよくわからないかもしれないが、ダイナミック転送の場合は転送ポートを指定する必要がない。ここがダイナミックと表現される所以だろう。 例えば、オフィスAにある開発サーバdev1にオフィス外からアクセスしたいとする。しかし、dev1はオフィス外には公開されておらず、踏み台サーバladd1を経由してしかアクセスするしかない。ladd1はsshのみが動いており、これまではsshのトンネリング機能を使ってアクセスしてきたのだが、ウェブアプリケーションをデバッグする際はいちいちウェブアプリケーションのポート毎にトンネルを掘るのが面倒くさい。オフィスに限らずデータセンターへ

宣伝です。Preferred Infrastructureで夏期インターン募集を開始しました。 注目ポイントとしては、割と高めに設定された時給（高校生1200円〜、大学生以上は1500円〜。）と、あとは個人的にはベンチャー企業の表と裏が見放題というところが、参加してみないと分からないおもしろさかなと思います。 ベンチャー企業に興味がある方、情報検索や自然言語処理、その他様々なアルゴリズムに興味のある方、ぜひご応募くださいませ。 追記：問い合わせを検討し、遠方からの方には住宅も用意させていただくことになりました！その場合は週5での勤務になります。 さらに追記：技術評論社様からのご厚意により、特別表彰の副賞として、WEB+DB PRESS年間購読権が頂ける事になりました！

2月は割とガンガンと開発をしてきたのだが、3月に入ってさすがにエネルギーが切れてきたので、一旦、気分転換にエントリに書いてみることにする。 ChaIMEというのは主に研究目的のかな漢字変換エンジンである。奈良先の小町さん(id:mamoruk)がメインで開発していて、自分もここしばらくはアクティブに開発している。こちらでデモを試すことができる。ChaIMEの特徴はひたすらに統計情報で変換をするところなのだが、今回はそういった話ではなく、もうちょっと一般的なかな漢字変換についての話をダラダラと書いてみようと思う。 デモを見て分かる通り、今までのChaIMEはステートレスで、ひらがな列を入力に対してそれっぽい変換候補を複数出力してさぁ選べ、という形だった。文節境界を変更したり、文節毎に候補を出すことはできない。これは単に実装コストの問題で、研究用途で実験をする際には文節境界を変更してどうたらこ

ICML2008で発表されたDredzeらのConfidence Weighted Linear Classificationを読んだ。これは線形分類器を学習する新しいオンライン学習型アルゴリズムの提案である。すぐに使える実装としてはOLLというオープンソースのライブラリがあり、実際に良い実験結果が出ているようだ。 Confidence Weightedのアイデアは、よく出てくる素性に関しては一回の更新における数値の変更量を減らしてやり、あまり出てこない素性に関しては、一回の更新でぐっと値を変更してやろう、というものである。 こういった新しい更新方法を考案した動機を明らかにするために、Perceptronを使って、単語を素性として評判分類の学習を行うような問題を考えてみる。肯定的な評価のサンプルとして"I liked this author."というものがあったとすると、このサンプルの分類

新はてブ正式リリース記念ということで。もうリリースから何週間も経っちゃったけど。 新はてなブックマークではブックマークエントリをカテゴリへと自動で分類しているが、このカテゴリ分類に使われているアルゴリズムはComplement Naive Bayesらしい。今日はこのアルゴリズムについて紹介してみる。 Complement Naive Bayesは2003年のICMLでJ. Rennieらが提案した手法である。ICMLというのは、機械学習に関する（たぶん）最難関の学会で、採択率はここ数年は30%を切っている。2003は119/371で、32.1%の採択率だったようだ。 Complement Naive Bayesの位置づけは 実装が簡単 学習時間が短い 性能もそこそこよい という感じで、2003年段階にあっても、絶対的な性能ではSVMに負けていた。しかし、学習が早いというのは実アプリケーシ