« June 2008 | Main | August 2008 »

2008.07.24

富士登山

#研究以外のことは最近mixiに書いてますが、山の体験は是非みなさんに知ってもらいたいのでこちらに書きます。

先週の連休、友人達と富士山に登ってきました。
私にとって数年前にいった北アルプスの奥穂高、北穂高に続いて3つ目の山です。

登頂前日まで:
最近運動らしいものを全くしてなく、やばいということで、可能な限り夜中(3時とか)走ってました。山グッズは、以前使ったものがあったので大体そろってました。あとはググって富士登山について調べたり。
今回は散財しサプリメント系を気合い入れてそろえました。以前登った時にアミノバイタルが非常に効いた記憶があったので。

初日:
新宿集合。バッテリーとかをヨドバシカメラで買い揃える。この時買った8GのSDカードが結局手持ちのカメラで使えない。無念。飯買って、高速バスに乗る。中央道が大変混んでるらしいということで萎える。

予想通り高速が混んでいたが、普段の寝不足解消ということでものすごい勢いで寝る。昼過ぎになると、さすがに寝飽きたので、買いっぱなしだったCDを片っ端から効き始める。椎名林檎のアルバム未収録を集めたやつとか、GReeeeN!とか。テンションがすごい上がるが全然着かない。

バスが山を登り始めると、違法駐車と駐車場待ちの自動車の列で全く動かない。道の途中で片側車線とかになっていたらしい。山っぽい雰囲気なのに、ずっと待つ。

3時ちょい前に河口湖五合目到着。既に一人着いているはずなのだが、待ち合わせに設定していた大草履が全く見つからない。まぁいいかということで準備体操などを始めていて、ぶらぶら歩いていたらメンバー発見。
しばらくしたら名古屋組も到着。7名全員そろう。五合目は高速のパーキングエリアみたいな感じで何でもある。これから登ろうという人と下山してぐったりしている人が入り乱れて異様な雰囲気。外国人なども多い。

Dsc_0002


五合目では1時間ほど体を慣らさないと高山病になるとの教えを忠実に守り、ぶらぶらする。準備運動などして、出発

最初はゆるい登り坂と下り坂が続く。最初に長いくだり坂で、「帰りにこれはきつい坂になるのかなぁ」と話していたが、予想通り帰りではトドメを刺されることになる。

六合目に到着。ここはまだ森の中の雰囲気。ここらあたりまでは馬に乗ってくることもできるそう。

登った後に知ったのだが、五合目とかは六合目とかは、標高とかに関係なく適当につけているらしい。

さて、六合目からはジグザグの長い坂道が続く。マリオとかのアスレチック面みたいな感じで、でかいブロックが壁になっている。

Dsc_0020

このへんからもうすごい人の量で行列がずらーっと並ぶ。前の人について、ひたすら坂を上り続ける。
しばらくすると、山小屋が見えてくる。このあたりからは30分ほど登ったらすぐ山小屋について、その前を通って、脇からまた山を登るというのが続く。岩場で結構段差とかがあって激しい。

Dsc_0037

いくつかの山小屋を過ぎた当たりから日が落ちて周りが暗くなってくる(登り初めて4時間ぐらい?)一応人がまだ多く、前と後ろに山小屋が見えるので、真っ暗な夜の山という感じではないが、寒いし大変。持ってきたお菓子とか(特に氷砂糖がよかった)、水をひたすら飲んで登る。食料などは山小屋で買えるので、そんなに困らない。

足が疲労のため動かなく、ゆっくりしか登れない人がでてきて、自分も高山病なのか頭がちょっとずつ痛くなっていた。
予定では7時ぐらいまでには宿泊予定の御来光館という旅館に着たかったが、全然着かない。八合目について、そろそろかと思いきや、八合目の次に本八合目というのがあると知り愕然。さらに泊まる予定の御来光館はそのさらに上(3450m)にあるという事実。買い物はできるが、どこの山小屋も宿泊客で中で休むこともできない。とにかく根性で登り続ける。

