Hatena::ブログ(Diary)

ny23の日記 このページをアンテナに追加 RSSフィード

2010-07-29 他にも試してみた

Vowpal Wabbit 入れてみた

|  Vowpal Wabbit 入れてみたを含むブックマーク  Vowpal Wabbit 入れてみたのブックマークコメント

Vowpal Wabbit を試してみようと思ったが,MacPorts で入れた gcc 4.5 (gcc-mp-4.5) からだと io.h から string.h を,example.h から pthread.h を,さらに loss_function.h から stdlib.h を追加で include する必要があった.さらに,boost の program_options が必要なので,MacPorts 経由で boost をインストールして,Makefile を編集し,漸くコンパイルに成功した.なのに,実行すると malloc: *** error for object 0xa03066d8 ... が連打.なんなの.valgrind で調べたら boost が Apple gcc-4.0 でコンパイルされているせいっぽい.Apple gcc で vw を再コンパイルしたら動いたのだけど,ハイパーパラメタの調整の仕方がよく分からなかった・・・折角なので boost の program_options だけ自分でインストールして,gcc-mp-4.5 でもコンパイル・実行出来るようにしておいた.

これまで色々なライブラリを試してきて思ったのは.

  • 環境の違いを吸収するために configure / waf みたいのはやっぱりあった方がいい.
  • 外部ライブラリへの依存は最低限に.大量に使わないヘッダが入るライブラリ (例: boost) とか入れたくない.
  • デフォルト設定は慎重に,またパラメタ数は必要最低限に(人は選択肢が多いと選べなくなる)

しかし,ソフトウェアごとに terminology が違うのは何とかならないのか.epoch / iteration / pass とか.違う意味で使われたりするし・・・

[追記] 漸く使い方が分かった.キャッシュファイルを指定して学習データをバイナリで保存するようにしないと,繰り返し数が無視されるらしい.というわけで,学習率 [-l] と 繰り返し数 [--passes] を調整した結果を公開ページにを載せた.VW (SGD) は学習率周りのパラメタが多過ぎて [-l, --power_t, --initial_t, --decay_learning_rate],やや使いにくいかも.しかしながら,学習データをメモリに置かない徹底したオンライン志向の実装は好感が持てる.

2010-07-23 実験は疲れるなぁ

二値素性でのオンライン学習の実験まとめ

| 二値素性でのオンライン学習の実験まとめを含むブックマーク 二値素性でのオンライン学習の実験まとめのブックマークコメント

複数のオンライン学習のライブラリについて,線形学習と多項式カーネルの学習の詳細な実験結果(構文解析タスクと関係抽出タスク)を学習器の公開ページに追加した.今までの実験のまとめ的な内容になっている.オンライン学習は,訓練例を shuffling をするように統一して実験したら,ライブラリ間の速度差が少し縮まった.分類時間にはモデルの読み込み時間も入っているが,多項式カーネルではモデルの読み込みに時間がかかる分(と言っても100msec.とかだけど),特にテスト例数が少ない関係抽出タスクの実験セットで(線形学習に比べて)やや不利となっている.

幾つか分かったこと

  • PA-I は averaging すると,繰り返し数を固定した場合の C の最適値が変わって,より少ないサポートベクタ数で同程度以上の分類精度が出せる.SVM よりサポートベクタ数が多くなりがちな PA-I にとっては良い特性だと思われる.
  • averaged PA-I(繰り返し20回)と SVM が最高精度を競い合っている感じ.L1 正則化系の学習は大体精度が劣化する.有効素性数が減っても平均発火素性数が減るとは限らないので,分類は大して速くならないことが多い.L1 正則化を使わなくても,例えば省メモリでモデルを学習/テストする方法はあるしで,個人的には L1 正則化自体にあまりメリットを感じないのだけど.Representor Theorem によりカーネル化可能な L2 正則化だけでいいのではないかと.
  • CW は全然ダメ(特に構文解析タスクでは),AROW は少しましで,関係抽出タスクの方では Averaged Perceptron に勝っている.CW は訓練例にノイズが多くなると精度が劣化しやすいようだけど,よりアノテーションのノイズが多そうな関係抽出タスクの方で差が小さいのは不思議だ.共分散行列を対角に近似した実装のみと比較したのだけど,構文解析タスクでは素性間の依存関係が強いのでこの近似があまり良くないのかも知れない.しかし,素性数が多いドメインだと,そもそも近似しないとメモリ的に苦しくなりそうなので,実際に動かすには少し工夫が要りそうだなぁ.Transition-Based Parsing with Confidence-Weighted Classification でも同じような結果が出ているが,他言語では CW~SVM となっている.ただ,中の人に聞いた限りでは,SVM は学習が重いのであまりパラメタチューニング出来なかったと言っていたので,世の中の人が言うほど CW 万歳ではないのかもしれない.
  • 二値分類向けの最適化は大事.内積取るのに浮動小数点数の演算が入らなくなったり,カーネル関数の結果をキャッシュできたり,データサイズが減ってキャッシュが効きやすくなったりと,あちこちでボディブローのように効いてくる(学習器の場合,体感で2倍以上は差が出る).古典的な TinySVM が(載せてないけど)SVMlightLIBSVM より速いのは,二値素性向けの最適化が効いているからだと思う.
  • 線形学習だと,(昔言ったのと逆の言い方だけど)LIBLINEAR が精度の安定性や速度面で強過ぎて半端なオンライン学習を実装してもあまり意味が無いかも知れない(というか,オンライン学習を,単に高速な学習手法としてでなく,モデルの追加更新など,バッチ学習自体が出来ない状況で使っている人ってどれぐらいいるのだろうか).LIBLINEAR-poly2 の実験も入れようと思ったけど,素性数が多いデータでは,訓練データ中の素性番号を密にして,さらに配列の添字を 64bit に書き換えないといけなかったり(そして密にしても 16G とかメモリを食う)で取り敢えず棚上げ.CW の共分散行列の実装とも関係するけど,機械学習畑の人って,素性数が極端に少ないか,極端に多いか,二つの状況しか想定していないような気もするなぁ.
  • Averaged Perceptron はパラメタが繰り返し数のみで,かつ安定して動き,収束も速いので,一家に一台は持つべき.シンプルと言えば,Winnow とかもあるけど,どうなのかな.
  • 最後に.IO を侮るなかれ.アルゴリズムの計算量ばかりが頭にあると,痛い目に会う(会った).C++ で STL 使うなら,手元のコンパイラの実装ぐらいは,さらっと目を通しておいても良いと思う.

