読者です 読者をやめる 読者になる 読者になる

デジタル・デザイン・ラボラトリーな日々

アラフォープログラマーが数学と物理を基礎からやり直す

確率を理解してみる-基礎編

数学 確率

はじめに

確率は最も実生活で役立つ分野といっても過言ではない。未来に起こりうる事象の割合である確率を勉強することは、予知能力を手に入れることにも等しい。元々、確率分野は「何とかして賭けに勝ちたい」という強い思いから始まった分野である。未来を予測することができれば、賭けでは非常に有利になる。人生には様々な分岐があり、どちらへ進むべきかを迷うことも多い。そんなとき、確率的思考ができる人とできない人では、どれだけ自分にとって有利な選択ができるかに差が生じてしまうのである。
出展:数A 確率 | 受験の月

確率が分かるようになると合理的な判断ができるようになりそうですね。
機械学習では「確率」が重要キーワードですし、これまで「順列と組合せを理解してみる」の記事を書いてきたのも確率を理解したいためです。

確率とは

「ある事象が発生する可能性の大きさを表す数値」のことである。
中学2年の時に確率の概念を習っているんですね。てっきり、高校の順列と組合せの後で習うと思い込んでいました。

確率といったら、「サイコロを1回振った時に3が出る確率は1/6である」といった例が有名です。

確率の求め方

\displaystyle 起こる確率=\frac{ある事柄が起こる場合の数}{起こりうるすべての場合の数}

一般式は、起こる場合が全部でn通り、事柄Aの起こる場合がa通り、その確率をpとする。
\displaystyle p = \frac{a}{n} (0≦p≦1)
※確率の英語「probability(プラバビリティ:アメリカ読み、プロバビリィ:イギリス読み)」

先程の「サイコロを1回振った時に3が出る確率」では、分母側は「出る目は全部で6通り」、分子側は「3の出る目は1通り」で \displaystyle  \frac{1}{6} となります。

問題と解説

1個のさいころを投げるとき,4以上の目が出る確率を求めよ

目が4以上になるのは、4,5,6の3通りです。
出る目は全部で6通りです。
\displaystyle p = \frac{3}{6} = \frac{1}{2} となります。

2個のサイコロを同時に投げるとき、2個のサイコロの目の和が6となる確率を求めよ

目の和が6になるのは、{1,5},{2,3},{3,3},{4,2},{5,1}の5通りです。
出る目は全部で 6^2 = 36 通りです。
\displaystyle p = \frac{5}{36}となります。

1~10までの異なる番号のついた10枚のカードから、2枚のカードを取り出すという試行において、次の事象が起こる確率を求めよ。

(1) 2枚とも偶数である。
同時に取り出すため、順番は考えないことで組合せを使う。
全事象は、\displaystyle _{10} C _2 通りとなる。
2枚とも偶数なのは、{2,4,6,8,10}の5枚のカードから同時に2枚を取り出すので、 \displaystyle _5 C _2 通りとなる。
\displaystyle p = \frac{_5 C _2}{_{10} C _2} = \frac{2}{9} となります。

(2) 少なくても1枚は奇数である。
少なくても1枚は奇数ということは2枚とも偶数でなければよいことになる。よって全体から引くことする。 このように「ある事象Aに対して、この事象Aが起こらないという事象」をAの余事象といいます。
2枚とも偶数であるのは先程求めましたので、全体「1」から引けばいいです。
※全事象の確率の方針は必ず「1」となる。
\displaystyle p = 1 - \frac{_5 C _2}{_{10} C _2} = 1 - \frac{2}{9} = \frac{7}{9} となります。

リンゴ2つとバナナ4つの入ったかごから2つの果物を同時に取り出すとき、リンゴ1つとバナナ2つを取り出す確率を求めてください。

全事象は、果物6個の中から3個を選ぶ組合せなので、 \displaystyle _6 C _3 通りとなります。
リンゴ2個の中から1個、バナナ4個の中から2個を選ぶ組合せは、\displaystyle _2 C _1 \times _4 C _2 通りです。
よって確率は、\displaystyle p = \frac{_2 C _1 \times _4 C _2}{_6 C _3} = \frac{2 \times 6}{20} = \frac{12}{20} = \frac{3}{5}

男4人、女3人の計7人を並べるとき、両端が2人とも女子である確率を求めてください。

全事象は、7人の並べ方なので順列となり、\displaystyle _7 P _7 通りとなります。
両端が女子となる時、両端の二人の並べ方は、\displaystyle _3 P _2、間の5人の並べ方は \displaystyle _5 P _5
よって求める確率は、\displaystyle p = \frac{_3 P _2 \times _5 P _5}{_7 P _7} = \frac{3 \times 2 \times 5 \times 4 \times 3 \times 2 \times 1}{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1} = \frac{6}{42} = \frac{1}{7}

最後に

今回はあくまで基礎の部分です。これすら自分的にはまだ勉強不足なところがありますが大まかな確率の概念が分かれば良しとします。
機械学習や統計で使っている確率はまた違った求め方になりますので、次回に説明していきます。

参照

順列と組合せを理解してみる-競馬の組合せ

数学 組合せ

はじめに

これまで順列と組合せを学んできたので、応用として競馬の組合せを計算してみたいと思います。 yaju3d.hatenablog.jp yaju3d.hatenablog.jp

競馬の組合せ

18頭出る場合で想定してみます。

単勝

1着になる馬を当てる馬券です。

1着になる馬は18通り考えられます。
一般式  n
n = 18 なので 18 通りです。

複勝

3着までに入る馬を当てる馬券です。