最終的に御来光館に到着したのは10時前ぐらい頃。
昼飯軽くしか食べていなかったので、すごくお腹が空いていた。予想通り晩ご飯はカレー。うまかったが、疲労のため消化されなかった。
10:30には消灯。とは言え、外を歩いている人は結構いるし、山小屋に入ってくる人はどんどんいるし、外からわけの分からんフランス語とか英語とかは聞こえるしということで、ゆっくり眠れる感じではない。横になって休める感じ。

ちょっとだけ眠れたかもしれないが、このあたりから高山病がひどくなってくる。ひどい頭痛と吐き気。以前山に登った時も高山病みたいな症状が少し出たが、今回ほどではなかった。布団の中で横になるのもつらくなり、暖炉のあたりで温まる。他の登山者の人も同じような症状で苦しんでいる。とにかく救いを求めて酸素ボンベをひたすら吸っていたが症状はよくならない。ぐったりする。

二日目:
そうこうしているうちに午前1時30頃になり、山小屋の中はみんな起き始める。外を見ると道沿いに下の方から上の方までライトの列で、すごい人の数。山小屋の周りも賑やかになってきた。2時頃予定通り出発。高山病と思われる症状はひどいが、ここまで来たら下るのは難しい。登るしかない。

幸いなことに動きはじめたら、高山病の症状が楽になった。高山病は酸素が薄い高地で酸欠のために引き起こされるらしいのだが、運動し始めて呼吸量が増え、体も温まったから楽になったのだろうか。

相変わらず人の数がすごく、渋滞。ツアー客も多くそういう人たちが待っているせいでより混んでいる。ちょっと登っては止まるという繰り返し。体調が万全でないから、これぐらいがちょうどよかったのだが。

3時ぐらいになってくると地平線が段々オレンジ色になってきた。この時点でも、まだ頂上らしき光は遥か遠く。延々と岩場を登っていく。道沿いには、くたびれた人がそこら中に横になっている。夜通し登る人も多いみたいだが、相当厳しそう。

自分は酸素を吸いながら登る。4時ぐらいになってくるとそろそろ日が出るのではということで周りの動きも速くなる。一応このルートではどこからでも日の出は見ることができるのだが、やはり頂上から眺めたい。最後の力を振り絞り登っていくと鳥居が見えてきた。なんども鳥居には騙されていたので、今度こそ騙されない思っていたが、ここが頂上だった。

ぎりぎり間に合い、頂上で日の出を迎える。日の出はとても感動的ですばらしいものだった。泣きそうになった。
日の出に合わせ、放送で君が代が流れ、山小屋の主人の音頭でみんなで万歳三唱をした。

Dsc_0065

疲労と高山病で体調がよくない人も多く、その後山小屋で800円の豚汁を食べながら休む。ここでお鉢巡りをするグループとそのまま先に下山するグループに分かれる。

お鉢巡りとは、富士山の火口の周りをぐるっと回ることで所要時間1時間ぐらいかかる。そして、最高地点の剣ヶ峯がちょうど登頂した河口湖側の反対側で、是非そこは登らないといういけないということで向かう。

空気も薄いし、疲労も大きいが、気分が高揚しているので、よくわからないうちに剣ヶ峯の下の到着。この峰に上る坂道が非常に急でとてもきつい。時間をかけてゆっくり登った。最高地点は観測所のすぐ隣にある。観測所の展望台からは(おそらく)日本アルプスが一望に見えて絶景。この後、アップダウンを繰り返し、お鉢巡りの出発地点に無事戻る。

ちょっと休んでから下山を開始する。

正直自分は、下山をなめていた。前回登った北アルプスとかは下山は比較的楽だった記憶があるのだが、富士山の場合は砂走りという、岩と砂が混じったような急な坂道をジグザグにひたすら下る。
この岩と砂が混じった坂道というのは最初はザザーとすべりながら降りるので楽しいかなと思っているのだが、しばらくするとすぐに足の先の方が痛くなり、体が支えられずずずずと降りるようになる。もうヘトヘトでつらいというところから大体30倍ぐらい続く。下を見ると延々と続いている。界王様に会いに行く蛇の道のような感じだ。途中にトイレがあり、それが終わりに近いらしいという情報を頼りに、遥かかなたに見える小さい屋根を目指し降りていく。しかし、着いたと思ったらそこは緊急避難用シェルターでトイレではない。周りには同じように落胆した表情の登山者達がぐったりしている。