さて,と.次いくか.

[追記] LIBLINEAR-POLY2SVMlin を結果に追加した.LIBLINEAR-POLY2 は以前の結果とほぼ同様の結果.素性数が30万の訓練データでは動かなかった(400GBぐらいメモリがいるはずなので仕方ないが).SVMlin は LiBLINEAR の10倍程度遅いぐらいだけど,半教師あり学習などをサポートしているのは良い感じ.libcvm は Windows しかサポートせず(なんだそれ),と.

[追記] libarow を結果に追加した.モデルを保存しないでテストする割り切った仕様.分類結果を出力しないので,分類結果を利用したい人は少しハックする必要はあるけど,オンライン学習系のライブラリでは(今回自分が公開したもの以外では)一番速そうだ(というか,Random Feature Mixing が入っている関係で,モデルを保存すること自体が微妙という話も).素性番号の代わりに文字列を使えて,さらに Random Feature Mixing でメモリを節約できるのは使い勝手が良さそう.文字列→素性へのマップには,MurmurHash 2.0 を使っているようだ.ハッシュ値を引くのは速そうだけどハッシュ値が散らばり過ぎてキャッシュが効きにくくなるような気がする(以前自分のライブラリで試したときは FNV-1a に比べて遅くなった).

2010-07-21 一仕事終えた

学習器の実装を公開

| 学習器の実装を公開を含むブックマーク 学習器の実装を公開のブックマークコメント

8月末に発表する分類器の学習手法の実装をホームページで公開した.古くは Passive Aggressive - ny23の日記, Passive Aggressive と多項式カーネル - ny23の日記 ぐらいから書いていたもので, LIBLINEAR と oll - ny23の日記, Kernelized Passive Aggressive の微々たる高速化 - ny23の日記, AROW は CW より幾分マシか - ny23の日記, liblinear-poly2 - ny23の日記 ときて, 突然来た - ny23の日記 で出てきたアイデアを実装したもの.最近では, 文節区切り - ny23の日記 粗末な(素性とモデルで)単語分割 - ny23の日記 でも使っている.

オンライン学習で適当に書くとボトルネックになりがちな IO 周りの実装に気をつけて,二値素性に特化した最適化をしたからか,(特別なことは何もしてないが)線形学習でも oll より繰り返し部で2倍,IOを入れたトータルの学習時間で約10倍程度(これはややズル)高速.線形学習器としては最速レベルの liblinear 比でも,(同程度の精度を出すモデルの学習で)約2-3倍ほど速いようだ.まあ線形学習だと学習速度はこれ以上速くする必要はないかも知れず,どちらかというと分類が速いことの方が売りかもしれない(oll の10倍,liblinear の3倍高速).

本来の売りの多項式カーネルを用いたカーネル学習(正確には線形学習とのハイブリッド方式)の方は,訓練例を全てメモリに載せた場合でも,SVM と同程度以下のメモリ消費で約100-1000倍高速(二値素性のための最適化が入っている TinySVM 比の場合.SVMlightや libSVM だともう少し差は開く),PKI を使ったオンライン(カーネル)学習比でも約30-250倍高速.liblinear-poly2 みたいにやたらとメモリを食うこともないのがポイント.コードは相変わらず惨めなものだけど.

別に公開している解析器の方からも使えるようになっている.これで,別の学習ライブラリを入れなくても一通り解析できる.

レコード付き動的ダブル配列の実装も公開

| レコード付き動的ダブル配列の実装も公開を含むブックマーク レコード付き動的ダブル配列の実装も公開のブックマークコメント

以前 トライ(ダブル配列,簡潔データ構造)と STL コンテナ - ny23の日記で比較に使った自作のレコード付き動的ダブル配列 (dda) の実装も公開.以下の論文のアルゴリズムを実装したもの.

矢田晋, 田村雅浩, 森田和宏, 泓田正雄, 青江順一.ダブル配列による動的辞書の構成と評価, 情報処理学会第71回全国大会, 1-263-1-264頁, 2009年3月.