考え方は単勝と同じです。
一般式  n
n = 18 なので 18 通りです。

馬単

1着と2着になる馬の馬番号を着順通りに当てる馬券です。

1着の馬は18通り、2着は1着の馬を除外して17通りで順列となります。
一般式  _n P _2
n = 18 なので  18 \times 17 = 306 通りです。

馬連

1着と2着になる馬の馬番号の組合せを当てる馬券です。

1着と2着の順序は関係ないため、組合せを使います。
一般式  _n C _2
n = 18 なので  \displaystyle \frac{18 \times 17}{2 \times 1} = 153 通りです。

枠連

1着と2着になる馬の枠番号の組合せを当てる馬券です。

枠を8通りにしたとして、考え方は馬連と同じです。
一般式  _n C _2
n = 8 なので  \displaystyle \frac{8 \times 7}{2 \times 1} = 28 通りです。

枠連(ゾロ目含む)

枠連の場合、同じ枠で1着と2着になる可能があるのでゾロ目も考慮する。

枠を8通りにしたとして、考え方は枠連にゾロ目分を加算します。
一般式  _n C _2 + n
n = 8 なので  \displaystyle \frac{8 \times 7}{2 \times 1} + 8 = 28 + 8 = 36 通りです。

または、全体から引く
一般式  n^2 - _n C _2
n = 8 なので  \displaystyle 8 \times 8 - \frac{8 \times 7}{2 \times 1} = 64 - 28 = 36 通りです。

ワイド

3着までに入る2頭の組合せを馬番号で当てる馬券です。

2頭の順序は関係ないため、考え方は馬連と同じ組合せを使います。
一般式  _n C _2
n = 18 なので  \displaystyle \frac{18 \times 17}{2 \times 1} = 153 通りです。

3連単

1着、2着、3着となる馬の馬番号を着順通りに当てる馬券です。

1着の馬は18通り、2着は1着の馬を除外して17通り、3着は同様に16通りで順列となります。
一般式  _n P _2
n = 18 なので  18 \times 17 \times 16 = 4896 通りです。

3連複

1着、2着、3着となる馬の組合せを馬番号で当てる馬券です。

1着と2着と3着の順序は関係ないため、組合せを使います。
一般式  _n C _3
n = 18 なので  \displaystyle \frac{18 \times 17 \times 16}{3 \times 2 \times 1} = 816 通りです。

ボックス

ボックスとは、連勝式馬券(枠連馬連、三連複、三連単)で選択した全ての番号の組み合わせを購入する投票方法です。

式別 展開
枠連  _n C _2 n(n-1) / 2
馬連  _n C _2 n(n-1) / 2
ワイド  _n C _2 n(n-1) / 2
3連複  _n C _3 n(n-1)(n-2) / 6
馬単  _n P _2 n(n-1)
3連単  _n P _3 n(n-1)(n-2)

5頭を馬連ボックスで買うとした場合、n = 5を計算式に当てはめると、5(5-1) / 2 = 5 \times 4 / 2 = 10 通りになります。6頭なら 6(6-1) / 2 = 6 \times 5 / 2 = 15 通りです。
5頭を3連単ボックスで買うと、5(5-1)(5-2) = 5 \times 4 \times 3 = 60 通りになります。

枠連をボックスで購入するとゾロ目(例 3-3、5-5)は含まれません。

フォーメーション

フォーメーションとは、特に三連単の時に1着・2着・3着それぞれに可能性のある馬番を選択する投票方法です。
ボックスでは買い目が増えるのが難点です。そこでもう少し予想の幅を狭めて目数を減らす買い方がフォーメーションとなります。

式別 展開
枠連 n n
馬連 n n
ワイド n n
3連複(軸1頭)  _n C _2 n(n-1) / 2
3連複(軸2頭) n n
馬単 n n
3連単(軸1頭)  _n P _2 n(n-1)
3連単(軸2頭) n n

枠連馬連・ワイド・馬単3連複(軸2頭)・3連単(軸2頭)

「軸と他1頭」と考えて n 通りとなります。

3連複(軸1頭)

「軸1頭と馬連BOX」と考えて、馬連BOXと同じ  _n C _2 となります。

3連単(軸1頭)

「軸1頭と馬単BOX」と考えて、馬単BOXと同じ  _n P _2 となります。

5頭を3連単ボックスで買うと60通りですが、1着はこの馬しかありえないと考えると3連単(軸1頭)とします。
1着以外の4頭の組合せで考えます。
n=4なので、4(4-1) = 4 \times 3 = 12 通りになります。ボックスで買うより48点も少なくなります。

マルチ

マルチ投票とは「馬単ながし」、「3連単ながし」において、軸と相手の着順を入れ替えた組合せも同時に購入する投票方法です。
言葉だけだと分かりにくいので例を挙げて見てみましょう。

式別 展開
馬単 n \times 2 n x 2
3連単(軸1頭)  _n P _2 \times 3 n(n-1) x 3
3連単(軸2頭) n n x 6

馬単

軸馬①から相手馬②③④に流した場合
・マルチなし→1着①から2着②③④流しの3点です。(軸馬2着固定もできます)
・マルチあり→上記3点に加え、2着①から1着②③④への流し3点で計6点です。
つまり「裏」も購入するって事です。軸馬が1着の時と2着の時両方が対象です。

フォーメーションの馬単が nですから、裏も対象となるため n \times 2 となります。

3連単(軸1頭)

軸馬①から相手馬②③④の場合
1着①から2・3着②③④に流した場合の①-②-③、①-②-④、①-③-②、①-③-④、①-④-②、①-④-③ の6点に加え
2着①から1・3着②③④に同様に流した場合の6点
3着①から1・2着②③④に同様に流した場合の6点の計18点です。