その後も下り続く。勢いよく降りてみると、それはそれで足の爪がはがれそうになり断念。だんだんあきらめの境地になり無我になったころ、ようやく砂走りが終わる。この後はゆるやかな下り坂を行く。とはいえ、砂走りで完全にくたびれた体にはこのゆるやかな坂道もつらい。思考能力も無くなり、最後はみんなで、5文字しりとりをしていたが、それも自然消滅。

最初に通った緩やかな坂道を登り、濃い霧の中無事下山。

五合目で飯をかるーく食って、こけももソフトを食ってバスで下山し、山中湖付近の温泉に入り、少し寝た後、中央本線で帰宅。

--
感想。

とてもよい経験だった。富士山は一生のうち一度は登っておくことをお薦めします!
北アルプスとかと比べ岩と砂が多く大変かもしれませんが、人も多く、お祭りって感じがします。

ただ、結構準備したつもりだったが、それでもかなりきつかった。
アミノバイタルがとても効いたらしく、筋肉痛はほとんどなかった。
酸素ボンベをケチらず大きめのを用意してもっと速めに多く摂取してれば高山病はもうちょっと防げたかなぁと。

写真は一緒に行った方のをお借りしました。

| | Comments (2) | TrackBack (0)

2008.07.18

機械学習のチュートリアル (ICML2008)

今年のICML2008はUAIとCOLTの共催と大規模で行なわれたようです。いろいろな方の話を伺うと楽しかったようで。

私は適当にお勧めされた論文やらを読み漁ってます。
個人的に印象深かったのはいくつかのmulti-armed bandit problemの話かな。特にこれとか。

bandit problemは強化学習の中にでてくるような問題の一つで、元々は複数のスロットマシンがあって、これから収益を最大化したいという問題。この時、やらなければいけないことは、現在持っている結果を元に各スロットのモデルを予想するとともに、自分からちょっとリスクを冒してでも他のスロットを試しにいかないといけない。スロットAが今のところ調子いいんだけど、もしかしたらさっきは出なかったスロットBの方がすごい調子がいいかもしれない。探索と最適化がまざったような話ですね。
コンピュータ囲碁で今一番強いモンテカルロ法とかでもでてきます。

実際世の中でもこういうmulti-armed bandit問題のケースが非常に多くでてきます。上の論文で熱かった問題は、マルチクラス問題のオンライン学習だけど、間違えた場合に正解はなんだったかを教えてもらえないケース。つまり当たっているかどうかだけが教えてもらえる。例えば検索システムでは、実際に表示した中でクリック率で検索結果が当たっているかどうかは分かるけど、クリックされなかった場合にユーザーから正解を教えてもらえるわけではない。残りの候補1万件の中にもっといいやつがあるかもしれないけどユーザーは教えてくれない。

こういう場合は下位の方のやつも試しに表示させてみて、クリック率はどうかなということを調べるが必要があるわけです。上の論文では一般的なマルチクラスのオンライン学習の枠組みの中で一定の確率でランダムに他のやつを見せるという、かなり荒っぽい方法でも、かなり速く学習することもできて、実験結果もかなりいいみたいです。すばらしい。

ICMLはチュートリアルも充実していて、多くが丸ごとスライドダウンロードできるし、そのうちビデオもここで公開されるでしょう(もうされてる?)

個人的に興味深かったのは劣モジュラを使った機械学習。連続的なパラメタを扱う場合は何とかして凸最適化問題にして効率的に解こうという話がありますが、離散的な話(例えば素性選択でN個の中からk個選びましょとか)には、こうした性質がなく一般的にNP完全になってしまいます。
しかし最適化したい問題に劣モジュラ性がある場合は、凸最適化のように効率よくとけることが知られています。効率よくといってもn^8とかすごいオーダーなんですが、greedyに解いてもこれだけの保障がありますよとかがあって、うまく利用すると一見すると全探しなければならなそうな場合でも、効率的に解くことができます。このへんは私が授業で教わった室田先生岩田先生など日本人もとても強い分野で、和書もいろいろあります。