レコード付き動的ダブル配列 - ny23の日記から始まり, レコード付き動的ダブル配列 - ny23の日記, レコード付き動的ダブル配列 - ny23の日記, レコード付き動的ダブル配列 - ny23の日記 と二週間かかって書いた僅か360行の c++ ヘッダファイル.動的ダブル配列は上の分類器の学習手法で素性の重みの管理に使っているので,学習手法の実装に同梱した.std::tr1::unordered_map ベースのトライに比べると,分類器の学習速度・分類速度が2倍程度高速になる( レコード付き動的ダブル配列 - ny23の日記, やっと出たのか - ny23の日記).動的ダブル配列を使って Wikipedia のテキスト処理を高速化 - ny23の日記 でも使っているけど,上の比較にもあるように,TAIL を「うまく」実装しないとサイズ面では静的ダブル配列に比べて明らかに不利(それでも葉に近づくに従い分岐数が減るような普通のキー集合なら追加順序によらず darts よりはうまく詰めてくれる)なので,静的な辞書を構築するのには明らかに不向き.キーの動的な追加(+レコードの更新)の高速性を最優先した実装になっているので,トライをコンテナ的に使いたいときには有用.あと,int / uint / float など,4 bytes のデータなら(例外値を指定することで)何でもダブル配列内に保存できるようになっているのは便利かもしれない.

これで ソフトウェアの名前 - ny23の日記で書いてたプログラムは全部公開終了.この中では動的ダブル配列のコードが一番ましだと思う.やっていることは,最もややこしいので読むのは一番骨が折れるだろうけど.

2010-07-18 学会出張@スウェーデン7日目

成田スカイアクセス

| 成田スカイアクセスを含むブックマーク 成田スカイアクセスのブックマークコメント

朝着いたので昨日から走っている成田スカイアクセスに乗れるかと思ったら,近傍の数本は全て羽田空港行き,上野に行こうとすると青砥乗換になる模様.使えん・・・結局特急で帰って余計に疲れてしまった.モーニングライナーに間に合っていればなあ.

2010-07-17 学会出張@スウェーデン6日目

ウィーン経由で日本へ

| ウィーン経由で日本へを含むブックマーク ウィーン経由で日本へのブックマークコメント

疲れて日記を書く余裕が無いという・・・

2010-07-16 学会出張@スウェーデン6日目

イントロを先に書いてみた

| イントロを先に書いてみたを含むブックマーク イントロを先に書いてみたのブックマークコメント

学会期間中に,二つ三つ物になりそうなストーリーを思いついたので(詳細なアイデアではなく,科研費の申請書レベルの問題認識),タイトルを決めて,イントロを二段落まで書いてみた(取り組む問題の歴史的な位置付け・正当化に一段落,大雑把なアプローチに一段落).あと一つか二つ書いて,一番本質的な問題に近いものを元にしばらく仕事をしてみよう.

昔は申請書を一生懸命書いてお金をもらっても,一年,二年と時間が経つにつれ実際にやっていることと乖離が大きくなっていったものだった.もう若くないし,これからはもっと現実を意識して出口のはっきりした研究計画を立てたいと思う.

2010-07-15 学会出張@スウェーデン5日目

論文賞の選び方

| 論文賞の選び方を含むブックマーク 論文賞の選び方のブックマークコメント

今回参加した学会の論文賞を見ながら,論文賞はそもそもどう選ぶべきだろうと考えてみた.論文賞は本来,その学会で「最も優れた」論文に与えられるべきだが(例えば,査読のときに評価が高いものを候補として,PC 全体で候補の論文を確認する,あるいは,より多くの研究者の意見を取り入れたいのであれば,セッションごとに聴講者に良い発表を選んでもらってその意見を候補の選択・最終的な決定に反映する),論文賞を与えられた論文の影響を考えると,必ずしもそう単純ではないのかなと思った.

  • 受賞者にとっては,自分の研究に対する評価を意味するので(特に若手研究者や大事だが解くのが困難な問題に取り組む研究者に取って)今後研究を進める上での励みになる.
  • 非受賞者にとっては,いま「学会が考える良い論文」とは何か(学会が総体としての考える研究の価値観)を知る指針になる.

このうち,後者の影響は無視してはいけないような気がする.というのは,研究の良さには,その学会という「点」で考えて良いというだけでなく,研究分野の今後の発展にどう影響するか(評価項目で言うと Impact)というのもあり,論文賞を受賞した研究は(多くの研究者に注目されるため)さらに大きい Impact を持つことになる.そういう意味では,ある種応用の利かない天性的な発想や,局所的に大きく駒を進めた論文よりは,今回のように次に続くものが増えるべき萌芽的な研究が受賞しても良いと思う.

そして,上に列挙した二つのタイプの研究が必ずしも同一の研究になるとは限らないことを考慮すると,若手の研究者の向けの賞を用意するなど賞を増やして論文賞の位置付けをより明確にするのもありだと思う.この辺りについて,研究分野全体で同意が出来ていないと,何故この研究が論文賞を取れるのか(あるいは取れないのか)となるのかなと思った.

2010-07-14 学会出張@スウェーデン4日目

Business Meeting

| Business Meetingを含むブックマーク Business Meetingのブックマークコメント