[A(軸)][B][C]というグループですので、ABCの組み合わせ(=馬単の3頭BOX)と同じ考え方になります。
3連単(軸1頭)に3を掛けた n(n-1) \times 3で計算できます。

上記例の4頭の場合、1着以外の3頭の組合せで考えます。
n=3なので、3(3-1) \times 3 = 3 \times 2 \times 3 = 18 通りとなります。

3連単(軸2頭)

軸馬①②から相手馬③④⑤の場合
①-②-☆、②-①-☆、①-☆‐②、②‐☆‐①、☆‐①‐②、☆‐②‐①以上の6パターンがあり、☆の部分に相手馬③④⑤が入ります。
よって6パターン×相手3頭で計18点です。

3連単(軸2頭)は[A(軸)][B(軸)][C]というグループですので、ABCの順列(=馬単の3頭BOX)と同じ考え方になります。
3連単(軸2頭)に6を掛けた n \times 6で計算できます。

上記例の5頭の場合、1着2着以外の3頭の組合せで考えます。
n=3なので、3 \times 6 = 18 通りとなります。

終わりに

即PATで投票内容を入力すると組合せの件数が出てくるけど、なんでこんな件数になるんだろうと思ってた部分があったので、理解が出来てすっきりした感じです。

余談ですが出来るだけ損をしたくない方は、即PATに「投票金額自動配分機能」があります。
参照:マニュアルの「金額」の入力の予算金額セット

これは購入予算額を入力するだけで、どのベットが的中しても払戻金が均一に近くなるように各ベットの購入金額を自動配分する機能です。

参考

順列と組合せを理解してみる-組合せ

数学 組合せ

はじめに

前回、順列を説明しました。今回は組合せとなります。 yaju3d.hatenablog.jp

順列と組合せの違いですが、順列の場合は「順番をつける」、組合せの場合は「順番をつけない」となります。

組合せ

組合せには下記の公式があります。Cはcombination(コンビネーション)の頭文字です。
公式: \displaystyle _n C _r = \frac{_n P _r}{r!}

問題と解説

A、B、C、D、Eの5人から3人を選ぶ

理解するために公式を使わずに問題を解いてみましょう。
3人を選ぶというのは、選ばれた組(3人)と選ばれない組(2人)に分けるということです。
まず、選ばれた組に1人目、2人目、3人目という「席」があると考えて順列と同様に考えます。
 _5 P _3 = 5 \times 4 \times 3 = 60通りとなります。

ところが、これでは「1人目、2人目、3人目」が「A、B、C」のときと「A、C、B」のときは、組としては同じなのに重複して数えられています。
f:id:Yaju3D:20160717113527p:plain

同じ3人が選ばれたときの並び方 3! = 6通り分が重複しています。
これが「B、C、D」…「C、D、E」など他の組合せでも同様となるため、元の式を 3! で割ってしまえばいいです。

 \displaystyle \frac{_5 P _3}{3!} = \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10通りとなります。

計算式を一般化

先程の計算式を一般化してみます。

 \displaystyle \frac{_5 P _3}{3!} = \frac{1}{3!} \times \frac{5!}{2!} (←\displaystyle _n P _r = \frac{n!}{(n - r)!}より)
 \displaystyle = \frac{5!}{3! \times (5 - 3)!}

よって、組合せは次の方法で計算できます。
 \displaystyle = \frac{n!}{r!(n-r)!}
最初の式に戻すと公式と同じになります。
 \displaystyle = \frac{_n P _r}{r!}

問題と解説

10人の人間から7人の代表を選ぶとき、選び方の場合の数を求めよ。

公式を使ってみます。
 \displaystyle _{10} C _7 = \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4}{7 \times 6 \times 5 \times 4 \times 3  \times 2  \times 1} = \frac{10 \times 9 \times 8}{3  \times 2  \times 1} = 120通りとなります。

これくらいならまだしも、例えば、 _{100} C _{98}だと計算が大変になります。
コンビネーションにはこれを簡単にできる性質があります。
 \displaystyle _n C _r = _n C _{(n-r)}
先程の計算を当てはめてみます。
 \displaystyle _{10} C _7 = _{10} C _{(10-7)} = _{10} C _3 = \frac{10 \times 9 \times 8}{3  \times 2  \times 1} = 120通りで同じとなります。

問題と解説

男6人と、女4人の計10人から4人の代表を選ぶとき、男2人と女2人となる選び方の場合の数を求めよ。

これは積の法則を使います。
 \displaystyle _6 C _2 + _4 C _2 = \frac{6 \times 5}{2 \times 1} \times \frac{4 \times 3}{2 \times 1} = 90通りとなります。

重複組合せ

順列に重複順列があるように組合せにも重複組合せがあります。

重複組合せには下記の公式があります。重複組合せはcombination with repetitionsですが Hを使われています。Hは同次多項式(homogeneous polynomial)がおそらく由来とのことです。
公式: _n H _r = _{n+r-1} C _r

問題と解説

青,赤,黒の三種類の玉がたくさんある。この中から4つ玉を選ぶときに得られる色のパターンが何通りあるか求めよ。

3種類のものから重複を許して4個選ぶ場合の数なので、重複組合せの公式から
 \displaystyle _3 H _4 = _6 C _4 = 15通りとなります。

参考

順列と組合せを理解してみる-順列

数学 組合せ

はじめに

前回、順列に入る前に「場合の数」として「積の法則」と「和の法則」を説明しました。 yaju3d.hatenablog.jp