もう一つは、最近私もOLLというライブラリを作ってみましたが、そのオンライン学習に関するチュートリアル
もともと解きたい(最適化したい)問題をSVMのように双対問題にして各訓練事例にパラメーターがつくようにして、その最急降下法という形で解いているのだという形でオンライン学習に落とします。で、いろいろな損失関数(例えばmax-marginだけではなくlogistic回帰とかも)とか最適化戦略とかできてということを紹介してます。この辺はまだまだやるところがいくらでもありそうですね。

| | Comments (2385) | TrackBack (0)

2008.07.17

自然言語処理の話

先日、自然言語処理はどのように役に立つのかというので酒の席で討論になりました。

自然言語処理とは、人が日常的に使っている自然言語(コンピュータ言語との対比でそうなってるらしく、日本語とか英語とか)をコンピュータに処理させる技術で、様々な技術と問題が融合する境界領域です。純粋な言語理論だけではなく、人工知能やら統計やら何でもまじってます。広義だと情報検索(の基盤といったほうがいいかな)とかも含まれます。

絵とか動画がいくらリッチな情報だとは言え、「昨日私がクーラーかけっぱなしのまま、裸で寝てしまい風邪をひいた」ということを言語情報無しで正確に伝えるのは難しいです。世の中の殆どの情報は自然言語で表されています。

で、自然言語処理が抱える宿命として、人にやらせると、言語処理は、ほぼ100%できてしまうということがあります。難しくないのです。

これは他の学問ではあまり見られないことで、例えば300kmで走る車を作るというと明らかに人間の能力より進んでいるという意味ですごいなって感じがしますが、このメールはスパムかどうかというのを判定させるのだったら人にやらせれば100%できるのに自然言語処理とかだと98%とかしかいきません。(唯一超えるかなというので機械翻訳とかがありますが、それはまた)

となると、自然言語処理は学問的には、人間の言語がどのような仕組みで動くのか、知能とは何かというのを解明するという意味で面白くすごく重要だと思いますが(赤ちゃんがなぜ恐ろしい速さで正例だけ与えて学習できて、年とると言語の習得が急激に難しくなるか。そもそも文法とは何かということとか)、実用的には人が既にできているものをやってどうするのということになります。

これはとても不思議なことで、人はどう言語を処理しているのか自分では分からないが、読み書きできて話して聞けて言語を使って考えることができるのです。

どのようにやってるのかわからないので、コンピュータにやらせようとすると途端に難しくなります(そういう意味で訓練データを与えて学習する機械学習と自然言語処理は相性がよかったのかも。訓練データは人が作り放題)

なので、デモとか見せても、「ほう」、「で?」ということになります。高校生とかに見せる発表会とかは地味なものです。個人的には係り受け解析や固有表現抽出の精度が数%あがった、すごいー!って思っていても受けが悪かったりします。悪いだけでなく笑われたり怒られたりします(ルーウェリン反応というのもある)。それはそれで正しい反応だと思います。

自然言語処理の実用的なすごさはスケーラビリティと低コストにあると思っています。

例えば、情報検索が一番分かりやすい例かもしれませんが、全ての文書を読まなくても全世界の文書の中から欲しい情報を見つけてくれます。これはインターネット、コンピュータ、自然言語処理が無かった時代と比べると大きな違いです。人間は限界があります。10人でweb上の全部の人名探すぞといって、ある程度うまくいったから、これを10万人に増やしてやろうとなると、これはなかなか難しいことですが、いい自然言語処理器があればコンピュータさえ増やせばできます。

世界最初のコンピュータが稼動してから数ヶ月で、それまで人類が誕生してから行なった全ての計算より多くの計算を行なったように、手元のパソコンはわずか数時間でその人が一生のうちに触れられる多くの言語情報を処理することができます。

しかも圧倒的に安いコストでできます。サービスとかでは違法系の書き込み削除にすごいコストがかかってますが(某大手サービスとかは数百人とかが常時待機)、これを全てとは言わなくても大部分排除できます。