「多様性は善」で論文の採録基準を調整した関係で,各分野の採択率のバラツキがやや大きくなっているようだったが,参加者はこの方向の改革に概ね賛成している模様.IR 系の論文を6本採択したが,2本は SIGIR に通って withdraw したそうな.その後,学会の査読を Journal-like にする話をしていたけど,採択数の調整をどうするかとか,出口は遠そうだった.

追悼スライド

| 追悼スライドを含むブックマーク 追悼スライドのブックマークコメント

第一著者の学生(正確には丁度 Ph.D. を取ったところ)が亡くなってしまい,共著の人が発表していたが,全体の8割ぐらいの時間で研究の発表を終えて残りの2割で追悼のスライドを流していた.学会会場は何だか少ししんみりしていた.

2010-07-13 学会出張@スウェーデン3日目

Banquet

| Banquetを含むブックマーク Banquetのブックマークコメント

連日30度を超す気温のせいか,本来丘の上にあって風が吹いて涼しいはずのバンケット会場が非常に暑かった.というか,人が密集し過ぎていた.そして,前菜が驚きの味だった.

2010-07-12 学会出張@スウェーデン2日目

だみだ,暑過ぎる − 実用と非実用の境界

| だみだ,暑過ぎる − 実用と非実用の境界を含むブックマーク だみだ,暑過ぎる − 実用と非実用の境界のブックマークコメント

聞いたセッションのまとめでも書こうと思っていたが,スウェーデン暑過ぎてだみだ.発表を聞いていて取り敢えず思ったこと(発散したのであとで書き直す).

  • 毎度のことだけど,精度の競争が盛んなタスクは(ノイズなどの関係もあって)理想的にどこまで上がるか分からないところを,良くみんな引き続きやれるなと感心する.タスクに対する一般的な改善になっているか,データ(全体)にオーバーフィットしてるだけか気にしていないとしたら幸せだと思う.数字だけに関心があって,「アプリケーションが要求する精度」を意識しないで研究を進めるのは個人的にはどうかと思うのだけど(ターゲットの精度は常に100%ではない),逆を返せば実用と結び付けなくても研究ができるところがこの分野の良さなのかも知れない.
  • 前ほどではないけど,発表がうまくないアジア人が目立つ.英語がどうこうというより,スライドの作り方が下手(話す内容を研ぎ澄まし切れておらず,一スライドが10行以上あったり,メインの主張に自信が持てないのか多数の主張を展開したがる).というか,研究の作り方のところまで遡ってうまくないのかもしれない.研究の目的関数がタスクの性能向上のみで,ベースの手法/モデルに改良を重ねるタイプの研究の仕方をして,結果が出てもシンプルなストーリーが作れなくて論文や発表の時に一言で内容を説明できなくて苦労する.つまり,手法/モデルを複雑にするタイプの研究が多い.逆に,非アジア人は,膨大なサーベイを元に,「論文やスライドをどう作るか」からスタートして(あるいは,自分の研究の位置付けを明確にしてから),複雑になった手法/モデルをどう単純なモデルとして昇華させるかを意識している感じがする(ある種研究の方法論として MDL 的な思想が背後にあるような).結果的にそういう論文の方がマイルストーン的に見えるので,引用件数は多くなる(研究という木で,葉を広げる研究をするか,新しい幹を作る研究をするか).この辺りは若手研究者と,経験を重ねた研究者との違いにも近い(年を取るほど,研究のスタイルは後者に移行する).葉を広げる研究でも,よく反芻しながら聞くと,研究の内容としては,むしろ綺麗にまとめた研究より面白い(新しい幹に繋がる話がある)のに,勿体無いと思う.とはいえ,実際のところ,これらの二つのタイプの研究は,相補的な存在でもあるので,今のままでもいいのかなとも思う.複雑化と単純化の繰り返しで世界は進む.
  • 上とも関係するけど,逆にモデルの見た目を単純化(あるいは「洗練」)することに拘って,線形オーダのアルゴリズムでほとんどうまく解ける問題で,僅かに精度向上させるために,学習やテストの計算オーダが大きく変わるほど重いモデルを使うのは理不尽だと思う.そういうモデルは,結局後々消えて無くなる.重いモデルを使って精度向上するのはある種当たり前.手法の費用対効果を意識して適切な手法を選択/考案する.データありきの研究分野でデータの性質に背を向けて研究するのは良くない.そういう人は,技術プロパーな会議で勝負すべき.
  • 去年はアジアで某国際会議と共催だったので,単独開催の今年の方が面白い発表が多いかと思ったけど,大して変わらない感じだ.ただ,論文の採否を決める段階で「多様性は善」的な観点が考慮されたらしく,絶滅しかかっていた研究分野や新興の研究分野,あるいは境界領域的な研究分野にセッションが確保されている.

工学的な側面も自然科学的な側面もある分野では,必ずしも実用を意識しなくてもいいけど,専門外の人に自分の研究をどう説明するかは,普段から意識したほうがいいと思う.誰かが作った既存の研究の流れに乗って研究を始めて,そもそもどうしてその研究をやっているのか本人が深く考えていないのは問題(そもそも論のできない研究者; 自分のやりたいことを実現するために本質的に解くべき問題を「放置」して,技巧的な手法に溺れて遊べるところで遊んでいたり).少なくとも日本ではそういうのは学生のうちにやめておかないと,あとで(自分の研究のディフェンスをしてくれる保護者の研究者がいなくなったときに)非常に苦労する.

