無駄なあがきの記録：2006-2008

この9年間の無駄なあがきについて書いてみる。(前回)
2007〜2008年の状況について追記しました(2010/7/6)
情報理論と領域計算量がらみで当時考えていたことを追記し、前後の文脈を書き直しました(2010/9/5)

独学はやっぱり無理だった

2005年末、会社を辞める直前の時期のAmazonの購入記録によると、自分は数学書を何冊かまとめて購入している。正統的な数学を学ぶというのは自分の意図するところでなかった。ただ、計算機科学というのは酷く数学を多用するので、数学語がわからないと全く意味がわからないので、順序構造とか圏論とか集合とかには慣れる必要があると考えていたようだ。
明けて2006年中の購入記録は、初志の高さが井の中の蛙の単なる幻想であったことを雄弁に物語る。そもそも学問の方法ひとつないのに本だけ積んだところで、何もできはしなかった。買ったものはコンピュータの実用書(請負仕事の為に買ったものもあれば、将来的に対応を求められるという漠然とした恐怖に駆られて買ったものもある)、家事まわりの本、趣味の本、ポルノにほぼ尽きている。
教訓があるとすれば、「仕事の方法を確立していないアマチュアが漠然としたビジョンで研究めいたことをはじめても、時間と金の浪費に終わる」ということに尽きる。ただし、食うためにLAPP(Linux + Apache + PostgreSQL + PHP/Perl)ないしLAMP(PostgreSQLのかわりにMySQLを使う)システムの開発を2〜3件請負で手がけたことは後の再就職の助けにはなっただろう。
志の低い購入記録の中で、Turing全集の「数理論理学」の巻[1]だけが、値段と内容の両面で異彩を放っている。もちろん読めるはずもなかったが、買った理由については説明が必要だろう。

Turing の "Checking a large routine"

自分はサーベイを進めていて発見したTuringの論文[2]に目を開かれた。数学者に対してではなく、コンピュータプログラマに向けて平易に書かれたこの論文は、40bitレジスタのマシン上で階乗を求めるプログラムを例にとって、プログラムの停止性証明の手法を説明している。かれは順序数の解釈について、人を驚かせるようなことを言うのだ(id., p. 2。なお順序数表記は現代のものと違うので注意(cf. [3], p. 2))：

純粋数学者にとって、[プログラムの実行に伴って減ってゆき、プログラムの終了時点で0になる]値に順序数を割り当てるのは自然なことです。この問題の場合、順序数は $(n-r)\omega^2+(r-s)\omega+k$ で、同じものをより高踏的でない形で表現すると、整数 $2^{80}(n-r)+2^{40}(r-s)+k$ になります。

Turingが言っているのは、40bitレジスタのマシンなら $2^{40}-1$ がレジスタ1個で表現できる最大の自然数になるのだから、 $\omega$ は $2^{40}$ 、 $\omega^2$ は $2^{80}$ で置き換えてしまってよいということだ。もちろん32bitマシン、64bitマシンそれぞれに $\omega$ の具体的解釈はレジスタ長に応じて変わることになる。
この論文の紹介記事[4]をダウンロードするため、2005年6月に、自分はIEEEに個人加入した。だが、もともと電気の「で」も知らず、ホイートストンブリッジの均衡状態の抵抗値について最近(2010年6月)知ったという有様の自分にとって、IEEEが有用だったのはそこまでで、翌年の会員資格延長は行わなかった。後2007年8月に加入したACMはまだしも有用だったため2010年7月現在も個人会員であるが、最近はあまりメリットを感じない。
ところで、数学者に対してTuringが書くときにも、確かに具体的な書き方はしてあるものの、自分が眺めた限りでは決して平易ではない。自分が買った巻はまさに、つまり1930-40年代の世界最高の数理論理学者たちに向けた、論理記号も当時の表記のままの、非常に読みづらい論文ばかりが載っているようだった[5]。収入の不安定さも手伝って、以後、自分は目次から内容を推測して、難しそうなものは買い控えるようになる。

性能予測の方法論を求めて

自分は SE みたいな仕事をやっていて、システムの性能予測をやりたくて Excel で fitting （実データをグラフ用紙の上にぶちまけて、できるだけ多くの点を通るか近くをかするようなきれいな曲線を探すという仕事）をやる必要に迫られて30過ぎではじめて片対数、両対数のグラフ用紙がなんの為にあるのか知った。経済学・ファイナンスとか、化学工学（反応速度論やら輸送やら撹拌やら、スループットとかスケールアップという概念を追って行ったらそういう話だった）とかを調べて、一応どういう事をやるのか、というのは判ったけど