余り、注目されていませんが、adsenseなどの記事連動型広告が動いている技術は情報検索技術並にすごいと思います。低コストで大量の広告をページ内の言語情報を解析して正確にマッチングさせ莫大な収益を生んでるのは今まででは考えられないことです。

人間ができて当たり前のことを、機械ができたら、ずいぶん違います。

もちろん人手に任せた方がいい部分もすごくたくさんあるし、それらを活用することでもっと面白いことができると思います。個人的にはニコニコ動画の市場の商品チョイスとかはいつも気が利いてるなと思うし、はてなキーワードとかをクローリングすれば最新のブログからキーワード抽出を頑張ってやるよりも遥かに質がよく新鮮なキーワードが手に入ります。基本的に人がやって楽しいことは人手でやらせた方がいいでしょう。

これをどう使ったら、みんなが幸せになれるかは使いどころですが、まだ試行錯誤中。
日々精進。

個人的には機械翻訳とかやはり夢ですかね。まだまだ先は長い。一歩ずつ。

#追記 今回の話は実用的な話でしたが、辻井先生が「月刊言語 8月号」で、自然言語処理から言語学へ向けてのフィードバックについて書かれてます。内容もさることながら文章も相変わらず上手い。私自身「確率的言語モデル」本の辻井先生のあとがきを読んで自然言語処理にやってきました。

| | Comments (218) | TrackBack (0)

2008.07.05

最長一致文字列の話

たまには自分の研究紹介

D. Okanohara, K. Sadakane. "An Online Algorithm for Finding the Longest Previous Factors". In the 16th European Symposium on Algorithms. Sep 2008. to appear. [pdf(draft)]

この研究では文字列を順々に読んでいったとき、各位置で過去に一番長くマッチした部分文字列を報告する問題を扱ってます。圧縮のLZ77法を知っているなら、マッチする部分を見つける部分を解いてます。で、圧縮以外にもいろいろなパターンマッチング問題とか、インデクシングとか、データマイニングとかいろいろなことにこの情報が利用できるということが知られてるみたいです。

で、大抵はハッシュやtrieを組んで履歴を探すんですが、今回対象にするのはテキストが数10GB overとか、すごいでかいデータも扱いたい。で、さぼらず近似ではなく、必ず一番長い文字列を見つけてこいという自ら厳しい問題設定。最悪計算量ももちろん抑えたく、さらにそのインデクスはコンパクトであってほしい。

で、アイディアとしては、実はPrefix Treeをインクリメンタルに構築する際の副産物として、マッチング情報が出てくる(論文自体も元々はCompressed Suffix Treeをインクリメンタルに作る方法として最初やりはじめたのだが、これだけ切り出すと結構きれいな話になったので切り出した)

結論として大体、履歴の約半分のスペースでできて、履歴長nだとlog^3 nぐらいで見つかる。

最終的に得られたアルゴリズムは、何でこれでできるのかはぱっと見わからん。インデクスといっても、持っている情報は履歴の文字を並び替えた配列と、それの2倍の長さのbit array。これらの上でrankやらselect、rmq操作をすると何故かマッチング情報がでてきて、インデクスも正しく更新される。詳しくは読んでみてください。

でアルゴリズム自体は結構単純にまとまったのだが、ちゃんと性能出そうと思うと実装が結構大変だった。
今もまだ、ゴリゴリチューニングしてます。あと10倍ぐらいは速くなるかなぁ。もう一工夫ぐらい必要か。

---
ついでに紹介。
moriさんが紹介していたsuffix arraysの新しい線形時間保障のアルゴリズム [pdf]。これは実用的にもそこそこ速いが、実装が非常にコンパクトなのがよい。これも要約しすぎていて、最終的には、なんでこれでできるのかわからないのが残った。

最近提案された線形カーネルに対する学習法。とても速いのに、これもすごいコンパクトな実装 [pdf] ( "A dual coordinate descent method for large-scale linear SVM.") shrinkingとか含めてもC++で100行強ぐらいでかけるらしい。

| | Comments (44) | TrackBack (0)

« June 2008 | Main | August 2008 »