読書メモ：プログラマの数学(4)

数学的帰納法

ある主張が成り立つことを0以上のすべての整数について証明する方法。
数学的帰納法は２つのステップで行う

1. P(0)が成り立つ　ことを証明する（基底）
2. 0以上のどんな整数kを選んでも、P(k)が成り立つならばP(k+1)も成り立つことを証明する（帰納）

ドミノだおしに例えると

1. 最初のドミノが倒れることを保証する
2. k番目のドミノが倒れたならばk+1番目のドミノも倒れることを保証する

プログラムで書くと

prove(3);
function prove(n){
    console.log(`いまからP（${n}）が成り立つことを証明します`);
    let k = 0;
    console.log(`ステップ１により、P（${n}）が成り立ちます`);
    while(k < n){
        console.log(`ステップ２によりP(${n})が成り立つならP(${n+1})も成り立つと言えます`);
        console.log(`従って、P(${n+1})が成り立つといえます`);
        k++;
    }
    console.log(`証明終わり`);
}

印象的だったのは、著者が昔、数学的帰納法がわからなかったというエピソードのところで
「p(k)はいまから証明しようとしている式なのに、それを仮定してしまったら証明にならないはずだ」←そうだった、わたしもそう思ったことある、わかる！
「いま思えばproveの引数n(目標にしている数)とproveのローカル変数kを混同してしたのですね」←ほんとだ〜〜！
という感じで、10年越しくらいにもやっとしていたことがわかってすっきりした〜　プログラムがちょっとでもかけるようになってよかったなぁ

ループ不変条件

ループを構成するときにはループの各回で成り立っている論理式をみつけることが重要！ この論理式のことを「ループ不変条件」という。 ループを作るときにはこのループの不変条件はなにか？を考えて作ると誤りが少なくなる

プログラマの数学

読書メモ：プログラマの数学(3)

剰余

剰余は周期性をみつける道具

• 剰余を使って考えると周期性をみつけることができる。
• 周期性を見つけると、大きな数の問題を扱いやすくなる。(一億日後は何曜日か？とか)
• 10の100乗みたいに解く数がとても大きくなっても、同じように位をあげながらあまりを書き出していくと周期性を見つけることができる。
• 「物事を詳しく調べよう」というときに、「こまかいところまで正確に把握しよう」ではなく、「的確な分類」の方が役に立つときもある。

周期性の見抜き方

• あんまりにも大きな数を調べたい時・・・今調べる必要があるのはどの位の数なのか？を考える。
• パリティチェックだとたくさんの並べ方があるけれど、奇数と偶数の２グループに分けて考える。（最後の１ビットがどちらに所属するかを示している。）

プログラマの数学

読書メモ：プログラマの数学(2)

理論

なぜ理論が必要なのか

• 自然言語のあいまいな部分をなくす。理論式で仕様書を表現しようとするとあいまいなところを見つけることができる。
• シンプルで理解しやすい式に変換することができる

理論の言葉

命題・真偽

• 命題：正しいか正しくないかを判断できる式
• 真:命題が正しいとき「真である(true)」という
• 偽：命題が正しくないとき「偽である(false)」という

もれ・だぶり