ここで重要なのは「積の法則」で、事象の数がいくつあっても、それが同時に起こる場合は積の法則で場合の数を求めます。

順列とは

順列とは、ひと言で言うと「並べ替え」のことです。 数学的な説明だと「一般に互いに異なる n個のものから r個取り出して、それを1列に並べるとき、その並べ方を、n個のものから r個取る」を順列といいます。
分かりにくいので、実際に問題を説いてみましょう。

問題と解説

1、2、3の3個の数字を並べ替えて3桁の整数を作ります。1度使った数字は2度は使いません。考えうる整数のパターンは何通りできるでしょうか?

積の法則で、 3 \times 2 \times 1 = 6通りとなります。

場合の数が少ないので樹形図で表現してみます。
f:id:Yaju3D:20160710161743p:plain

1度使った数字は2度は使わないため、次の数字のパターンは1つずつ減っていきます。
これは数学の定義では、nの階上(かいじょう) n! として表します。

nの階乗は1から n までの整数を乗算したもので、以下のように展開できます。 n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1

席とは

「並べ替える」というのを視点を変えてみると、下図のように「用意された席に要素を当てはめる」と考えることができます。
f:id:Yaju3D:20160710213741p:plain

n=rの場合

A、B、Cの3人が3つの席に座る方法(順番)は何通りあるか。

「席の問題」では、「席を順番に埋める」ことを考えます。3つの席(n)に3人(r)と n=rの場合となります。

1つ目の席の埋め方は、A、B、Cの3通り。
2つ目の席は、1つ目の席に座った人以外の2通り 。
3つ目の席は、1つ目と2つ目の席に座った人以外(残り)の1通り。

積の法則で、 3! = 3 \times 2 \times 1 = 6通りとなります。

n<rの場合

A、B、C、D、Eの5人が3つの席に座る方法は何通りか。

「席の問題」なので、まず席を順番に埋めてみます。3つの席(n)に5人(r)と n<rの場合となります。

f:id:Yaju3D:20160710222219p:plain

積の法則で、 5 \times 4 \times 3 = 60通りとなります。

順列の計算方法

n<rの場合の計算では、5(=n)から始めて3(=r)個の数を、1ずつ減らしています。
問題の人数(n)や席の数(r)が変わっても、計算の方法は同じです。

順列には下記の公式があります。Pはpermutation(パーミュテーション)の頭文字です。
公式:\displaystyle _n P _r = \frac{n!}{(n-r)!}

_5 P _3 = 5 \times 4 \times 3 (←5から始めて3個かけた)
公式を分解していくと下記のようになります。
=\displaystyle \frac{5!}{(5-3)!}
=\displaystyle \frac{5!}{2!}
=\displaystyle \frac{5 \times 4 \times 3 \times 2 \times 1}{2 \times 1}
=5 \times 4 \times 3 (←分母分子の 2×1 を消した)

n=rの場合も、_3 P _3となります。これは 3!と同じことになります。

重複順列

最初に重複順列の説明をしましたが、もう少し説明を追加してみます。
yaju3d.hatenablog.jp

問題と解説

5題の問題に○、×で答える答え方は何通りあるか。

この例では、「1問目」「2問目」・・「5問目」を「席」と考えます。
このように、要素を何度使ってもよい問題では、「席」の考え方が便利です。

f:id:Yaju3D:20160711002227p:plain

積の法則で、 2 \times 2 \times 2 \times 2 \times 2 = 32通りとなります。
重複順列の公式  n^r を用いて  2^5 = 32 でもいいです。

1問目の答え方は、○か×の2通り。
2問目の答え方も、○か×の2通り。これは1問目の答え方に影響されません。
同じようにして、3、4、5問目の答え方もそれぞれ2通りずつとなります。

順列と重複順列の違い

  • 順列は並び方を考慮する。
  • 重複順列は並び方を考慮せず、選び方のみ。

順列と和の法則

事象の数がいくつあっても、それが同時に起こらない場合は和の法則を使って場合の数を求めます。
今回、順列と和の法則を組合せて場合の数を求めます。

問題と解説

0 から 6 までの7個の数字を取り出して並べるとき、5で割り切れる4けたの整数の個数を求めなさい。

ヒント:5の倍数は一の位が必ず、0か5になることに注意します。

一の位が0の場合と5の場合を別々に考えます。

一の位が0の場合

千の位、百の位、十の位は1から6までの数字を1回づつ使うことができるので、6個の中から3個を取り出し並べる順列の数を求めます。
_6 P _3 = 6 \times 5 \times 4 = 120 通りとなります。

f:id:Yaju3D:20160716164303p:plain

一の位が5の場合

千の位に0が使えないので、千の位は0、5以外の5通り、百と十の位は一と千の位で用いた数字以外どれでも1回づつ使える順列の数を求めます。
5 \times  _5 P _2 = 5 \times 5 \times 4 = 100 通りとなります。

f:id:Yaju3D:20160716164238p:plain

和の法則を使う

ここで、一の位が0の場合と5の場合は同時にはおきないので、和の法則を使用します。
全部で 120 + 100 = 220 通りとなります。

円順列

順列には円順列というのもあります。

問題と解説

4人の生徒が円形のテーブルのまわりに座るとき、座り方は何通りあるか?

順列と同様に並び方だけなら、4! = 24 通りになります。順列と円順列の違いはここからです。

f:id:Yaju3D:20160716170514p:plain

これら4つの並び方は、回転させることによって重なるので、どれも同じ1つの並び方だと考えられる。
つまり、上図の①,②,③,④のように順送りに並ぶ4つの順列は、円形に並べた場合には同一視とします。
よって、この4人の座り方は \displaystyle \frac{4!}{4} = 3! = 6 通りとなります。