2006年末から2008年にかけては、プログラミングやシステム構築の半端仕事から離れて情報システムインフラの設計／見積もりに携わることが増え、それに伴って自分の関心は、あくまで「そういってよければ」だが、形式言語理論から最適化手法にシフトしていった。上の引用は当時の状況について2009年に書いたもの([6])。
当初、自分は最小二乗法も知らない状態で性能の実測値から将来の性能を外挿することに挑んだが、それはどうもグラフを見る限りほとんど無意味なようだった。自分の知っているシステムの性能は処理量に対してほぼ一定かなめらかに変化し、ある点からほとんど不連続に落ち込むものであって、多項式近似や指数近似による外挿に意味があるようには思えなかった。
性能問題に直面するときには、プログラムの遅いアルゴリズムよりは、むしろ、データベースの大きいテーブルにロックが集中するといった設計上の問題や、単純なメモリ不足が問題になることが多かった。重いソートは要件定義や試験実装の段階で諦め、組合せ最適化は近似アルゴリズムとタイムアウトを設定すればよい。「実用システムのコードで遅いアルゴリズムが問題になることはない」と仮定するのは、自分の視点からはよい近似であるように思えた。
サーバの設定シートを書いたり、Visioでシステム構成図を書いたり、データベース上の排他制御に関連した厄介なバグの洗い出しのために、Oracleのトリガーを一夜漬けで書くといった仕事をしながらも(PL/SQLの文法は本で見たAdaに似ていた)、自分はプログラムを書く前、システムを構築する前にシステムのボトルネックを予測する方法はないものか、と考えるようになった。
自分は性能改善の手がかりを化学工学に求めた。化学工学というのは化学工場を経済的・効率的に運営し、高品質な製品を作るための工学である。化学工学でプラント全体のスループットや効率性を考えるときには、単位操作(unit operation)、すなわち独立した各工程に分解して考えてゆく。この考え方自体は化学工場以外にも適用できるから、適用範囲を広げてプロセス工学と呼ばれることもある。
情報システムインフラはすべて情報理論に従うから、そのスループットの経時変化も、運用上の制約も、熱機関と同じような性質を持つ。熱力学・統計力学とのアナロジーで表現すると、こうなる。メモリアロケータは未確保の記憶域という「負のエントロピー」を消費してデータを書き込み、全体の「温度」を上げてゆく。CPUと記憶域の「温度差」がなくなると、情報システムは「カルノーサイクル」に近づき際限なく遅くなるか、データ領域が溢れて正常に機能しなくなるから、どこかで「操業」を止めて「冷却」するか、効率を犠牲にして並行して「冷却」を行う必要がある。これがつまり postgresql の週1回の vacuum や、毎朝の tomcat の再起動といった当時よくあった運用の意味である。(cf. [7][8])
だから事情は化学プラントでも情報システムインフラでも全く同じだと当時の自分は思った。
自分にはそこまでしかわからなかった。何を目標に最適化し、コスト関数が何であるかがわかっていなかった。化学工学やデザインパターンの本を見ながら自分は情報システムインフラにおける「単位操作」の定義を模索したが、全く実りはなかった。
また、系全体のスループットはボトルネックに鋭く制約される。ボトルネックの事前予測はこれらの性能分析結果を照らし合わせて行うものであって、数学の出番はほとんどない。情報システムインフラの諸特性を汎用性のある数式に詰め込むことは不可能か、無意味である。
今考えてみると、在庫から補充される化学プラントの原料と違い、通信サービスのリクエストは確率過程に従うから、全く同じとも言い切れない部分はあるし、電車や電気自動車の回生ブレーキのようなサブシステム相互の密結合が、情報システムインフラにも皆無ではないのに、それをうまくモデル化できる人材が少なくとも日本のIT業界には欠けているようにも思う。

半可通と専門知、領域計算量、漸近記法

