Weekly Top 10
エレベータとHDDヘッダの動きに共通するもの
2007/08/20
先週の＠IT NewsInsightのアクセスランキングは第1位は「Visual Basicアプリをどうする？ に情シス担当者は悩んでいる」だった。Visual Basicで書かれたアプリケーションを、Webシステムに移行したいという企業からの相談を、アクシスソフトが当初の予定から1カ月延長して受け付けるというニュースだった。Visual Basic 6.0のサポートは2008年4月に終了する。レガシー資産となったVBアプリケーションが頭痛の種となっているようだ。
|
||||||||||||||||||||||
個人的に気になったのは、2位の「辞書不要の形態素解析エンジン『マリモ』とは」だ。事前に人が作成した辞書を使うのではなく、動的にネット上から集めたテキストを解析して辞書を生成するという新しいアプローチの形態素解析エンジンだ。新語や未知語に強いという特徴があるという。
ヒューリスティクスと統計的アプローチ
自然言語を計算機で処理するには、統計的アプローチだけでは難しいというのが常識的な見方だろう。ある程度、機械的に処理をして、そこからは特定の語彙をキーに、たくさんの例外ルールを適用するといったことを行わないと、精度が上がらない。
経験的に付け加えられていくルールやアルゴリズムは、「ヒューリスティクス」と呼ばれ、自然言語処理には欠かせないアプローチだと認識している。
今回取材したマリモでは、1000語ほどの予備的な語彙があるだけで、基本的にすべて統計処理だけを行う。それで十分な性能や精度が出るというのだから、にわかには信じがたい。
かな漢字変換はヒューリスティクスのかたまり
ジャストシステムの類似文書検索ソフト「ConceptBase」が登場したばかりの頃、その仕組みを知ろうと取材したことがある。それ以前に、かな漢字変換ソフトの「ATOK」について取材を重ねており、日本語に関する深い洞察と、積み重ねてきた日本語処理の経験とが生かされているということを聞いていたので、ConceptBaseにも、そうした「日本語処理のジャストシステム」の面目躍如たる技術が入っているのだろう、と思ったのだ。私は飛行機に乗って本社のある四国にまで飛んだ。
ATOKの開発担当者は、辞書や変換アルゴリズムのメンテナンスを、「調香師やピアノの調律師のような仕事」であるという。ほんの少しのさじ加減の違いで、ユーザーを驚かせるような誤変換を起こしてしまう。変換効率だけが重要なのではなく、ユーザーの思考や作業が一瞬止まってしまうようなインパクトを取り除くことも、かな漢字変換には重要で、そのためには根気よく誤変換の例をつぶしていくヒューリスティックなアプローチが欠かせないのだという。
ところが驚いたことに（そして飛行機で飛んでいった記者が落胆したことに）、ConceptBaseは純粋に工学的、統計的アプローチ以外に特殊な言語処理を行っていないという。開発担当者は、だからこそクリーンなコードで高い精度が出せたと胸を張った。
同じ頃、マイクロソフトでかな漢字変換を開発していた担当者に取材をした。すると、その担当者はかな漢字変換からヒューリスティクスな処理を取り除き、ユーザーが入力した文章から得られた統計的なデータを元に辞書を作るのがベストだと話した。
ATOKとマイクロソフトのIMEとで、同じことをやるのに、まるで正反対のアプローチを取るのはおもしろいなと感じた。ちょうど、形態解析エンジンのマリモで、統計処理だけに頼るという従来と正反対のアプローチを取ったように。
エレベータとHDDヘッダの動きに共通するもの
ここで、ちょっとしたクイズを1つ。エレベータと、ハードディスクのヘッダの動きに共通するものは何でしょう？
答えはヒューリスティクスを用いてスケジューリングを最適化していること。エレベータというのは、ただ単にボタンが押された階に向かうだけでは運用効率が低くなり、ユーザーはなかなか来ないエレベータを待つのにイライラしてしまう。例えば、2台のエレベータが運行しているビルで、特別なアルゴリズムを使わないとする。すると、こんなことが起こる。1台が1階から出発して3階でお客を拾う。拾っている隣をもう1台が通り過ぎ、4階のお客を拾う。2台のエレベータは尺取り虫のように1階違いで止まりながら進むことが多く、結果として動きが同調しがちになる。ユーザーの待ち時間を最短にするなら、1台が上のほうにいるときには、他方は下の方をカバーするべきだが、そうはならない。
これは寺田寅彦が随筆に書いていたというぐらい古くから知られた話で、よほど古いビルでもない限り、最近のエレベータは、さまざまなアルゴリズムで効率を高めている。上下方向を示すライトだけを点灯させ、エレベータのカゴが何階に止まっているかをユーザーに知らせないものが増えた。これは、必ずしも直近にいるカゴを呼ばれた階に止めるのが最善とは限らないことから、古いエレベータなら止まったであろう階を通り抜けさせることがあるからだ。
また、最近はエレベータホールの手前で行き先の階を入力させるようなものもある。あらかじめ行き先階が分かることで、はるかに効率的な運行が可能になる。
ハードディスクのヘッダも、エレベータ運行と似たような問題を抱えている。ヘッダは、レコードの針のように回転する円盤に記録されたデータを読み取っている。あるセクタのデータが読み込めるチャンスは1回転する間に1度しかない。しかし、ヘッドの移動速度は有限で、円盤は高速に回転している。従って、読み出すべきセクタに対して順番にアクセスするよりも「1-3-2-4-5-7-6」と、適宜順番を入れ替えたほうが結果として高速に処理が終わる可能性がある。考えなければいけないのは、最小の回転数で必要なデータをすべてピックアップすることだ。
エレベータやハードディスクのヘッドのスケジューリングには、これがベストだという決定的な解がない。与えられた条件（時間帯、利用法などでも変わってくる）で、経験的にこうするといいだろうというヒューリスティックなアルゴリズムを積み重ねていくしかなく、そのアルゴリズムは企業秘密というベールに包まれている。
ヒューリスティクスを捨てるLinuxカーネルのタスクスケジューラ
もう1つ「ヒューリスティクスか否か」という文脈で、最近驚いたことがある。それは現在、Linuxカーネルでタスクスケジューラの大がかりな入れ替えが進行中であるということだ。
OSのタスクスケジューラは、実行すべきプロセスに優先順位を付け、一定の実行時間を割り振るという重要な仕事を担っている。それほど重要でOSの根幹に関わるようなモジュールが、ごっそり入れ替わるというのも驚きだし、いまだに入れ替える意味があったというのも驚きなのだが、それにも増して驚かされたのは、新しく採用される「CFS」（Completely Fair Scheduler）というタスクスケジューラは、それまでのタスクスケジューラで採り入れられてきた多くのヒューリスティックなアルゴリズムを一切捨ててしまった、ということだ。どのタスクを優先するべきか、あるいはいつどういうタスクが発生するかなどは、結局のところ分からない。だったら、もう純粋にすべてのプロセスを「フェア」（公平）に扱い、ややこしいルールは捨ててしまおう、ということだ。
LinuxをデスクトップOSとして利用している人なら、X Window Systemのレスポンスが悪いことにイライラしたことがあるだろう。実行中のプロセス自体は順調に動いても、ひどいときには数秒ほど画面が更新されないためにユーザーの感覚的には「固まった」ように見える。これは優先順位の付け方が恣意的であるために起こる問題だ。Xの優先順位をユーザーが明示的に変更することで回避できる問題として広く知られていたが、ほめられたアプローチではない。
この問題は、今後CFSに移行すれば軽減されるといわれている。処理速度が上がるようなことは当然ないが、ユーザーが体感する処理速度は変わってくる。CFSで変更できるのはタスクスイッチの粒度だけで、粒度を荒くすればバッチ処理のサーバ向け、粒度を細かくすれば遅延の少ないデスクトップ向けのシステムになる。
ちなみに、こうしたアプローチを最初に唱道し、パッチを作成したのがコンピュータの専門家ではなく、オーストラリア在住の麻酔科医だというのも、ちょっと驚かされる話だ。
さまざまな条件を勘案してヒューリスティックなアルゴリズムを積み重ねても、ある時、パッと捨ててしまった方が、よりよいものができることがあり得る。まるでコロンブスの卵のようだが、Linuxカーネルのタスクスケジューラと辞書不要の形態素解析エンジンのマリモは、そうした点で共通しているように記者には思われた。
情報をお寄せください：
最新記事
 |
|
|
|
|