\displaystyle \frac{4!}{4} = (4 - 1)!と変換できますので、円順列の公式は (n - 1)!で表します。

数珠順列

数珠順列は「じゅず順列」と読みます。回転したりひっくり返しても一致しない円状の配列を数珠順列といいます。

問題と解説

A・B・C・Dに紐を通してネックレスを作るとき、作り方の場合の数を求めよ

並び方だけなら円順列と同じなので、(4 - 1)! = 3! = 6 通りとなります。円順列と数珠順列の違いはここからです。

f:id:Yaju3D:20160716173715p:plain

上図のようにネックレスなので裏返しても同じになることがあります。
このように表裏をひっくり返すことができる場合には、同一視とします。
よって、2で割るため、\displaystyle \frac{ (4 - 1)! }{2} = 3 通りとなります。

参考

順列と組合せを理解してみる-場合の数

数学 組合せ

はじめに

前回、重複順列をやりましたので今回は順列と行きたいところですが、順列に入る前に「場合の数」として「積の法則」と「和の法則」について説明します。 yaju3d.hatenablog.jp

場合の数とは

ある事柄の起こりうる場合の総数のことです。
場合の数を数える重要な考え方として「積の法則」と「和の法則」があります。

積の法則

事柄Aの起こり方が m 通りあり、その各々に対して事柄Bの起こり方が n 通りあるとき、AとBがともに起こる場合の数は( m × n )通りである。

問題

例えばお絵かきソフトのオプションボタンで、ペンの色が「赤・黄・青」、線の種類が「実践・点線」、図形の種類が「直線・四角形・円」とあった場合、このオプションボタンの組合せで描くことができる図形は何種類あるか?

3 \times 2 \times 3 = 18通りとなります。

解説

ペンの色、線の種類、図形の種類は、それぞれの中から必ず1つを選択するようになっています。つまり、この3つは同時に起こる事象です。事象の数がいくつあっても、それが同時に起こる場合は積の法則で場合の数を求めます。

和の法則

事柄A、Bが同時には起こらないとき、Aの起こり方が m 通り、Bの起こり方が n 通りとすると、AまたはBのどちらかが起こる場合の数は( m + n )通りである。

問題

まったく同じ形の2つのサイコロを同時に投げて、出た目の合計が「5」または「10」になる組合せはいくつあるでしょう?

2 + 2 = 4通りとなります。

解説

出た目の合計が「5」になるのは「1+4」と「2+3」の2通り、出た目の合計が「10」になるのは「4+6」と「5+5」の2通りです。 事象の数がいくつあっても、それが同時に起こらない場合は和の法則を使って場合の数を求めます。

和の法則と積の法則の使い分け

簡単な考え方
和の法則=「または」のとき
積の法則=「かつ」のとき
参照:【場合の数と確率】和の法則と積の法則の使い分け

順列と組合せを理解してみる-重複順列

数学 組合せ

はじめに

高校生の時に順列と組合せを学びました。公式と計算方法は覚えているのですが、きちんと理解していないので実践で組合せを考えても答えがすぐに導き出すことが出来ないんですね。

日曜日の「林先生が驚く初耳学」という番組の中で林修先生が「数学を理解することができれば見え方が変わるからもったいない。」と仰っていました。 例えば講演会の時などに参加者の方と一緒に写真を撮ることになり4人の方と写真を撮ることとなった場合、数学ができる人だと返す言葉が違う、全通り撮っても4人なのでたった15通りと計算することができる。数学を学んでいればそのことが一瞬で処理することができる、なので写真を撮ることは「そんなに大変なことじゃないですよ」と上手に解決することができる。他のケースでも応用することができる「どうせ多くても15枚だし」という考え方になるのでどれだけ写真を撮ってもOKですよと数学的思考がある人は日々の生活での解決法が違う」

私も林修先生のように組合せを瞬時にできるようになりたい。
先ずは重複順列をやります。

写真の組合せ

林先生と写真を撮りたい4人との組合せは全部で16通り。 写りたい人がそれぞれ「いる」か「いない」の2択が4人なので 2×2×2×2=16 全員いなかったら林先生の1ショットになるので(4人全員が「いない」という組合せになるため)その1は引くので(16-1)で15通りとなる。

組合せの基礎

学校で習ったのは、 _n P _r_n C _rn! です。写真の件は n^r - 1 ですよね。

丁度、記号の英語名を探していたら「LaTeXコマンド集」で見つけました。

  • 重複順列 (repeated permutation)
  • 順列 (permutation)
  • 組合せ (combination)
  • 重複組合せ (repeated combination)

重複順列

「同じものを繰り返し取ってよいという約束のもとで」できる順列を重複順列といいます。

参照 重複順列重複順列 nr

プログラマーなら二進数の問題が分かりやすいと思います。
問1 二進数は、2種類の記号0,1を並べて表現されます。2種類の記号0,1を合計3個使って作れる記号は何通りありますか?
答1 2 \times 2 \times 2 = 2^3 = 8 通りとなります。

問2 異なる3個の文字a,b,cから重複を許して4個取って並べる順列の総数は何通りありますか?
答2 3 \times 3 \times 3 \times 3 = 3^4 = 81 通りとなります。

テジションテーブル

参照:第5回 仕様整理に「デシジョンテーブル」を使ってみよう

重複順列が分かると下記3つの条件があった場合、条件はそれぞれ独立していて Y/N の2通りだと2 \times 2 \times 2 = 2^3 = 8通りとすぐに導き出してテジションテーブルをExcelにさらっと書けるようになります。

  • クーポン持参
  • 平日割引
  • 平日シニア割引(65歳以上)

