2016かちのぼやき数学系、情報系を中心に、日頃考えていることをメモがわりに書いていく予定。大学に入ってはじめてプログラミングにふれてから、C、Java、Pythonなど、数種類の言語を使ってきました。プログラミングというものがどういうものなのか分かり始めてきた今、各言語の文法だけではなく、すべての言語に共通している「抽象的な概念」を知りたいと思い始めました。どの言語を学ぶ時も、最初は初心者向けの書籍(あるいはウェブページ)をみて勉強すると思います。初心者向けのものの多くは文法の説明がほとんどであり、各言語の特徴的な機能を理解するためには中級者向け以上のものを読まなければなりません。中級者向けのものを読んでみても、プログラムコードが複雑で何をしようとしているのか理解するのは容易ではありません。そのようなコードを書くに至ったのかを理解するのは至難の業でしょう。そこで、いったん具体的な言語仕様に依存しない抽象的な概念をまなぶことで、プログラム全体を俯瞰的にみる力を手に入れたいと思いました。この力を手に入れれば、難しいコードに出会っても「道筋」がわかるので理解しやすくなるはずだと考えたのです。このような目的に適した本を探した結果、「プリンシプルオブプログラミング」に出会いました。似たような本で「リーダブルコード」という有名な本がありますが、この本では「リーダブルコード」とは異なり、プログラムコードが一切出てきません。抽象度が高い知識を手に入れることができます。本の概要この本は「プリンシプル」という短い標語と、その解説という構成になっています。分類されており、わかりやすいです。解説する本はなかなかないので貴重です。本の帯に書かれた「脱・初心者」という言葉の通り、いままで小規模な開発しか行ったことのない初心者が意識すべきことが書かれています。現役プログラマの方から見ると当たり前のことしか書かれていないらしいのですが、僕のようなプログラミング初心者には「常識」を手っ取り早く身に着けられる良い本だと思います。この本から学んだことこの本の内容を一言でいうとシンプルなコードを書け!です。本全体を通して「シンプル」とはなにか、そしてなぜ重要なのかを説明しています。「シンプル」という言葉には、コードが短い、余計な機能を実装していない、テクニカルではなくだれでもわかる、プログラムを構成している各モジュールの依存関係がほとんどない、など、いろいろな意味を持っています。この「シンプルさ」が必要かというと、プログラムコードは書いたらそれで終わりではなく、ほかの人が書いたコードと組み合わせ、完成した後はそれを保守管理する必要があるからです。「シンプルさ」を維持することで、いつだれがみてもわかりやすいコードになり、また機能の拡張や置き換えが容易になります。考察この本はシンプルということを様々な角度からとらえて解説しています。読み進めていくと繰り返しが多いように感じますが、そのぶん読む側にとっては復習になり理解の助けになります。大規模な開発を始める前に、一度は読んでおいたほうがよい本だと思います。〜ノーフリーランチ定理〜大学の講義「人工知能」の課題でノーフリーランチ定理についての課題が出たので、ついでにブログにも載せておきます。題名に「万能なアルゴリズムは存在しない」と書きましたが、もう少し厳密に言うとこのようになります。コスト関数の極値を探索するあらゆるアルゴリズムは、全ての可能なコスト関数に適用した結果を平均すると同じ性能となる。Macready、1995年、Wikipediaより又引用)少し分かりにくいですね。そこで一般性を捨てて具体例を考えることで、分かりやすさを手に入れましょう。(といっても以下で考える具体例はほぼもとの命題に言い換えに過ぎません。)次のようなアルゴリズムを考えます。関数$f(x)$を最小化するアルゴリズムただし、定義域の要素は有限個だとします。このときノーフリーランチは次のように言い換えられます。すべての関数に関して性能の平均を取ると、どのアルゴリズムも同じである。このことから、次のようにもいえます。関数$f(x)$が未知の場合、どのアルゴリズムが最適かはやってみないと分からない。きなまし法などすべてのアルゴリズムは問題によって得手不得手があり、どの問題にも万能な「最強のアルゴリズム」は存在しないのです。逆に言えば、最適なアルゴリズムを見つけてきたいのならば、解きたい問題についてよく理解し、その情報をアルゴリズムに反映せよ、といえます。言いたいことはすべて書きましたが、「証明がないと信じられない」というかわいそうな素晴らしい人のために略証を与えておきます。この略証は、伊庭先生の研究室が発表した論文に沿って書かれており、記号などもなるべく同じものを使うようにしています。アルゴリズム$a$の集合ただし$X$の要素数は有限します。同じ箇所を探索しても意味がないため、そのような探索はしないことにします。定義を理解しやすいように$f(x,y)=x^2+2xy+3y^2+4y$とし$a$は山登り法(近傍をみて最良の点を採用する)アルゴリズムを考えます。はじめに$a$は初期値を与えます($(x_1,y_1)=(0,0)$)。次に関数$f$によって$z_1=f(0,0)=0$が計算されます。このとき$d_1^X=((0,0)),\,d_1^Y=(0)$となります。,(1,1)$のうちひとつ$(-1,-1)$を返します。次に関数$f$によって$z_2=f(-1,-1)=2$が計算されます。このとき$d_2^X=((0,0),(-1,-1)),\,d_2^Y=(0,2)$となります。9$まで$a$は$(0,0)$の残りの近傍を返します。次にアルゴリズム$a$は$(0,0)$の近傍のうち最良な$(1,-1)$の近傍のうちひとつ$(0,-2)$を返します。次に関数$f$によって$z_{10}=f(0,2)=4$が計算されます。10,4)$となります。残りの近傍についても同様にします。中心$(1,-1)$が全近傍で最良なことがわかったのでアルゴリズム$a$は終了します。証明ここでは証明の方針を書くだけにとどめて、残りは伊庭先生の研究室が発表した論文に任せることにします。あと、ここだけ「ですます調」をやめます。すます調の証明は気持ち悪いので。D_k^Y$で評価できる。求めるべき最小値が$d_k^Y$の成分、すなわち探索を行った全ての$f(x)$の最小値であるからである。そこでアルゴリズム$a$において以下の式を評価することにする。F}P(\mathcal{D}_k^Y=d_k^Y|\mathcal{A}=a,\mathcal{F}=f)\]ただしカリグラフィー書体は確率変数を意味する。ノーフリーランチ定理の主張は、上の式がアルゴリズム$a$に寄らないというものである。ここでこの確率を$d_k^Y$に関して分割する。F$である(元の論文とは記号を変えた)。ここで分割した和が元の式の和をダブりなく全て網羅していることを確かめる。全て網羅していることはほぼ自明のためここでは証明は省略する。アルゴリズム$a$は初項を与える。関数$f$とアルゴリズム$a$が与えられていれば、関数全般の性質から$d_k^Y$が一意に定まる(アルゴリズム$a$は一種の関数であることに注意)。$a$が与えられているとき、$d_k^Y$が違えば$f$も違うことがわかるので、ダブりがないことが示された。d_k^Y$ならば$f$をいくら動かしても$d_k^Y$は取り得ない。逆に$t=d_k^Y$ならば$f$をいくら動かしても必ず$d_k^Y$を取る。F_{a,t}$の個数に等しい。$k$ステップを終えた後で残っている$X$の要素(個数:$|X|-k$)から、$Y$の要素(個数:$|Y|$)への関数の全個数を数えればよく、これは$|Y|^{|X|-k}$である。F}P(\mathcal{D}_k^Y=d_k^Y|\mathcal{A}=a,\mathcal{F}=f)=|Y|^{|X|-k}\]となり、アルゴリズム$a$に依存しない。故にノーフリーランチ定理は示された。