多少論文が通りにくくても,新しいタスク(問題)を,その意義を議論するところから始めてデータ・評価基準(「良さ」を数値化する方法)を適切に定め,必要最低限に複雑な(逆に言うと,素直で単純な)手法/モデルをベースラインとして考えて評価する,というところまで通してやってみたら良いと思う.いかに自分が本質的に疑問に感じるべきところに背を向けて研究していたかが分かる.一度はイントロを自分だけの言葉で語れるような研究をしよう(偉い人が有用だと言っている的な excuse 無しで).

2010-07-11 学会出張@スウェーデン1日目

ウィーン国際空港

|  ウィーン国際空港を含むブックマーク  ウィーン国際空港のブックマークコメント

朝6時起きで,成田→ウィーン.オーストリア航空は座席が緑色で新鮮だけど,食事はメニューの案内もなく、味ももう一つ.(ルフトハンザは乗ったことがないが)ドイツを連想させる味気なさだ.シンガポール航空やコンチネンタル航空のようにデザートが出たりはしないが,その代わり,おにぎり or ミニチキンラーメンが途中で軽食として出た.接客は基本的に良いと思う(飲み物を頻繁に持ってきてくれる).

ウィーン国際空港は,無線LANが繋がり,便が良いと思う.あまりヨーロッパという感じがしなくて,なんだかアメリカに来ているような感じだけど.空港で3ユーロのバウチャーをもらったけど,この額ではスタバでカフェモカすら飲めない(今回はユーロを使う当てがないのでここで両替してもしょうがないし).乗換のゲート近辺は,壁に世界時計が100個以上かかっていてなかなか見ごたえがあった.ウィーン市内は空港から20分ほどのようなので,4時間ぐらい乗換時間があれば,世界遺産の街並をちょっと見るぐらいはできるかも.

ウプサラ着

| ウプサラ着を含むブックマーク ウプサラ着のブックマークコメント

夜8時前にストックホルム・アーランダ空港着.ウプサラ行きのバス (801) は少し前に出たところで,電車に乗ろうか迷ったが,乗り場のスカイシティまで遠そうだったので止めてバスにした(実際は近かったらしい).途中街らしき街もなく,約40分でウプサラ着.街は人気がなかったが,途中で見かけたスポーツバーには人が群がっていたので,ワールドカップの決勝に夢中というところか.ホテルでスーパーの場所を聞いて,プリングルス+スプライトを買った.夜9時過ぎにホテルにチェックイン.

学会出張でコーヒーを自挽

|  学会出張でコーヒーを自挽を含むブックマーク  学会出張でコーヒーを自挽のブックマークコメント

ホテルの部屋には湯沸かし器も冷蔵庫も無く軽く凹んだが,諦めず,ホテルの人に聞いてみたら,コーヒーメーカーで (tea) 用に熱湯を出せるから,それを使っていいとのこと.早速紙コップに汲んでいそいそと部屋に持って帰った.そして,ついに挽いて

f:id:ny23:20100711215055j:image

飲んだ.うまーい.手分量だったのと,あまりに嬉しくて持ってきたお湯を最後の一滴まで入れてしまったのとで,少し薄かったけど,飛行機で飲んだインスタント珈琲とは天地の差ですよ.今回珈琲を淹れるために持参したものは以下

  • ポーレックス・セラミックコーヒーミル
  • ユニフレーム・コーヒーバネット cute
  • ハリオ・v60用ペーパーフィルタ
  • スノーピーク・チタンシングルマグ 220ml フォールディングハンドル
  • 珈琲豆 (ブラジル 30g + 餞別に頂いた本日の珈琲 50g; 30g分はポーレックスの受け手に収納)

これらに MacBook や Lonely Planet Sweden,モレスキンや ER-4S + アンプ,下着類など旅行用品を含めて,普段使ってるアークテリクスのワンショルダーバッグ (quiver; 11L) に入った.珈琲器具の関係で,少しバッグがきつかったが,これから毎日挽いて飲めることを考えると,持ってきて本当に良かったなと思う.

2010-07-09 手抜き仕事

粗末な(素性とモデルで)単語分割

|  粗末な(素性とモデルで)単語分割を含むブックマーク  粗末な(素性とモデルで)単語分割のブックマークコメント

追記: 粗末な(素性とモデルを用いた)単語分割に辞書情報を入れてみた - ny23の日記 でもう一頑張りしてみました.

micterという単語分割器が公開されて,高速化もされたようなので,精度の方を追って見ることにした.と言っても,micter を使うわけではなく,手元にあった文節区切りのプログラム (c++で160行ぐらい) を少し書き換えただけ(文字分割は面倒なので最初から分割したファイルを入力).ラベルは,その位置から新しい単語が始まるか否か,素性は,分類対象の位置の前二文字 (pp, p) と後二文字 (n, nn) を一文字単位で入れて,多項式カーネルで n-gram を考慮(nn だけみたいな skip n-gram も考慮される).学習・テストは文節区切りの時も使った標準的なセットを使用(訓練例 1,029,654).PA-I は C=1.0,0.5,0.1,0.05,0.01,0.005,0.001, iter=20, shuffling + averaging; 素性ベクトルの長さ以下の d だけ試した.