f:id:Yaju3D:20160630235211p:plain

TensorFlowコトハジメ Fizz-Buzz問題

機械学習 tensorflow 人工知能

はじめに

Fizz-Buzz問題
1から100までの数をプリントするプログラムを書け。ただし3の倍数のときは数の代わりに「Fizz」と、5の倍数のときは「Buzz」とプリントし、3と5両方の倍数の場合には「FizzBuzz」とプリントすること。

ここ最近、通勤中の車の中でFizz-Buzz問題をTensorFlowを使って予測出来るんじゃないかと考えていたのですが、 どうやってモデルを作ればいいのか機械学習の初心者なんで方法が思い付かない。
訓練では下記ソースのように数式を使えますが、予測させるわけですから倍数も剰余も使えない。

for i in range(1,101):
    if i % 15 == 0:
        print 'FizzBuzz'
    elif i % 5 == 0:
        print 'Buzz'
    elif i % 3 == 0:
        print 'Fizz'
    else:
        print i

今日(2016/06/04)、何気に誰かやってないかと「FizzBuzz 機械学習」で検索したら見つけました。
2016/05/23に少しバズってたようですが気が付かなかったです。その後リンク先追加

ソースコード

いつものようにDockerのJupyter Notebook上で動かしたのですが、4000台あたりで固まって最後まで動作しませんでした。 Ubuntu上で「python fizz_buzz.py」とすれば最後まで動作しました。
github.com

再度挑戦、Jupyter Notebook上で動かす際にprintを100単位(if epoch % 100 == 0)に出力するようにしたところ、最後まで動作することが出来ました。

# coding: utf-8
# Fizz Buzz in Tensorflow!
# see http://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/

import numpy as np
import tensorflow as tf

NUM_DIGITS = 10

# Represent each input by an array of its binary digits.
def binary_encode(i, num_digits):
    return np.array([i >> d & 1 for d in range(num_digits)])

# One-hot encode the desired outputs: [number, "fizz", "buzz", "fizzbuzz"]
def fizz_buzz_encode(i):
    if   i % 15 == 0: return np.array([0, 0, 0, 1])
    elif i % 5  == 0: return np.array([0, 0, 1, 0])
    elif i % 3  == 0: return np.array([0, 1, 0, 0])
    else:             return np.array([1, 0, 0, 0])

# Our goal is to produce fizzbuzz for the numbers 1 to 100. So it would be
# unfair to include these in our training data. Accordingly, the training data
# corresponds to the numbers 101 to (2 ** NUM_DIGITS - 1).
trX = np.array([binary_encode(i, NUM_DIGITS) for i in range(101, 2 ** NUM_DIGITS)])
trY = np.array([fizz_buzz_encode(i)          for i in range(101, 2 ** NUM_DIGITS)])

# We'll want to randomly initialize weights.
def init_weights(shape):
    return tf.Variable(tf.random_normal(shape, stddev=0.01))

# Our model is a standard 1-hidden-layer multi-layer-perceptron with ReLU
# activation. The softmax (which turns arbitrary real-valued outputs into
# probabilities) gets applied in the cost function.
def model(X, w_h, w_o):
    h = tf.nn.relu(tf.matmul(X, w_h))
    return tf.matmul(h, w_o)

# Our variables. The input has width NUM_DIGITS, and the output has width 4.
X = tf.placeholder("float", [None, NUM_DIGITS])
Y = tf.placeholder("float", [None, 4])

# How many units in the hidden layer.
NUM_HIDDEN = 100

# Initialize the weights.
w_h = init_weights([NUM_DIGITS, NUM_HIDDEN])
w_o = init_weights([NUM_HIDDEN, 4])

# Predict y given x using the model.
py_x = model(X, w_h, w_o)

# We'll train our model by minimizing a cost function.
cost = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(py_x, Y))
train_op = tf.train.GradientDescentOptimizer(0.05).minimize(cost)

# And we'll make predictions by choosing the largest output.
predict_op = tf.argmax(py_x, 1)

# Finally, we need a way to turn a prediction (and an original number)
# into a fizz buzz output
def fizz_buzz(i, prediction):
    return [str(i), "fizz", "buzz", "fizzbuzz"][prediction]

BATCH_SIZE = 128

# Launch the graph in a session
with tf.Session() as sess:
    tf.initialize_all_variables().run()

    for epoch in range(10000):
        # Shuffle the data before each training iteration.
        p = np.random.permutation(range(len(trX)))
        trX, trY = trX[p], trY[p]

        # Train in batches of 128 inputs.
        for start in range(0, len(trX), BATCH_SIZE):
            end = start + BATCH_SIZE
            sess.run(train_op, feed_dict={X: trX[start:end], Y: trY[start:end]})

        # And print the current accuracy on the training data.
        if epoch % 100 == 0:
            print(epoch, np.mean(np.argmax(trY, axis=1) ==
                             sess.run(predict_op, feed_dict={X: trX, Y: trY})))

    # And now for some fizz buzz
    numbers = np.arange(1, 101)
    teX = np.transpose(binary_encode(numbers, NUM_DIGITS))
    teY = sess.run(predict_op, feed_dict={X: teX})
    output = np.vectorize(fizz_buzz)(numbers, teY)

    print(output)

出力結果

(0, 0.53196099674972919)
(100, 0.53412784398699886)
(200, 0.53412784398699886)
(300, 0.53412784398699886)
(400, 0.53412784398699886)
(500, 0.53412784398699886)
  ︙
