Toy problemsは役立たずか(Floydの問題)

U = {√1, √2, …, √50}を2つのグループに分け、グループ毎の和を求める。和の差がなるべく小さくなるようなグループ分けを、制限時間10秒で見つけよ。

goal = (√1 + √2 + … + √50) / 2 ≈ 119.517900301760392247020223113… としたときに、{√1, √2, …, √50}のサブセットで、和がgoalに最も近いものを求めればよい問題です。

1881526917Bob Floydによって提供されたというこの問題は、Knuthによって1977年に発表されました(Selected Papers on Computer Scienceに再掲されています。参考文献リストあり。索引あり。)。

学生だったときに研究室(の一部)でこの問題を話題にしたことがあります。遺伝的アルゴリズム(Genetic Algorithm, GA)と呼ばれる最適化手法を研究する人が多くいた研究室でしたが、GAではあまりよい解は見つかりませんでした。(エージェントアプローチ人工知能 第1版のp.624によれば、GAは何かをする上で3番目によい方法だそうです。)

4274200183伊庭先生の『進化論的計算手法』でこの問題が取り上げられているのは、そのような経緯のためと思われます(ちなみに、この本の第1版のまえがきによると、私は第5章の共著者ということになっていますが、第6章の間違いですね。)

すべてのグループ分けは2の49乗通りありますが、当時のコンピュータで10秒でこれを全探索するのはおそらく不可能だったはずです。当時のコンピュータでよい解を見つけるには、大量のデータを処理する方法と計算時間を見積もる方法を知る必要がありました。ですから、このようなtoy problemsからも、いろいろ学ぶことがあるというのがKnuthの主張でした。

学ぶことがあるという点は今日でも変わりませんが、コンピュータは圧倒的に速くなっているので、この問題から学べることは少なくなっているかもしれません。それでも、やったことがない人は、ちょっとプログラムを書いて試してみてください。楽しめることは間違いありません。

doubleで計算するとこんな感じになります(最良解は1つではありません)。

119.517900301760391812422312796: goal
119.517900301760320758148736786: {1,4,5,7,8,9,12,13,15,16,20,25,27,30,31,33,37,38,41,43,44,46,47,48,49}
119.517900301760462866695888806: {2,3,6,10,11,14,17,18,19,21,22,23,24,26,28,29,32,34,35,36,39,40,42,45,50}

goalの正確な値は119.517900301760392247020223113...で、doubleの計算結果は小数点以下14桁までしか一致しません。2つのグループの合計の一致は、(厳密に計算しても)小数点以下12桁までなので、けっこうぎりぎりのところで計算していることがわかります。

GCCでlong doubleで計算するとこんな感じです(最良解は1つではありません)。

119.517900301760392242633734838: goal
119.517900301760320737332055074: {1,4,5,7,8,9,12,13,15,16,20,25,27,30,31,33,37,38,41,43,44,46,47,48,49}
119.517900301760463740996520698: {2,3,6,10,11,14,17,18,19,21,22,23,24,26,28,29,32,34,35,36,39,40,42,45,50}

コードは後ほど。

マンデルブロ集合をOpenCLで描く(Mathematica)

CUDAを使ってマンデルブロ集合の描画を3桁速くする方法を以前紹介したのですが、同じことをOpenCLでやってみます。NVIDIAのGPUを搭載していないノートPCを使うことが多くなった自分用のメモでもあります。書き換え方は、OpenCLLink プログラミングで紹介されています。

書き換えたコードは以下の通りです(RSSリーダーでは表示されないかもしれません)。

最初に作成したコードをCore i7-3612QM 2.1GHz上で実行するのと比べて、ここで作成したコードをIntel HD Graphics 4000上で実行すると、3桁くらい速くなります。

Manipulateを使ってインタラクティブに描くコードは以下の通りです(RSSリーダーでは表示されないかもしれません)。

似たような話がMathematicaのマニュアルにも載っていますが、ここで書いたコードなら、描画の中心もインタラクティブに変わります。

realtime

チューリング生誕100年