素性は n だけから始めて精度の最も上がったものを greedy に追加
d |      n    |    p,n    | pp,p,n    | pp,p,n,nn | + ctype   |
--------------------------------------------------|-----------|
1 |  79.839%  |  91.310%  |  93.016%  |  93.667%  |  93.751%  |
2 |    NA     |  97.081%  |  98.430%  |  98.705%  |  98.715%  |
3 |    NA     |    NA     |  98.507%  |  98.805%  |  98.849%  |
baseline: 58.162% (全部切った場合)

学習は一番遅いモデルで約20秒,文字面しか使っていない割に,意外と良い精度だ.高頻度の単語は文字列として短い場合が多いので,辞書なしでも学習データのみでトークンとしては大体カバーされるのだろう.文節区切りと同じで,前後の単語のラベル(単語がその位置で切れてるか切れてないか)は分類に寄与しなさそうなので,見えてる情報だけ使って決定的に区切っても精度にはあまり影響なさそうだ.区切り位置の両側二文字を見れば大体解ける問題ということか.まあ,`すもももももももものうち' をみたいなのはダメだけど.

[追記]字種 (ctype; 平仮名,カタカナ,漢字,アルファベット,記号,数字) を素性に足したけど,上げ止まっている感じ.

学生セッションのコメンテータ

| 学生セッションのコメンテータを含むブックマーク 学生セッションのコメンテータのブックマークコメント

帰ったら,明後日から行く学会の学生セッションのコメンテータの依頼のメールが来てた(参加者にはみんな来てそうだが).6年前は自分も発表してコメントしてもらったし,やってもいいかな.まだ13本も担当者が決まってないみたいだけど,大丈夫かな.

2010-07-08 一通り終了

キナ臭さが漂うオンライン登録(でも中の人は親切)

|  キナ臭さが漂うオンライン登録(でも中の人は親切)を含むブックマーク  キナ臭さが漂うオンライン登録(でも中の人は親切)のブックマークコメント

飛行機のチケットの支払いが終わったので,学会の参加登録の支払いをしようと,オンライン登録のサイトでカード情報を入れて submit した.7/10 以降に confirmation が来るみたいだけど,すぐ来ないと不安だ.というか色々な意味で今回のオンラインでの参加登録は不安を煽る仕上げになっている.

  • オンライン登録サイトの対応 OS が MS 2000/XP/Vista,さらにブラウザが MSIE 6.0 以上のみ対応とある.Mac OS 10.6 + firefox の自分はどうしろと.Firefox では,カード情報の submit はできず,結局 Safari で登録(したことになってるのかどうかよく分からないが)
  • ユーザ情報のページのフォームが,再ログインすると空(初回登録時に一応 confirmation は来る)
  • 参加登録についての連絡先が,gmail.これはまだしも,リンクをコピーすると .cn のアドレスになっている.
  • 学会の推奨ホテルをネットで検索したら,ボロクソに貶されていた.
  • ちなみに,オンラインのカード支払いについては,`If you choose on-line credit card payment, you should do it at your own risk.' 洒落になりません.
  • そして 7/2 締切りのカメラレディ原稿の投稿サイトがまだ開いている.