(9500, 1.0)
(9600, 1.0)
(9700, 1.0)
(9800, 1.0)
(9900, 1.0)
['1' '2' 'fizz' '4' 'buzz' 'fizz' '7' '8' 'fizz' 'buzz' '11' 'fizz' '13'
 '14' 'fizz' '16' '17' 'fizz' '19' 'buzz' 'fizz' '22' '23' 'fizz' 'buzz'
 '26' 'fizz' '28' '29' 'fizzbuzz' '31' '32' '33' '34' 'buzz' 'fizz' '37'
 'fizz' 'fizz' 'buzz' '41' 'fizz' '43' '44' 'fizzbuzz' '46' '47' 'fizz'
 '49' 'buzz' 'fizz' '52' '53' 'fizz' 'buzz' '56' 'fizz' '58' '59'
 'fizzbuzz' '61' '62' 'fizz' '64' 'buzz' 'fizz' '67' 'fizz' '69' 'buzz'
 '71' 'fizz' '73' '74' 'fizzbuzz' '76' '77' 'fizz' '79' '80' '81' '82' '83'
 'fizz' 'buzz' '86' '87' '88' '89' 'fizzbuzz' '91' '92' 'fizz' '94' 'buzz'
 '96' '97' '98' 'fizz' 'buzz']

幾つか不正解してますね、15が'fizz'だったり。

NUM_DIGITS = 10→14に変更するだけでも下記結果の通り精度があがります。

['1' '2' 'fizz' '4' 'buzz' 'fizz' '7' '8' 'fizz' 'buzz' '11' 'fizz' '13'
 '14' 'fizzbuzz' '16' '17' 'fizz' '19' 'buzz' 'fizz' '22' '23' 'fizz'
 'buzz' '26' 'fizz' '28' '29' 'fizzbuzz' '31' '32' 'fizz' '34' 'buzz'
 'fizz' '37' '38' 'fizz' 'buzz' '41' 'fizz' '43' '44' 'fizzbuzz' '46' '47'
 'fizz' '49' 'buzz' 'fizz' '52' '53' 'fizz' 'buzz' '56' 'fizz' '58' '59'
 'fizzbuzz' '61' '62' 'fizz' '64' 'buzz' 'fizz' '67' '68' 'fizz' 'buzz'
 '71' 'fizz' '73' '74' 'fizzbuzz' '76' '77' 'fizz' '79' 'buzz' '81' '82'
 '83' 'fizz' 'buzz' '86' 'fizz' '88' '89' 'fizzbuzz' '91' '92' 'fizz' '94'
 'buzz' '96' '97' '98' 'fizz' 'buzz']

仕組み

It would be cheating to use the numbers 1 to 100 in our training data, so let's train it on all the remaining numbers up to 1024:

学習用データに1から100までの数値を使うことは不正行為とのことで、101から1023までのデータで学習したニューラルネットワークに対して、1から100までの答えの予測を出力するプログラムになっている。

多クラス識別問題

手書き文字認識(MNIST)による多クラス識別問題の時に10クラス(0-9)に分けましたが、今回は4クラスに分けます。
one-hot ベクトル (one-of-K表現) f:id:Yaju3D:20160604231742p:plain

# One-hot encode the desired outputs: [number, "fizz", "buzz", "fizzbuzz"]
def fizz_buzz_encode(i):
    if   i % 15 == 0: return np.array([0, 0, 0, 1])
    elif i % 5  == 0: return np.array([0, 0, 1, 0])
    elif i % 3  == 0: return np.array([0, 1, 0, 0])
    else:             return np.array([1, 0, 0, 0])

入力値と正解値の準備

入力値となる特徴ベクトル「trX」と正解値の「trY」の配列を、101~210まで用意します。
手書き文字認識(MNIST)の入力値は白黒画像(28x28ピクセル=784)でした、Fizz-Buzz問題の入力値は数値をバイナリ変換することである種の白黒画像にするってことになりますね。

NUM_DIGITS  =  10 

# Our goal is to produce fizzbuzz for the numbers 1 to 100. So it would be
# unfair to include these in our training data. Accordingly, the training data
# corresponds to the numbers 101 to (2 ** NUM_DIGITS - 1).
trX = np.array([binary_encode(i, NUM_DIGITS) for i in range(101, 2 ** NUM_DIGITS)])
trY = np.array([fizz_buzz_encode(i)          for i in range(101, 2 ** NUM_DIGITS)])
入力値のtrXは101~1023までの数値のバイナリ表現

trX=
[[1 0 1 ..., 0 0 0] <<101の2進数(0000110101)
 [0 1 1 ..., 0 0 0] <<102の2進数(0000110110)
 [1 1 1 ..., 0 0 0]
 ..., 
 [1 0 1 ..., 1 1 1]
 [0 1 1 ..., 1 1 1]
 [1 1 1 ..., 1 1 1]] <<1023の2進数((1111111111))


正解値のtrYは101~1023までのfizzbuzz値のバイナリ表現
trY= 
[[1 0 0 0] <<101:5でも3でも割り切れない
 [0 1 0 0] <<102:3で割り切れる
 [1 0 0 0]
 ..., 
 [1 0 0 0]
 [1 0 0 0]
 [0 1 0 0]] <<1023:3で割り切れる

ニューラルネット

入力層:10(NUM_DIGITS)ノード, 隠れ層:100(NUM_HIDDEN)ノード, 出力層:4ノード f:id:Yaju3D:20160605163528p:plain

ノードの作成

入力ノードと出力ノードはplaceholderという名前の関数で構築されます.第一引数は型,第二引数は配列の形状です。