ボトルネックの予測の方法論について考えつつ、自分はネット上の計算機科学をめぐるある論争を傍観していた。
インターネット事業で財をなしたプログラマがいる。かれは一線を退いたのち書評家として有名になったのだが、自分の見識に基づいてアルゴリズムについてのアンソロジーを編む意向をブログに書いていた。だが、かれの理解は偏頗で、とうていまともなアンソロジーが出来上がるようには思えなかった。なお悪いのは、かれがその偏頗な理解を、自身への注目を集めるための戦略的な武器として用いているように見えることだった。釣り乙、である。
かれは、精度を適当に落とせばいろいろな演算が一定時間で終わるという、科学技術計算に通じた人間なら誰でも知っている話を、計算量理論の用語を使ってセンセーショナルに紹介した[9]。
これに対する計算機科学の専門家たちの応答[10][11]は自分にとって不満足なものであった。応答内容それ自体の妥当性については当時の自分の理解ではなんとも判断できなかったが、計算量がいくらか、という主張の前提となる計算モデルの一般的な妥当性が問題なのだとすれば、そこで "it depends." とだけ言われても納得できないと思った。
(量子計算機やアナログ計算機を除く)デジタル計算機の計算可能性についてはTuring Machineという一般的モデルがあり、すべての議論をTMでの計算可能性に帰着させるというコンセンサスがある。
だが、計算量理論の現実的な適用範囲を狭めているのは、現実の計算資源は常に有限であり、TMのようにテープが尽きたら端に継ぎ足せばよい、とはいかないという事実である。詳しい方ならお分かりのように、これは初期の形式言語理論における言語クラスの特徴付けに直結する論点であるが、ここではこれ以上触れない。
当時の自分は数理論理学の周辺分野に「有界算術」とか「有限モデル理論」という分野があることを聞き及んでいた。
もちろんそれらの分野の実情は自分の理解を超えていたけれども、情報理論(統計力学)が領域計算量の根本にある以上、ボトルネックの代表格であるメモリ不足(データベースのインデックス領域不足や、多倍長整数演算の性能に対するレジスタ長の関係など)は、素直に領域計算量の問題である、と考えた。
自分の偏見では、アルゴリズム関連の研究者はそういう本質的問題を半ば意図的に無視し、結果的に(かれや自分のような)半可通が増長するに任せているように見えた。当時の自分は計算量クラスL(LOGSPACEとも書く)、LINSPACEおよびPの関係がP≠NP予想に密接に関連する難問であることを知らなかったから、その理由を単に専門家の傲慢に帰した。
また、関数の増大度を示す漸近記法(asymptotic notation)の不正確な用法が世界的に蔓延しているらしく[12]、非アルゴリズム的なボトルネックの内側での限定的な計算量に対しては適切な表記がないらしいこと[13]も気になった。そしてそれらは本質的に結びついた問題なのだと自分は考えた。
当時知人に出したメール：

bottleneck とか principle of weakest link とか、農学の Liebig's law of the minimum とか、化学工学の rate-determining stage とか、似たような概念があって、(リービッヒのだけは他のより複雑な概念ですが)
まあ要するに landau's ο ですが、
この「もっとも緩増加な関数を選ぶ操作」そのものには1単語の名前はあるんでしょうか? あとその order にも。候補全部それぞれ order があるわけで、何か別の名前で呼べるとうれしいのですが。

この関数増大度の列が超限順序数と関係していること[14][15]に、当時自分は気づいていなかった。だから、この段階ではそれ以上に思考を深めるということもできなかった。

References:

[1] R. O. Gandy, C. E. M. Yates (eds.), Collected works of A. M. Turing, vol.4, North-Holland, 2001
[2] A. M. Turing, "Checking a Large Routine," In Report of a Conference on High Speed Automatic Calculating Machines, Univ. Math. Lab., Cambridge, pp. 67-69, 1949, http://www.turingarchive.org/browse.php/B/8
[3] P. Manolios, D. Vroon, "Ordinal arithmetic: Algorithms and mechanization," Journal of Automated Reasoning, vol. 34, no. 4, pp. 387-423, 2005, doi:10.1007/s10817-005-9023-9
[4] F. L. Morris, C. B. Jones, "An Early Program Proof by Alan Turing," IEEE Annals of the History of Computing, vol. 6, no. 2, pp. 139-143, 1984, doi:10.1109/MAHC.1984.10017 ([2] の解説、訂正済み本文および書き直した図を含む)
[5] M. Davis (ed.), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Dover, 2004 ([1] の計算可能数に関する論文の他、Gödel、Church、Post らの基本文献のアンソロジー)
[6] http://anond.hatelabo.jp/20090924142336 (自分の投稿)
[7] H. G. Baker, "Thermodynamics and Garbage Collection," ACM Sigplan Notices, vol. 29, no. 4, pp. 58–63, Apr 1994
[8] 酒井政裕(訳), 「熱力学とガベージコレクション」, http://www.tom.sfc.keio.ac.jp/~sakai/docs/ThermoGC/ThermoGC.html ([7] の邦訳)
[9] 小飼弾, 「ベキ乗はO(1)でOK?」, http://blog.livedoor.jp/dankogai/archives/50962361.html
[10] 矢吹太朗, 「O(1)というのはご機嫌に速いということ？」, http://www.unfindable.net/~yabuki/blog/2007/12/o1.html
[11] id:okamoto7, 「誤解の元凶は「計算量」ということば？」, http://d.hatena.ne.jp/okamoto7/20071206#p2
[12] D. E. Knuth, "Big omicron and big omega and big theta," ACM Sigact News, vol. 8, no. 2, pp. 18-24, 1976
[13] 矢吹太朗, 「カジュアルなO記法」, http://www.unfindable.net/~yabuki/blog/2007/12/o.html
[14] G. H. Hardy, Orders of infinity, the 'Infinitärcalcül' of Paul Du Bois-Reymond, Cambridge, 1910, http://www.archive.org/details/ordersofinfinity00harduoft
[15] E. Borel, Leçons sur la théorie des fonctions, 4/e, Gauthier-Villars, 1950