William Cohenの情報抽出の授業のサイトで知った論文。
http://acl.ldc.upenn.edu/W/W06/W06-1655.pdf (EMNLP 2006)
内容
普通のCRFでは表現されているがSemi-Markov CRFでは表現しづらい素性があることを指摘し、その素性の表現方法を示している。
- 情報抽出や単語区切りのようなセグメンテーション問題に適していると思われるSemi-Markov CRFだが、CRFに負けたという報告も少なくない。
- Semi-Markov CRFではsegment単位の素性（segmentの文字列が辞書にあるか、など）は表しやすいが、segment内のtoken単位の素性は表現しにくい。
- 特に、あるtokensの前後ではセグメントが切れにくいことを表す素性がSemi-Markov CRFでは表しにくい。これまでのSemi-Markov CRFを応用した実験では上記の素性が使われていない。
- 上記の素性は、中国語単語分割では未知語の解析に重要。
- 本質的にはSemi-Markov CRFはCRFを含んでいるので、token単位の素性も表現できることを示す。
- ナイーブに実装すると文長T に対してT３乗の計算時間になるところを、Dynamic Programming でT2乗に落とすアルゴリズムを提案。
- おまけで、generative modelの情報をlog oddsで素性としてCRFに取り入れる手法と合わせて評価。
- Semi-Markov CRFにtoken単位の素性を追加することで中国語単語分割のF値が 95.28から96.46に向上。
- CRF(95.69)にも勝利。
私見
- セグメンテーション問題のデファクトっぽく扱われているSemi-Markov CRFの弱点を指摘しており良い論文。
- ただ、改良方法の解析時間O(T^2)は厳しい。
- Semi-Markov CRFでしか使えないというsegment単位の情報は不完全ながらもCRFの素性に反映出来ないこともないのでCRFでいいような気もする。
Information Extraction: Machine Learning Approaches to Extracting Structured Information from Text
Javaの例外を起こすようなプログラムで、InterruptedException をキャッチしたときの処理の仕方について。
Javaの理論と実践：割り込み例外の処理
http://www-06.ibm.com/jp/developerworks/java/060616/j_j-jtp05236.shtml
例外が起きた時に即座にプログラムを止めたい場合には、以下のように現在のThreadに割り込みを行う。
catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
機械学習系の論文でも時々出てくるsupやinfについて説明しているページ。
http://www.nn.iij4u.or.jp/~hsat/techterm/sup.html
やわらかい感じで説明してあって、わかりやすい。
sup は上限と訳されるらしく、最大値の仲間。
xの範囲が0 <= x <= 1 の時のmaxは1だが、範囲 0 < x < 1の時にはx=１にはならないからmax=1とは言えない。
代わりにsup{0 < x < 1}=1と書くそうだ。
inf (infimum)は逆で、inf{0 < x < 1}=0。
例はWikipediaから引用。
NIPS 読む会で使われた、紹介資料が以下で公開されている。
http://sugiyama-www.cs.titech.ac.jp/T-PRIMAL/2007/NIPS2006seminar/index-jp.html
個人的には、杉山先生の紹介してくださった論文に注目。
二分探索で真ん中のインデックスを計算するときに、mid=(low+high)/2とやっていたがlowとかhighが大きな値だとオーバーフローしてしまうというはなし。
Official Google Research Blog: Extra, Extra - Read All About It:
Nearly All Binary Searches and Mergesorts are Broken
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
http://nais.to/~yto/clog/2006-06-09-2.html
より。
Javaだとmid = (low + high) >>> 1とすればOK。まったく気がついていなかった。
>>>は論理シフト演算子でシフトした左端には0を埋める。>>（算術シフト）だと最上位ビットが保持されるのでオーバーフローしたときは符号が逆転したままになってしまう。
Java のシフト演算子については以下が詳しい。
Unicodeを使ったクロスサイトスクリプティングなどの手法10個がまとめてある。
http://openmya.hacker.jp/hasegawa/public/20061209/momiji.html
Bidi(アラビア語などの逆から読む言語用)を使った拡張子の偽装は感心。
NIPS読む会が1/26(金)に東工大で開かれる。
NIPSの発表者の方も参加予定。
http://www23.atwiki.jp/ilcorgi-n-corgi/
に週末に行って来た。
ニンテンドーDSを展示ガイドとして貸してくれた。一部の作品（25位くらい）を音声で解説してくれる。
混んでいるので、作品の解説が読めなくても音声で聞けるのでなかなかよい。
タッチ画面で作品の前に来たら「ガイドを聞く」ボタンを押すのだが、理想的には画面なしで作品に近付いたら勝手に説明してくれた方が良い。画面で作品の拡大なども見られるのだが、目の前に絵があるのだから意味無い。
一方、座席で休んでいる人にとっては座りながら次に見に行く作品をブラウズできて良さそうだった。