# Our variables. The input has width NUM_DIGITS, and the output has width 4.
X = tf.placeholder("float", [None, NUM_DIGITS])
Y = tf.placeholder("float", [None, 4])

ノード重みの作成

モデルのパラメーターとなる結合重み(ノードの間をつなぐ重み)はVariables関数を利用して領域を確保します。
ニューラルネットワークで学習を行う際、ネットワークの各重みの初期値は乱数により決定することが一般的となっている。
重み初期化:正規分布(ガウス分布)による乱数で初期化(平均 0.0, 分散 0.01)

def init_weights(shape):
    return tf.Variable(tf.random_normal(shape, stddev=0.01))

# Initialize the weights.
# モデルパラメータ(入力層:10ノード, 隠れ層:100ノード, 出力層:4ノード)
w_h = init_weights([NUM_DIGITS, NUM_HIDDEN])
w_o = init_weights([NUM_HIDDEN, 4])

予測式(モデル)を定義

def model(X, w_h, w_o):
    h = tf.nn.relu(tf.matmul(X, w_h))
    return tf.matmul(h, w_o)

# Predict y given x using the model.
# 予測式(モデル)
py_x = model(X, w_h, w_o)

入力した値を0から1の間に収めてくれる関数として八百屋で識別問題の際にシグモイド曲線を使いました。 今回は隠れ層の活性化関数としてReLU(ランプ関数)を使用します。 f:id:Yaju3D:20160605005559p:plain
プラスならどこでも一定の勾配になります。中間層で0未満の値を0にするいうことでモデルの精度を上げる目的。

qiita.com なんでシグモイド曲線ではなく、ReLU使っているのか分かるかも知れません。

誤差関数と最適化手法を記述

tf.reduce_mean()は、平均を計算する関数。

# We'll train our model by minimizing a cost function.
# 誤差関数(loss)
cost = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(py_x, Y))
# 最適化手段(最急降下法)
train_op = tf.train.GradientDescentOptimizer(0.05).minimize(cost)
  • 誤差関数を変更
    多クラス識別(分類)問題
    →多クラス用クロスエントロピー(softmax_cross_entropy_with_logits)

モデルの評価

tf.argmaxは、いくつかの軸に沿ったテンソルで最大値となるインデックスを一つ返す。

# And we'll make predictions by choosing the largest output.
# 1に一番近いインデックス(予測)が正解とあっているか検証
predict_op = tf.argmax(py_x, 1)

fizz-buzz値の出力

predict_opのインデックスからfizz-buzz値を出力する。

# Finally, we need a way to turn a prediction (and an original number)
# into a fizz buzz output
def fizz_buzz(i, prediction):
    return [str(i), "fizz", "buzz", "fizzbuzz"][prediction]

セッションを準備し,変数を初期化

一般的な初期化処理

BATCH_SIZE = 128

# Launch the graph in a session
with tf.Session() as sess:
    tf.initialize_all_variables().run()

訓練開始

10000回繰り返す。 トレーニングデータは順番に並んでいるが、それでは面白くないのでランダムに並び替えている。
np.random.permutationは、配列をランダムに並び替える(多次元配列のときは、第1軸の方向だけでランダム入れ替え)

ミニバッチのバッチサイズ(BATCH_SIZE)を「128」としています。
利用した学習データに対して更新を終えるのが、1エポックというサイクルになります。通常は、このエポックを何回か繰り返して学習していきます。 ただ、単純に繰り返しているとあまりよろしくないので、エポックの度に学習データをシャッフルしたり、ミニバッチの場合はミニバッチの取得位置をずらしたりランダムにサンプリングしたりします。
len(trX)は、1024-101=923なので、startの値は(0,128,256,384,512,640,768,896)となります。

    for epoch in range(10000):
        # Shuffle the data before each training iteration.
        p = np.random.permutation(range(len(trX)))
        trX, trY = trX[p], trY[p]

        # Train in batches of 128 inputs.
        for start in range(0, len(trX), BATCH_SIZE):
            end = start + BATCH_SIZE
            sess.run(train_op, feed_dict={X: trX[start:end], Y: trY[start:end]})

学習データの出力

np.meanは、平均を計算する関数、sess.runには実行結果の値が入ります。
np.mean(1==1)は「1.0」、np.mean(1==0)は「0.0」となります。

        # And print the current accuracy on the training data.
        if epoch % 100 == 0:
            print(epoch, np.mean(np.argmax(trY, axis=1) ==
                             sess.run(predict_op, feed_dict={X: trX, Y: trY})))

※Jupyter Notebook上で動かす際にprintを100単位としました。

予測出力

101から1023までのデータで学習した結果から、1から100までの答えの予測を出力する。

np.transposeは、転置行列にします。
numpy.vectorizeは配列を引数に取って配列として返す関数を作るもの。

    # And now for some fizz buzz
    numbers = np.arange(1, 101)
    teX = np.transpose(binary_encode(numbers, NUM_DIGITS))
    teY = sess.run(predict_op, feed_dict={X: teX})
    output = np.vectorize(fizz_buzz)(numbers, teY)

    print(output)

np.transposeのサンプル

numbers = np.arange(1, 4)
print(np.transpose(binary_encode(numbers, NUM_DIGITS)))

[[1 0 0 0 0 0 0 0 0 0]
 [0 1 0 0 0 0 0 0 0 0]
 [1 1 0 0 0 0 0 0 0 0]]

最後に

処理を分解してみて何となくやっていることは分かりましたが、まだまだしっくりとはいっていません。
基礎的な理解がまだ足りていないので、分かったら記事を修正していきます。
ディープラーニング入門としては、Fizz-Buzz問題はいいと思います。