今年はチューリング生誕100周年、2012年6月23日はまさにその記念日だったそうです。チューリングは私のヒーローだったはずなのですが、彼の発明をネタにしたパズルがGoogleのトップページを飾るまで、そのことに気付きませんでしたアーカイブ。(参考:Google アラン・チューリング生誕100周年のアルゴリズムゲームが出来るロゴを全問クリアすると・・・

追記:ソースが公開されています:Google doodle for Alan Turing’s 100th birthday

そういえば、natureでも特集が組まれていましたね(Alan Turing at 100)。

チューリングにはたくさんの業績がありますが、その中でも特に輝かしいのは次の2点でしょう。

チューリングマシンについてはかつて、ペンローズ『皇帝の新しい心』を読みながら「ペンローズ『皇帝の新しい心』の万能テューリング機械」を、その応用について「停止問題の解決不可能性についてのチューリングの証明」を書きました。他にもすごく重要な文書があった気がしますが・・・。

Windows関係の優れた技術書や、コンピュータのすばらしい入門書『CODE』の著者であるチャールズ・ペゾルドさんが、チューリングマシンについてのオリジナル論文“On Computable Numbers, with an Application to the Entscheidungsproblem”を解説した『チューリングを読む』が、いいタイミングで出ています。情報系の学生は原論文の概要はもちろん知っているでしょうが、細かいところまでとことん読んでみたいという人は、手に取ってみてはいかがでしょうか。原題は“The Annotated Turing”、邦題ももう少し格調高いものにして欲しかったです。

チューリングテストとは、人間と会話して、機械であることを見破られるかどうかのテストです。機械なのか人間なのかを機械が判断する試みの一つ、CAPTCHA(ブラウザに変形させた文字列や単語を表示し、それを読み取れるかどうかを試すテスト)に尊厳を傷つけられている人も多いかもしれませんが、チューリングテストはこの逆バージョン(?)という感じです。

しかしよく考えると、チューリングテストというのはかなり気の利いた構造になっています。試すものと試されるものが同じ、つまり「知性」によって「知性」をテストするのです。知性を、

知性:それが存在しないことが「知性」によって断言できないなら、あると見なされるもの

という再帰的な形式で定義しようというのがチューリングの提案です(と私は解釈しています)。

このような再帰的な構造が見出されない場面で、「人間が区別できるかどうかでテストする」という意味で「チューリングテスト」ということばを使うのは間違いだと思います。そいうい意味で、先述のCAPTCHAは実は、チューリングテストの別バージョンとは言えません。たとえば、「人間が秩序が見出せない」という条件で乱数を定義するのはかまいませんが、ここで試されているのがランダム性であるのに対して、試す方にはランダム性はおそらく要らないので、この条件を「チューリング的」と呼ぶのは(私の解釈では)間違いです。

という具合に、チューリングテストについて考え出すといろいろ面白いのですが、これまで考えたことのなかった視点を提供してくれたのが、クリスチャン『機械より人間らしくなれるか?』です。ロブナー賞という、チューリングテストのコンテストでは、人間の審判が機械と人間の両方とチャットします。審判は、機械と人間を正しく区別することを目指し、機械(の開発者)と人間(審判とは別)はともに、人間と見なされることを目指します。クリスチャンが、このコンテストに審判でない人間、つまり人間と見なされることを目指す人間として参加した経験を元に執筆したのが本書です。

チューリングテストは、人間が知性を持っていることを前提としたテストなので、人間がこのテストで機械と見なされたとしても、傷つくのはチューリングテストというアイディアであって、人間の尊厳ではないと思うのですが、この本の著者は「ディープブルー対カスパロフ」におけるカスパロフのように、人類を代表して、自分の人間性をかけてコンテストに参加したようです。

このような、チューリングテストの人間側の視点から書かれたものは見たことがなかったので、その意味で面白かったのはもちろん、チューリングテストに関連して紹介される人工知能研究のさまざまなトピックも面白かったです。かつては人工知能研究者のバイブル的な位置づけだった『ゲーデル・エッシャー・バッハ』をずいぶん意識しているようで、ホフスタッターにはたびたびイヤミを言ってたり。

実はチューリングにはまだあまり光の当たっていない重要な業績があるのですが、それについて書かれたもののベスト1は、スティーブンスンのSF、『クリプトノミコン』かもしれません。

米国製の計算機と日本製の計算機の違い

AppleとSonyの一番の違い part IIという記事を見て、「なるほど」と思ったのですが、こういう「たとえ」を使わなくても、そのままずばりのわかりやすい例がありました。

「高さが3の正三角形の面積は?」と訊かれたら、たいていの人は答えられると思いますが、ウェブで検索するより早く答えられる人は少ないでしょう。実際に、ウェブで解決しようとするとき、米国製の計算機と日本製の計算機、どっちを使いますか?

米国製の計算機

日本製の計算機

米国製の計算機、WolframAlphaの場合

「equilateral triangle height=3」と入力すれば答えが得られます。簡単に答えがわかるのはもちろん、結果のURLが得られるのもいいですね。

日本製の計算機、高精度計算サイトkeisanの場合

  1. 「数学・物理の計算」をクリックする
  2. 「三角形」をクリックする
  3. 「正三角形」をクリックする
  4. 入力指定を「高さ」にする
  5. 高さを「3」にする
  6. 「計算」ボタンをクリックする

これでやっと答えが得られます。初めて行く人は、どこに何があるかがわからないので、「手で計算した方が早い」ということになるでしょう。

keisanがWolframAlphaになる必要はありませんが、「英語がわからなくても大丈夫」以外のメリットを打ち出せるようになるといいですね。

Wolfram CDF PlayerをMathematicaとして使う方法

2017年12月の時点で、ここで紹介する方法は実現困難になっているようです。

http://www.unfindable.net/umm3/

計算可能ドキュメント形式(Computable Document Format, CDF)を閲覧するためのソフトウェアWolfram CDF PlayerとMathematicaの関係は、Portable Document Format (PDF)を閲覧するためのソフトウェアAdobe ReaderとAcrobatの関係に似ています。Wolfram CDF Playerで閲覧可能なCDF文書を作るにはMathematicaが、Adobe Readerで閲覧可能なPDF文書を作るにはAcrobatが必要です。

しかし、CDFとPDFには大きな違いがあります。PDF文書は内容が固定された静的な文書であるのに対して、CDF文書は内容を変化させられる動的な文書です。下はCDF文書の簡単な例です。Wolfram CDF Playerがインストールされている環境なら、aの値を変えながらSin[a x]をプロットしてみることができます。CDF文書の内容は計算によって変化するのです。


Sin[a x]のaの値を変えられるなら、もっと大胆に「Sin[a x]」という式全体を変えられるのではないかと考えるのは自然でしょう。Mathematicaの式を処理できるCDF文書、それはMathematicaとして使えるCDF文書です。使い勝手は多少悪くても、「Mathematicaを使いたいけれど高すぎて買えない」という人にとっては有用でしょう。みんな大好きWolframAlphaも、Mathematicaのすべての機能を使えるわけではありませんし。

残念ながら、直接的な方法はうまくいきません。CDF文書に入力できるのは数値だけであり、「Sin[a x]」のような文字列は入力できないからです。しかし、コンピュータ上で表現されるすべてのものは、メモリ上では数で表現されています。「Sin[a x]」のような式ももちろん数で表現されています(メモリのことがよくわからない人は、ゲーデル数を思い出してもいいでしょう)。ですから、Mathematicaの式を一度数値に変換してからCDF文書に入力し、CDF文書内でそれを元に戻すというような工夫をすれば、CDF文書で式を扱えます。このアイディアを実現したのが、以前紹介したUniversal Mathematica Manipulator (UMM)です。

UMMには、Mathematicaの式を変換してできる数値が長大なため入力に手間がかかるという問題がありました。Wolfram CDF Playerには、文書上でクリップボードからの貼り付けができないという制約があるため、長大になる数値をCDF文書上で入力するための面倒な仕掛け(VBScriptやAppleScript)が必要でした。(Mathematicaに付属するCDF Playerなら貼り付けられます。このように仕様がばらばらなことが後で混乱を生まないことを祈ります。)

ここでは別の方法を紹介します。

まず、Wolfram CDF Playerをインストールします。これがなくては始まりません。

次に、PHPを使えるウェブサーバをlocalhostに用意します。WindowsならXAMPPを導入するのが簡単でしょう。

下のような内容のexpression.phpをhttp://localhost/umm3/expression.phpというURLで呼び出せるようにしておきます。ディレクトリumm3は、ウェブサーバから書き込めるようにしてください。

<?php

$file = 'expression.txt';

if (isset($_GET['body'])) {
  file_put_contents($file, $_GET['body']);
  echo $_GET['callback'].'()';
} else {
  if (is_file($file)) echo file_get_contents($file);
  echo '(* OK *)';
}

PHPのmagic_quotes_gpcがOffであることを確認します。XAMPPの場合はデフォルトでOffになっています。Macの場合はphp.iniを編集してApacheを再起動する必要があるかもしれません。

http://www.unfindable.net/umm3/にアクセスします。

お約束ですが、上の手順がよくわからない人は、拙著『Webアプリケーション構築入門』などを参照してください。

以上の準備ができたらhttp://www.unfindable.net/umm3/にアクセスします。ピタゴラス3体問題のような比較的大きなプログラムも実行できることを、Wolfram CDF Player 8.0.4(Win, Mac)で確認しています。