Confidence Weighted Linear Classificationを読んだ - 射撃しつつ前転 改
ICML2008で発表されたDredzeらのConfidence Weighted Linear Classificationを読んだ。これは線形分類器を学習する新しいオンライン学習型アルゴリズムの提案である。すぐに使える実装としてはOLLというオープンソースのライブラリがあり、実際に良い実験結果が出ているようだ。 Confidence Weightedのアイデアは、よく出てくる素性に関しては一回の更新における数値の変更量を減らしてやり、あまり出てこない素性に関しては、一回の更新でぐっと値を変更してやろう、というものである。 こういった新しい更新方法を考案した動機を明らかにするために、Perceptronを使って、単語を素性として評判分類の学習を行うような問題を考えてみる。肯定的な評価のサンプルとして"I liked this author."というものがあったとすると、このサンプルの分類
パーセプトロンはマージン最大化の夢を見るか？ - 射撃しつつ前転 改
前回の記事は長くなりすぎたので、長文を読みたくない人のために、まず三行であらすじをまとめる。 ソフトマージンSVMがマージン最大化してるって言うけど、ちゃんと理解するの結構難しくない？ なんか自分の中で議論を進めると、正則化項つきパーセプトロンもマージン最大化に分類されるんだけど大丈夫？ こうなったらもう、正則化項つきパーセプトロンを実装して、実験してみるしかない…次回に続く という話であった。 さて、前回の落ち穂ひろいから始めよう。前回「マージン最大化はSVMの特権ではなく、MIRAとかAveraged Perceptronとか、ラージマージン分類器と呼ばれる分類器はいくつもある」と書いたが、ここでは、「マージン最大化」という概念と、「ラージマージン」という、似たようだが違うかもしれない概念が混同して提示されている。どうも、この二つの用語は分けて考えた方が良さそうに思える。 その観点から
SVMのマージン最大化についてしつこく考えてみる - 射撃しつつ前転 改
SVMの説明というと、よく出てくるのはマージンの最大化である。しかし、実装を行う場合には、どちらかというと目的関数をどうやって最小化しようかな、というところの方が重要（注：主形式を勾配法で最適化する場合の話です）で、この間にある微妙なギャップを超えるのは微妙ながらも大変なような気がしている。このギャップをどうやったら埋められるのかというところを考えてみたい。考えながら書いてきちんと推敲しておりませんのでご注意ください。 SVMってなに、という説明でよくあるパターンは、線形識別器（というか、SVM）の学習というのはパラメーターをいじって分離(超)平面をいい感じに引くことですよ、というところから始まり、いい感じってなんだろうか、マージンが最大化されるように引くといいっぽいよね、けど分離不可能な場合はマージンの値が負になることがあるよね、そこでソフトマージンというものを定義して、マージンが負にな
単語分割器Micterを公開しました - 射撃しつつ前転 改
しばらく日記書いてなかったら、また文体忘れて敬体で書いちゃったよ…。でも常体に書き換えるのもめんどくさいのでこのままうpします。 単語分割器を作ったので、githubで公開しました。→http://github.com/tkng/micter 名前は単純にMIC segmenTERでmicterにしました。作ってから気づいたのですが、segmentという単語のうち、最後のtしか名前に入っていません。今更名前を変えるのも面倒なのでこのままにしておきますが、微妙に失敗した感がありますね…。 形態素解析器としては既にmecabやらchasenやらjumanやらがありますし、最近では単語分割&読み推定のkyteaもあります。そんなにいろいろある中でまた似たようなツールを書いたのは、自分のパッケージに取りこめる小さな単語分割器が欲しかったのが理由です。文章を単語に分割する機能だけあればいいんだけど、
rxを読んだメモ - 射撃しつつ前転 改
rxはGoogle日本語入力（Mozc）でも使われているTrieのライブラリである。LOUDSというツリーを表す簡潔データ構造を使ってTrieを実現している。第2回自然言語処理勉強会@東京に行ってきて、そういえばrxは読んでなかったなと思ったので、ちょっとだけ読んでみた。あくまでもメモ書きである。絵があると100倍ぐらいわかりやすくなる気がするけどメモなので絵は描きません。 読んだのは現在公開されている最新版であるrx-1.0rc4。 rxというのとrbxという2つの機能がある。rxが実現しているのはあくまでもtrieで、値的なものとしてはノードIDしか取れない。rbxはノードIDのような整数から、任意の長さのバイト列を引っ張ってくるためのライブラリ。普通の配列は当たり前だが要素が固定長であるので、要素が可変長であるというところがrbxの大きな特徴である。 rxでのエッジに対する文字割り当
google-glogに潜むトリックを解明する - 射撃しつつ前転 改
google-glogは非常に有名なロギングライブラリであり、その名前からわかる通りgoogleの人々によって開発されている。使い方は簡単で、 LOG(INFO) << "this is not a drill"; みたいな感じで、LOG()が返すオブジェクトoperator<<で記録したいオブジェクトをつなげていくだけで使える。とても便利である。実は、この便利さの裏には、実はいくつかのトリックが隠れている。適当に見た目を真似して作るだけでは、glogと同じような便利さは実現できないのである。今日は、その便利さを実現しているトリックを紹介したい。 なぜLOG()はマクロなのか まず、このLOG(INFO)というのは一見、関数もしくはクラスのコンストラクタかなにかに見える。しかしその実体は実はマクロで、以下のように展開される。 LogMessage(INFO).stream() LOGという
条件付き確率場のマルコフ性とか準マルコフ連鎖とか - 射撃しつつ前転 改
実装する上ではどうでもいい、言葉の定義の問題のところに足を突っ込みつつあるような気もするけれど、CRFについて調べていたらどんどん混乱してきたので、現在のところの理解をまとめてみる。たぶん、突っ込みどころはいっぱいありますので、突っ込んで頂けると幸いです。 CRFは入力Xと出力Yの組をたくさん与えることで、未知のXに対してもP(Y|X)を計算できるようにするモデルである。ただし、Yは構造を持つ（この構造を持つというのがどう言うことかもややこしくて今調べているのだが、こちらはとりあえず棚上げする）ものとする。 CRFはであるということしか規定せず、自然言語処理ではlinear chain CRFとsemi markov CRFの2つ、特にlinear chain CRFがよく使われている。 linear chain CRFは出力Yが一本鎖の構造になっているところが特徴である。linear c
Text Service Frameworkに関するメモ - 射撃しつつ前転 改
諸事情でWindowsの文字入力について調べたのだが、専門用語が多くて理解に時間がかかったので、数ヶ月後の自分のためにメモしておく。 Text Service Framework(以下TSF)は汎用的な文字入力フレームワークで、キーボードだけではなく、音声認識や手書き入力などもサポートできるフレームワークである。 TSFを考える時には登場人物が3つある。アプリケーション、テキストサービス、テキストサービスマネージャの3種類である。アプリケーションが普通のアプリケーションデベロッパが開発するもの、テキストサービスがかな漢字変換エンジンのベンダーなどが開発するものである。テキストサービスマネージャはアプリケーションとテキストサービスを仲介する。アプリケーションとテキストサービスが直接通信することはなく、必ずテキストサービスマネージャを通す（らしい）。以下、いくつか用語を箇条書きする。 アンカー
Mozc(Google日本語入力)のコードを読んだメモ - 射撃しつつ前転 改
Google日本語入力がOSS化されたということで、気になっていたところをいくつか確認してみた。 変換アルゴリズムはどんな感じか？ twitterの工藤さんの発言にも「わりと古典的な最小コスト法」とあるけれど、まさにそんな感じ。人名の処理とかでちょっと特別なコードが入ったりもしているが、ほぼ基本的な統計的かな漢字変換のモデル。係り受けの情報とかは使っていない。Viterbiでベストパスを求めて、品詞ベースで文節にまとめあげている。コストモデルは接続コストが品詞対品詞で、単語コストの方は単語毎に設定されているっぽい。 src/converter/immutable_converter.ccのImmutableConverterImpl::ViterbiがViterbiアルゴリズムの部分で、その後にMakeSegmentsで文節にまとめている。読むならImmutableConverterImp
ディレクトリの中にある大量の小さなファイルを高速に読み込む方法 - 射撃しつつ前転 改
ディレクトリの中にある大量のファイルを高速に読み込む方法が知りたかったので、実験してみた。想定しているシチュエーションは、一つ一つのファイルは数KB程度だが数が多い、という場合である。適当な順番でアクセスすると、ランダムアクセスになってしまいとても時間がかかる。個々のファイルを読み込む順番はどうでも良く、すべてのファイルを処理することさえできればいいので、原理的にはシーケンシャルアクセスで処理できてしかるべきである。 まず、ファイルシステムについて。HDDやSSDなどのハードウェアにアクセスする際には、ファイル名などという概念はもちろん存在しない。ファイル名と実際のディスク上の対応を管理するのがファイルシステムの主な役割である。ファイルシステムは、ファイル名からそのファイルに対応するブロック番号（メモリアドレスみたいなもんだな）を調べて、そのブロック番号を指定してHDDやSSDにアクセスす
最近のDoubleArrayの性能 - 射撃しつつ前転 改
DoubleArrayの性能に関して、最近は少し改善されているかも知れませんとあるので、具体的にどれぐらい改善されているのか、少し書いてみます。もちろん、現実逃避です。 まず、DoubleArrayがなんなのかというところから説明をします。DoubleArrayは、簡単に言うとTrieを実現するためのデータ構造の一種です。日本語ではダブル配列と呼ばれているようです。Trieに関しては横着プログラミング 第6回: chatty: 小うるさい端末あたりを読めば良いでしょうか。要するにTreeを表現するためのデータ構造です。使い道はいろいろありますが、辞書的なものに使われることが多いでしょうか。 Trieを単純に実現しようとすると、すごくたくさんメモリを使ってすごく速い実装をするか、速度を多少犠牲にしてメモリ消費量を削減するかの選択を迫られます。多くの場合はメモリを節約しないと使いものにならない
Firefoxからsshのダイナミック転送を使って非公開サーバへアクセスする - 射撃しつつ前転 改
sshにはダイナミック転送という機能がある。この機能を使うと、sshはアプリケーション側にはSOCKSプロクシとして振る舞うが、そこからsshの接続先までは暗号化された状態で通信が行われる。 これだけだと通常のトンネリングとどう違うのかよくわからないかもしれないが、ダイナミック転送の場合は転送ポートを指定する必要がない。ここがダイナミックと表現される所以だろう。 例えば、オフィスAにある開発サーバdev1にオフィス外からアクセスしたいとする。しかし、dev1はオフィス外には公開されておらず、踏み台サーバladd1を経由してしかアクセスするしかない。ladd1はsshのみが動いており、これまではsshのトンネリング機能を使ってアクセスしてきたのだが、ウェブアプリケーションをデバッグする際はいちいちウェブアプリケーションのポート毎にトンネルを掘るのが面倒くさい。オフィスに限らずデータセンターへ
新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ - 射撃しつつ前転 改
新はてブ正式リリース記念ということで。もうリリースから何週間も経っちゃったけど。 新はてなブックマークではブックマークエントリをカテゴリへと自動で分類しているが、このカテゴリ分類に使われているアルゴリズムはComplement Naive Bayesらしい。今日はこのアルゴリズムについて紹介してみる。 Complement Naive Bayesは2003年のICMLでJ. Rennieらが提案した手法である。ICMLというのは、機械学習に関する（たぶん）最難関の学会で、採択率はここ数年は30%を切っている。2003は119/371で、32.1%の採択率だったようだ。 Complement Naive Bayesの位置づけは 実装が簡単 学習時間が短い 性能もそこそこよい という感じで、2003年段階にあっても、絶対的な性能ではSVMに負けていた。しかし、学習が早いというのは実アプリケーシ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