• もれがないこと(網羅的であること）→　そのルールがどんな場合にも適応できる
• ダブりがないこと(排他的であること) →　そのルールに矛盾がない
• もれ・だぶりがないことは数直線を書くとわかりやすい　

withdom.jukendou.jp

• 網羅的で排他的な分割をすると大きな問題を解きやすく分解することができるようになる。
• 問題の分割はプログラムの中でいうとif文の部分。一つ一つは単純でも組み合わせると複雑になりバグが生まれやすい。if文を書くときは「網羅的で排他的である」のを意識する必要が有る。

命題を組み合わせて新しい命題を作る

• 否定：「〜ではない」という命題を作る演算。
• 二重否定は元に戻る
• 論理積：「AかつB」という命題を作る演算
• 理論和：「AまたはB」
• 排他的論理和：「AまたはB(でも両方ではない)」
• 等値：「AとBは等しい」
• 含意：「AならばB」

論理包含 - Wikipedia

• AがfalseのときBがtrue/falseどちらであってもtrueになるのがわからない・・・！後でもう一回！

• 含意の命題「ならば」をあらわす論理記号 A⇒B [数学についてのwebノート]

• 真理値表：網羅的で排他的な分割を表現する表　 真理値表 - Wikipedia

• ベン図：集合の関係を表す図・直感的に理解しやすい ベン図 - Wikipedia

ド・モルガンの法則

ド・モルガンの法則 - Wikipedia

• 理論式の相対性:理論式の中のtrueとfalse、Aと¬Aと、またはとかつを交換すると論理式全体を否定した式ができる。

カルノー図

複雑な理論式を整理するための図

カルノー図 - Wikipedia

1. 命題の取り得るすべての真偽値の組み合わせに対応した図を書く
2. チェックをつける
3. 隣接するチェックマークを囲うグループをつくる（できるだけ大きく・重なっていてもOK）
4. 作ったグループをあわらす式をつくる

未定義

• true/falseのどちらも得られないとき　undefined(未定義)
• 3値論理での論理積（条件付き論理積）→　&&
• 3値論理での論理和（条件付き論理和）→　||
• 3値論理での否定→　！

プログラマの数学

読書メモ：プログラマの数学(1)

数え方と0の役割

数が大きくなってくると扱うのがむづかしいのでいろいろ数え方が生まれた

大きくなってきたら　小さな「まとまり」に分けて解く

位取り記数法(くらいどりきすうほう）

位取り記数法 - Wikipedia

2進法・16進法など

• 普段使っているのは10進法(10で位が上がる)
• 2進法はコンピュータで使われる(桁数は多くなるが数字の種類は少ない・コンピュータでは10進数より扱いやすい)
• コンピュータを使って計算するとき10進法を2進法に変換し、2進法を使って計算して10進法にしている
• 記数法ではない数え方もある(ローマ数字)

指数法則

指数法則

10の0乗は1の考え方

10の0乗→10を0回かけた数と考えずに、10の３乗・10の２乗・10の１乗は・・と考えていくときルールがシンプルになるには10の0条がなんであれば妥当か と考える

０の役割

• 場所の確保(100　１の位には何もない)
• パターンを作ってルールをシンプルにする

プログラマの数学

the nature of code を読み終えて

1年と半年かかった「the nature of code」の最後の課題が終わったところで、（正確には終わってないんですが・・最終課題の生態系プロジェクトがまだノータッチ）、
いままで書いたブログ記事へのリンク、課題を作って知って楽しかったこと・さっぱりわからなかったことなどまとめておこうと思います。

英語版はこちら

The Nature of Code

で読めます。

日本語版はこれ

Nature of Code -Processingではじめる自然現象のシミュレーション-

私はどちらも読みつつやりました。

はぁ楽しい本だった！ 帯に「一番簡単な世界の作り方」と書いてあるんですが、言いえて妙。
canvas(sketch)の中で自分の書いたルールが、いきいきと、動く！

そしてシフマン先生が大好きになりました。
↓シフマン先生（この動画の最初で拾い上げているのがthe nature of codeです）

次はcoding rainbowやろうかなぁ。 ・・今見たらcoding[Undefined]になってる！商標権の問題だそうな。笑ってしまった

読んでいた時の自分なりのルール

• 本を読んで、そのあとprocessingのサンプルコードを読んで、課題はjavascriptで書く、p5.jsは使わない。

これは単に「書いたことがあるのがjavascriptしかないから」という理由なので特に大した意味はない縛りだったのですが、 おかげでprocessingは描画に特化した言語なんだと気づいたり・processingにある機能を使いたいなぁ〜と思ったら自分で書くしかなく、その結果ES2015を知ったりするきっかけになったりして振り返ると結構よかったかも。

• わからなかったらやめる・脱線する

「高校生や大学生はお休み中にさくっとやってしまってもいいですね」的な紹介をどこかでされていたため、さくっとできるかと思ったら、 全然そんなことはなく・・・。特に序盤よくつまずき、もう軽い気持ちでやることにしました。

課題のリンクとメモ

1~4章をやっていた頃はブログを書いてなかったので課題のリンクなしです。

無生物編

物体が動くのをシュミレートできるようになる

Chapter 0 はじめに

• アニメーションはパラパラ漫画みたいにちょっと動かして・消してを繰り返すと作れる
• 「ちょっと動かして」のルールをどう定義するかが大事
• random()に頼ることは有機的なデザインの解決にはならない。
• 擬似ランダムに偏りを持たせる方法
  • 格率を高くしたい数値を多めに用意してそこから選ぶ
  • 最初に選択肢を決めるランダム値の範囲を偏りのある状態で定義しておく
  • ランダム値を２つ使う（１つ目はただのランダム値・二つ目は１つ目を使うか破棄するかの判別用）
• 平均値付近に多く分布させたい時はガウス分布が使える
• より自然なランダム値を生成するパーリンノイズというものがある

Chapter 1 ベクトル

• 座標を扱うときはxとyをまとめて扱えるベクトルとして使うと楽
• 位置　= 位置　+ 速度
• 場所の変化の割合（速度）
• 速度 = 速度　+ 加速度
• 速度の変化の割合（加速度）
• processingにはベクトルの計算のセットPVctorがある(javascriptにはないので自分でつくる)
• 移動オブジェクトが持つべきデータは何か？機能はなにか？ということを考えてオブジェクトをつくる

• processingにはstatic関数と非static関数がある。（javascriptだとES21015で使えるようになる）

  ログイン - はてな

• static関数がわからない

• javascriptで書こうとするとPVectorを自作しないといけない

  ログイン - はてな

Chapter 2 力

• オブジェクトに力を適用（積算・すべての力を合計）するには　質量で割って、加速度のベクトルに力を加算する。 このときの加速度は瞬間ごとなので、フレームを次に進める前に０にする必要がある
• 物理の公式を使ってシミュレーションしたいとき
  • 力の方向をどう計算するか？
  • 力の大きさをどう計算するか？ のふたつに分けて考えてコードに書き直す。
  • 扱っている対象がベクトルなのか・スカラー（浮動小数点数）なのかに注意する。
• ２章では摩擦や抵抗や重力をやってみた
• 重力の課題でオブジェクト間の対話についてでてくる。どっちに力を計算する機能をもたせるか？で結構迷った。
• 割り算の記号（/）を見たら０で割ることがないように注意する

Chapter 3 振動

• radian（孤の長さ = 半径のときの角度） = 2 * PI * (度数 / 360)
• 角度 = 角度 + 角速度
• 三角関数をつかってベクトルの大きさや方向などを調べたりできる
• 極座標とデカルト座標の変換は結構でてくる
• 単振動などは三角関数を使うと簡単に再現できる
• 波は単振動をずらしてアニメーションさせると作れる
• 波は足すことができる

Chapter 4 粒子系

• 粒子のような多くのものをスケッチするときには、複数のクラスや他のクラスのインスタンスのリストを保持するクラスをつくるとやりやすくなる
• 粒子をつくるときは存続期間のプロパティをつける（粒子が増えすぎると停止しちゃうので永続させない）

• 粒子には普通エミッター（粒子の初期速度・位置などの設定ができる発生源）がある

  パーティクル・システム - Wikipedia

• processingではArrayListをつかって粒子のリストを管理してこれをエミッターとする。

• processingのArrayListはiteratorオブジェクトを作れる。 （反復処理中に要素を削除したり追加したりしても２回参照したりスキップしたりせずにすべての要素に処理ができる！便利！） （hasNext()で次があれば実行させることができる！便利！）

• ES2015の配列でもiteratorオブジェクトが作れる

  ログイン - はてな

• 粒子を管理する粒子系・粒子系を複数管理するクラス、を管理する・・・と、どんどん入れ子にして複雑にできる

• オブジェクト指向の基本原則（継承・ポリモーフィズム・カプセル化）がでてくるけれどここの部分はついていけてないのでまた絶対読み返す

• 継承を使うと他のクラスから特性と機能を受け継ぐことができる。

  ログイン - はてな

• ポリモーフィズムが何か全然わからない・・

Chapter 5 物理ライブラリ

• Box2Dをつかってみる

  ログイン - はてな

・・・の途中で脱落。

あとで読む

• 積分
• toxiclibs

---

生物編

環境に応じて動きを決められるようになる

Chapter 6 自律エージェント

複雑系のルールベースの技法を学んで、複雑な動きをつくれるようになる

• 自律エージェント = 環境ないでどう行動するかをリーダーや全般的な計画を受けずに自分で選択すること
• 自律エージェントの構成要素
  • 環境を認識する「限られた」能力がある
  • 環境からの情報を処理して行動を計算する
  • リーダーを持たない
• 課題ででてくる「vehicle」は「模型は心を持ちうるか」という論文から。

模型は心を持ちうるか―人工知能・認知科学・脳生理学の焦点

• レイノルズ(boidの人)の理想的なvehicle（仮想的な乗り物）
  • 行動選択：環境の注意を向けて環境に応じて行動を計算する
  • 操舵：行動を選択したら次の動きを計算する
  • 移動運動：これは課題ではあんまり出てこないが、行動するときの動きを決める（足を左右交互にだすとか）
• 操舵力の式：操舵力 = 必要な速度（現在の位置から目標地点までの位置ベクトルを最大の速度などで適宜制限したもの） - 現在の速度
• 最大速度などの変数をいろいろあてて特定の動きのシュミレートができる

• 目標に近くなるにつれて減速させたり・・・必要な速度は自分で好きなように決めることができる

  ログイン - はてな

  ログイン - はてな

  • 前方の点から円を描いて円周上のランダムな点を目標地点にする
  • 壁の近くに来たら壁の反対方向へ最大速度ですすむ
  • 流れ場などで環境から与えられる力に沿わせる など

  ログイン - はてな

  ログイン - はてな

  ログイン - はてな

• 経路追従の課題ではベクトル内積が活躍した

  ログイン - はてな

• 複雑系

• 群れ

  ログイン - はてな

• boidを描いて、処理速度をあげるにはどうするか考えた

  ログイン - はてな

  ログイン - はてな

Chapter 7 セル・オートマトン

• 単位を最小（ビット・０か１か）に絞って仕組みを考える

• 時間の経過とともに状態を変化させるやり方をセルオートマトンで見てみる。 すごく単純な系であっても洗練された形状をつくることができる！

  ログイン - はてな

• 2次元のセルオートマトンは世代をフレームで表してアニメーションにしていた

  ログイン - はてな

• 近隣と自分のセルの組み合わせで次の世代が０か1か決めるとき、必要な３つの数字を文字列にしてくっつけて3桁の数字にして、２進数に変換するというのをやっていた、これ思いつかないなぁと思った

Chapter 8 フラクタル

• 自然法則をコーディングするなら、丸や四角よりなどの理想化された形状だけでなく、複雑なパターンを作る必要がある（そのためにフラクタルを学ぶ）
• フラクタルとは、自己相似性のある形状（きりとった一部が、全体を縮小した複製になっている・小さい尺度の構造がある・再帰性がある）
• 株価の変動グラフなどは確率的フラクタル

• 再帰 ログイン - はてな

• 再帰関数には終了条件が必要

• コッホ曲線（決定的フラクタル） これも線はオブジェクトにして、線を管理するarrayListを使うといい。

  ログイン - はてな

• 木　フラクタルに若干のランダム性をもたせると自然にみえる（確率的フラクタル）

  ログイン - はてな

• L-system フラクタルを管理するメカニズム　文字列でルールを表して、タートルグラフィックで描写する、とルールと表現が切り離されてるのが面白かった

  ログイン - はてな

---

知能編

生物の進化の法則を使ってオブジェクトを進化させる

Chapter 9 遺伝と進化

• 今までの課題は初期化するときランダム性や考えた結果としてオブジェクトに特性を割り当てていたが、進化の過程にまかせてみても面白い
• 結果がわかっているときに総当たり的なアルゴリズムを組んで解こうとするのはよくない

• 遺伝的アルゴリズム

  • 遺伝子の型と表現を切り離してつくる
  • 適応度を評価する関数を自分で設計する
  • 評価の高い遺伝子を次の世代に拾われやすいようにする

  • でも突然変異させるのも必要

    ログイン - はてな

• 表現と遺伝子を切り離してつくるといろいろ応用できる

  ログイン - はてな

• 適応度関数を変化させるとこんなことも

  ログイン - はてな

• 適応度関数の部分を人力でやってもいい（対話的選択）　もっとも人気のあった作品に似た作品を次の世代に残しやすくするとか

  ログイン - はてな

Chapter 10 ニューラルネットワーク

• 脳の機能の概念をヒントにより環境に適応できる動きを作ってみる
• 機械学習の初歩の初歩の部分を作ってみる

• 教師あり学習(正解がある)

  ログイン - はてな

• 強化学習（環境に適応する）

  ログイン - はてな

• パーセプトロンは線形分離可能な問題しか解決できない。でも複数のパーセプトロンを組み合わせたら解決出来る（多層パーセプトロン）

• アニメーションで多層パーセプトロンをイメージする

  ログイン - はてな

---

脱線して読んだ（読むつもり）の本

形の美とは何か (NHKブックス)

自然物の美しさはフラクタルの美しさだった・・・！おまけに黄金比もフラクタルの美しさ。ああフラクタル！

ログイン - はてな

[普及版]ジェネラティブ・アート―Processingによる実践ガイド

the nature of code　の前に読んで、nature of code読むきっかけになった本。これはいつかメモに起こしたい

複雑系入門―知のフロンティアへの冒険

複雑系のところを読んでいて、こんなことどうやって思いつくのかなと気になって。でもまだ未読。

プログラマの数学

１章をやっているときに高校数学の記憶がきれいさっぱり消えてることに気づいてあわてて読むことにした。読み途中。

波紋と螺旋とフィボナッチ

この本はめっちゃおもしろかった・・！
アンモナイトも、結晶の螺旋も、しましま模様も、なんでできるか解説がわかりやすく書かれててスッキリとした気持ちに。 植物の茎の先端の「中央部分の連続した拡大と周囲の相似形の構造」が黄金比の長方形そのものだ！ コッホ曲線を単なる座標を再帰関数で扱う書き方からクラスを使う書き方へ変換する課題をやっていたときに、この本を思い出したりした。 あと後ろの方の自伝が胸熱。

www.google.com

私は美術館とかにいったら絵画の細部を眺めるのが好きで、 直線を描いてる部分だったらマスキングテープの剥がれる部分のちょっと絵の具が引っ張られて固まった感じとかすごく綺麗だなって見てしまうんですが、 それって８章に出てきた自己相似性のある形が好きとも言える。 このサイトはかなり高解像度の作品が収容されてるので信じられないくらい拡大できて細部が眺められる。あぁ欲が満たされる・・。

nature of code : 今日の練習「ネットワークのアニメーション」

the nature of code 10章最後の課題

これまで読んできたニューラルネットワークのさわりの部分を可視化したアニメーション

See the Pen ネットワークのアニメーション by kanaparty (@kanaparty) on CodePen.

2016年にギリギリ間に合った・・・！

nature of code : 今日の練習「ビークルの訓練」

前回作成したのは教師あり学習（正解があって、結果と正解から誤差を計算し重みを調整する）だったが
今回は簡易的な強化学習（結果から誤差を計算し、環境に対応する）を作ってみる練習。

今回のビークルにはbrainプロパティがあって、操舵力を決めるときにbrainから処理された操舵力を受け取って それに従って運動させる。

See the Pen ビークルの訓練 by kanaparty (@kanaparty) on CodePen.

環境（黄色い点）から受ける力をbrainに渡して処理してもらい、 その結果が画面の中心（灰色の点）からどれだけ離れているかをエラーとしてトレーニングしている。今回は活性化関数がない。

ビークル内

//操舵力を計算
steer(target){
  var force = [];
  for (var i = 0; i < target.length; i++) {
    force[i] = this.seek(target[i]);
  }
  //ターゲットから受ける力をbrainプロパティに渡して結果をもらう
  var result = this.brain.feedfoward(force);
  this.applyForce(result);
  //トレーニング
  var error = Vector.sub(this.desired, this.position);
  this.brain.train(force, error);
}

brain内では受け取った力の分だけ重み（今回は位置なのでxとyの２つ分）を調整している。

//調整
train(forces, error){
  for (var i = 0; i < this.weightLength; i++) {
    this.weight[i] += this.c * error.x * forces[i].x;
    this.weight[i] += this.c * error.y * forces[i].y;
  }
}

1000回トレーニングを繰り返したら、点の位置を変える。
位置が切り替わった直後は前の位置のときに調整した重みに従って動くので目標がわからなくてフラフラしているように見えるが、
まただんだん調整されて画面の真ん中を目指すようになる。

the nature of codeの一番最初の課題はランダムウォークだった。
ついに動きをつける対象にbrainが〜！！すごい、私も進化してきた感がある。