採録されたところからフィッシングだったらウケるな.結局,Windows XP/Parallel + MSIE 6.0 で再度試したら,あちこちで XML エラーを吐きながらポップアップウィンドウが出て,`do it at your own risk' で支払いができましたよと(Safari ではポップアップがブロックされているのに気づかず,結局払えていなかった; 一応 https).怖いな.

[追記]参加登録についての連絡先は,gmail の方に送ったメールに返事が来た.それによれば,無料でネットに接続できるのは,三番目のホテルだけだそうで,他は外れ(より宿泊料金の高い2件は有料; 一日 120 CNY/day (3 CNY/min.) と 60 CNY/day (10 CNY/hour); 一番宿泊料金の安いホテルは部屋にネット接続なしとのこと).当たりを引いて良かった.チュートリアルの午後は2時から開始なので,午後のみの参加であれば,羽田発朝便で間に合うようだ.100%の保証はしないけど,参考まで.

confirmation が来なかったので,break down list くださいというついでに,メールを送ってみたら,領収証も送ってくれた.前言撤回.一見怖そうな顔をしていても,中の人はいい人だった.ありがとうと返信したら,どういたしましての返信まで来た.

ちなみに.カメラレディ原稿の投稿サイトは,「投稿した論文がフォーマットの要件を満たしていない」と連絡を受けた人が(直して)再投稿するために開いていたらしい.

2010-07-07 挽くに挽かれぬとはこのことか

ここは挽くしか無い

| ここは挽くしか無いを含むブックマーク ここは挽くしか無いのブックマークコメント

いつも豆と珈琲を買っている大月珈琲店で,来週は北欧に行って現地で豆を挽きます!と言ったら,サービスで本日のコーヒーの豆を50g頂いた.これはもう,挽くしか無いですね.

[追記] 結局チタンカップは,スノーピーク チタンシングルマグ 220ml フォールディングハンドルを amazon で注文.

2010-07-06 もうやばい

北京行きの航空券

| 北京行きの航空券を含むブックマーク 北京行きの航空券のブックマークコメント

H.I.S. の人から2ヶ月前には予約したほうがいいと言われていたけど,カメラレディでしばらく忙しかったため動けず,今日ようやく問い合せてみた.既に結構席は無くなっていて,スウェーデンに行く前に全て済ませた方が良さそう.アジアぐらい近いと,航空会社の選択肢が少ない関係で逆にすぐ埋まってしまうのではないかと思った.乗換する距離ではないし(乗換も,アシアナ航空ぐらいしか無い),直通だとANA/JAL の日系か,中国系航空会社に限られる.

学会の本大会が5日,前後にワークショップとチュートリアルがあるので,全部出ると,8泊9日の長丁場になってしまう.うーむ,困った.初日のチュートリアルを午後だけ出て,最終日のワークショップを早めに切り上げようかと思ったが,日系は帰りの便で遅い時間のものが無いようだ(時差の関係で,当日着だと帰りはあまり遅い便がない).中国系はあるようだけど,躊躇われるなぁ・・・うーむ,困った.

北欧に行く前に予約せねばと H.I.S. で ANA の便を予約.行きは羽田からチュートリアルの日の朝に羽田から出る便に,帰りはワークショップの翌日昼過ぎに出る便にした.7/17 から新型スカイライナー出るらしく,それだと羽田でも成田でも往路の時間に大きな差はないようだ.7/17 なら,北欧の学会の帰りにも乗れるかな・・・と思ったら,時刻表を見る限り,ちょっと厳しい感じ.

2010-07-03 非公開な公開

開催前の学会の Proceedings (CDROM) を眺める

|  開催前の学会の Proceedings (CDROM) を眺めるを含むブックマーク  開催前の学会の Proceedings (CDROM) を眺めるのブックマークコメント

同僚氏に,11日から行くスウェーデンの学会の Proceedings (CDROM版) が Google に既にインデクスされていると教えてもらった.さらに検索すると,6月10日に,あるブログから CDROM の PDF に直リンクされているのを発見.こんなに早く,よく見つけたなー.これぐらい早く公開してくれるとのんびり読んでから聴講できるので良いですね.

2010-07-02 忘れてたわけじゃないが

カメラレディ原稿締切り+学会参加登録締切

| カメラレディ原稿締切り+学会参加登録締切を含むブックマーク カメラレディ原稿締切り+学会参加登録締切のブックマークコメント

もっと強いベースラインと比較して欲しいと言われたので実験をしていたが,終わったのでグラフを二つ追加した.なんか順番が逆なような気もしたが,参加登録終わった.中国は,ビザいるんだっけ?

[追記: 7/3; 03:15] 取り敢えず寝る前に出しとこうと思ったが,参考文献が一件はみ出ている・・・困ったな.

[追記: 7/3; 06:35] 出した.もう直す気力なし.

[追記: 7/3; 11:05] 学習曲線でデータサイズを2倍ごとにプロットしてるの(スカスカで)気になるな・・・√2倍ごとにした.

[追記: 7/3; 19:45] 18:00 頃更に直したが,直せば直すほどもっと直したくなる不思議タイムに突入したので,家族の顔を見ることで心を落ち着かせて直すの辞めた(イントロ一段落書き直そうとしてた).

[追記: 7/3; 21:00] 銀河高原ビールのペールエールサーモスの真空断熱タンブラーで飲んだ.香ばしい,冷たい,うまーい.わーい.忘れないうちにホームページにも上げておいた.

[追記: 7/4; 12:30] まだ投稿サイトが開いてたので,概要と,結論を大幅に書き直して,投稿.

次は学習器のオープンソース化.

2010-07-01 やむを得ず部分的に非公開に・・・しないでいいのか

オープンソースとアルゴリズムの特許

| オープンソースとアルゴリズムの特許を含むブックマーク オープンソースとアルゴリズムの特許のブックマークコメント

GPL で公開していた構文解析ライブラリで実装していたアルゴリズム(の一つ)について,特許が出ているという指摘を受けたので,GPL で公開するのは不適切だと判断して,当該アルゴリズムの実装を取り除いた.このアルゴリズムは,同じくオープンソースな解析器 (LGPL/BSD) でも実装され公開されていたので,すっかり ok だと油断していた.確かに企業研究者の提案手法なので,特許が取られている可能性は頭の隅にはあったのだけど,それにつけても非常に残念だ.今回のアルゴリズムは,かんたん特許検索で提案者名を入れてもそれこそ「かんたんに」出てくるので,自分自身の過失だろう.が,それで済ませていいのだろうか.[最後にオチあり]

以前, Bayesian Setsの特許について - のんびり読書日記 を読んだ時も思ったけど,アルゴリズム(あるいはソフトウェア)の特許というのは,オープンソース開発者にとっては極めて厄介な問題だ.自分自身は,企業研究者が特許を取るのは企業の利益を守るという観点でも十分理解できるし,企業研究者の間では,新しいアルゴリズムを開発する動機付けにもなるので,反対ではない.ただ,アカデミアの研究者としては,自分の提案手法を制限なく利用してもらうため,実装を公開したいというのもあって,(それと相反する)特許を取らないようにしようと思っている.自分は学生ではなく雇用されている立場の人間なので,自分の判断だけで実装を公開するわけにはいかないのだけど,今のところは問題なく(スムーズに)公開できている.

難しいのは,今回のように,他人の提案したアルゴリズムを実装して公開する場合.Bayesian Set を実装した人のケースは公開差し止めを求めるだけだったみたいだけど,特許を知らずにオープンソースで公開して特許取得者に不利益が出た場合(第三者に商用利用された場合とか)はどうなるのだろう.GPL で公開するということ自体が不適切だったわけなので,何がしかの責任が発生するような気がする(というか,特許の専門家が周りにいない現状では,「どうなるのか分からない」というのが本当の問題; 安易に公開できなくなる).手法を提案した研究者自身が実装をオープンソースで公開している場合は,まず再実装して公開しても問題ないと思うが(厳密にはライセンス依存だが),そうでない場合は公開前に特許の確認をした方が良いのだろうか?特許の専門家が周りにいない立場の人間が完璧なチェックをするのはちょっと無理だと思う.

そういうことを意識し出すと,他人の提案するアルゴリズムの実装をどんどん公開する(失うもののない)若い人(主に学生)は羨ましいと思う.自分も学生の時は「怒られたら引っ込めればいいや」的な気分が大なり小なりあったが,今は守らなければいけないものもあり,リスクを冒すことは難しくなっている(というか,より責任を意識する).自分としては,彼らの行動にはむしろ賛成で,萎縮しないでどんどん公開したらいいと思うけど,彼らを「守る」には,自分たち(アカデミアの研究者で,学生の行動に責任を持つ立場の人達)はどうしたらいいのだろうか.研究者の場合,基本的に論文でアルゴリズムを知って実装する場合がほとんどなので,特許取得者(多くの場合,論文の著者)が「この論文のアルゴリズムは特許申請中である」という事実を,もっとオープンにしてくれたらな,と思うのだけど(特許自体は,そもそも第三者に何が特許申請されているか分かりやすくあるべきだし,サブマリン特許的に罠にはめようと思っている企業研究者(職務発明規定の関係で,出願者は多くの場合企業なので,トンデモ会社ならあるかも)はほとんどいないだろうから,もっと論文と特許の関係を明確にしてくれたらなと思う; 論文中に特許出願中と書くとか).実際,網羅的にオープンソース開発者が特許を確認するというのは難しいのが現状だ.論文で提案されているアルゴリズムが patent-free か patent-protected かもう少し簡単に知る方法は無いのだろうか.今のところ,論文の著者に直接聞く以外には思いつかないなぁ.

話は変わるが,この件を同僚氏に話したら,Viterbi アルゴリズムと特許の話を教えてくれた.Viterbi 自身は Viterbi アルゴリズムに特許を取らなかったが,それで良かったと思っているという話.興味がある人は Andrew Viterbi Oral History を patent で検索して見て欲しい.大学研究者としては,アルゴリズムの特許を取ること自体に反対も賛成もしないが,特許を取った方が良い場合(あるいは取っても良い場合)と,良くない場合というのがあるように感じている.あまりいい例えではないかも知れないが,優れた基礎的なアルゴリズムというのは科学哲学でいうところのパラダイム(教科書)の様なもので,しばらくの間は研究者はその上で背伸びをしないといけないので,早い段階でそこに特許のフタをしてしまうと研究の発展が阻害される場合があると思う(そして必ずしも代替案が見つかるとは限らない; CKY も Earley パーザも dynamic programming であることは変わりない).

一方で,オープンソース開発者としては,アルゴリズムに貼られた特許のラベルは Google が表示させる広告のようなものだと思っている.

「ある種の代償として必要であることは分かっているが,なるべく見ないで済ませたい」

参考リンク

[追記; 7/2]

アルゴリズムの考案者発明人(=発明の出願者; 出願人は所属企業)に直接問い合わせてみた.当該発明は公開後,審査請求されておらず,取下げになっているとのこと.特許電子図書館公報テキスト検索で特開番号などを指定して検索結果のリンクをたどると,経過情報が見られて,確かにみなし取下げになっている.特許権を取るための手続を見ると

5)みなし取り下げ(審査請求期間内に審査請求なし)

出願から3年以内に審査請求のない出願は、取り下げられたものとみなされます。以後権利化することはできませんのでご注意下さい。

とあり,特許化はできなくなっている模様.というか,論文の発表より特許の出願の方が容易なので,出願・公開だけして(維持にお金がかかる取得はせず)他社に特許を取られるのを防止するというのが主目的なのかな.なるほど,こういう利用法なら,上に書いた記載は少し言い過ぎだったかも.というわけで,オープンソース化は問題なさそうなので再公開しました.

今回は運良く出願から3年以上たってみなし取り下げになっていたから良かったが,出願から3年以内であれば審査請求をする場合もあるわけで,「論文を見てすぐアルゴリズムを実装して公開する」ことにリスクがあることには変わりがないか.3年というのは,技術の陳腐化との兼合いで,他企業が公開技術を利用するのを(一定期間)防ぐという意味合いなのかな(公開技術を使って他企業が商売を始めたら,審査請求→取得することで利益を守れる; 3年間で技術が陳腐化していなければ(その後も独占的に技術を使いたければ),審査請求・取得すれば良い).