MIT OCW, Machine Learning 04日目 宿題

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Assignments

Problem Set 1

Section A: Background

1.

$n$人の集団で,少なくとも二人が同じ誕生日である確率を計算する関数birthday_prob(n)を書け.(Matlab指定だったがPythonでやる)

答案

import math
def birthday_prob(n):
    # n人全員の誕生日が違う場合の数は365Cn x n!. また,n人の誕生日の場合の数は365^n
    comp = (math.factorial(n)*math.factorial(365))/(math.factorial(365-n) * math.factorial(n))
    total = 365**n

    return 1 - comp/total

birthday_prob(23)
-> 0.5072972343239854

2

$X_1, ..., X_n$ はi.i.d.で,$(0, 1)$上のUniform distributionに従うとする.
(a)$E[\max(X_1, ..., X_n)]$, (b)$E[\min(X_1, ..., X_n)]$を求めよ.
答案

確率論でやった.
(a) $X= \max(X_1, ..., X_n)$とする.
$X \leq x \Leftrightarrow (X_1 \leq x) \land ... \land (X_n \leq X)$
独立性より$P(X \leq x) = P(X_1 \leq x) P(X_2 \leq x) ...P(X_n \leq X) = x^n$
PDFは$nx^{n-1} \text{a.e.}$よって
$$E[X] = \int_0^1 xnx^{n-1} = \frac{n}{n+1}$$
(b) $Y = \min(X_1, ..., X_n)$とする.
$$\begin{aligned}X \leq y &\Leftrightarrow P(x \leq X_1)P(x \leq X_2)...P(x \leq X_n) \\ &= (1-P(X_1 < x))...(1-P(X_n < x)) \ \ \ &\text{(独立性)} \\ &= (1-P(X_1 \leq x))...(1-P(X_n\leq x)) &\text{CDFの連続性}\\&=(1-x)^n \end{aligned}$$
PDFは$-n(1-x)^{n-1} \text{ a.e.}$よって
$$E[Y] = \int^1_0 -n(1-x)^{n-1}x dx=\frac{1}{n+1}$$

3.

16の二人組があって,計32人のうち4人が風邪を引いてしまう.このときまだ組める二人組の数の期待値を求めよ.
答案

全ての事象の場合の数$\ _{32}C_4= 35960$
- 2つの組が全員風邪を引く場合の数: $\ _{16} C_2=120$
- 1つの組が二人風邪を引き,もう２つの組が一人づつ風邪を引く場合の数: $16 \times \ _{15}C_2 \times 2 \times 2 = 6720$
- 4つの組で一人づつ風邪を引く場合の数: $\ _{16}C_4 \times 2^4 = 29120$

以上より求める期待値は$(14 \times 120 + 13 \times 6720 + 12 \times 29120) / 35960 = \frac{378}{31}$

4 (Monty Hall)

3つのドアがあって,そのうち1つは当たり,他の２つは外れである. 1つのドアを選ぶと,Monty Hallは他の２つのドアのうち外れのドアを一つだけ教えてくれて,さらにもう一度ドアを選び直させてくれる.
(a) ドアを最初に選んだドアから選び直すべきだろうか？
(b) この試行を1000回おこなうプログラムを書き,結果を説明せよ.
(c) ドアを4つに増やしたほかは同じゲームを考える. 最初に選んだドアからドアを選び直すべきだろうか? そのとき, どのドアを改めて選ぶべきだろうか?
答案.

(a)
最初に選ぶドアを$A$,もう２つのドアを$B,C$とする.$1$で当たり,$0$ではずれ,$-1$でMontyがドアを選ぶという事象を表すことにする.
$P(A=1)=P(B=1)=P(C=1)=1/3$.
$\begin{aligned}P(A=1|B=-1) &=P(A=1 \land B=-1)/P(B=-1) \\ &= (\frac{1}{3} \times \frac{1}{2}) /(\frac{1}{3} \times (\frac{1}{2}+1)) = \frac{1}{3} \end{aligned}$
$\begin{aligned}P(C=1|B=-1) &=P(C=1 \land B=-1)/P(B=-1) \\ &= (\frac{1}{3} \times 1) /(\frac{1}{3} \times (\frac{1}{2}+1)) = \frac{2}{3} \end{aligned}$
$\because P(B=-1) = \sum_{X \in \{A, B, C\}}P(B=-1|X=1)P(X=1)$
だから,ドアを選び変えたほうが良い.
(b)

def monty_trial(change = True):
    # ドアを0, 1, 2とする. 当たりのドアは毎回ランダムに生成され,最初に0のドアを選ぶとする.
    success = random.randint(0, 2)
    chosen = 0

    # 当たりのドアによって場合分けする.
    if success == 0:
        monty = random.randint(1, 2) # モンティがひらくドア
    elif success == 1:
        monty = 2
    else:
        monty = 1

    if change:
        chosen = 3 - monty

    if success == chosen:
        return 1
    else:
        return 0


cnt0 = 0
cnt1 = 0
for i in range(1000):
    cnt0 += monty_trial(True)
    cnt1 += monty_trial(False)

print(cnt0/1000)
print(cnt1/1000)

->

0.663
0.361

から, 確かに理論的な値に近い.

(c) (a)と同じ理由でドアを選び変えるべきだが,対称性から,どちらのドアを選んでも同じ.

5

(a) $X$は正規分布のベクトルで
$$E[X] = (10, 5)^T, cov(X) = \left(\begin{array}{} 2 & 1 \\ 1 & 1 \end{array}\right)$$
とする. $X$のpdfを,joint PDF $P(x_1, x_2)$の形で書け.
(b) $A, B$は$p \times q$行列で,$x$は$q$次元のrandom variable vectorとする.
$$cov(Ax, Bx) = Acov(x) B^T$$
を示せ.

答案.

(a)
確率論で学んだ定義(def. 15-2)を書くと,
$$\begin{aligned}f_X(\mathbf{x})&= \frac{1}{\sqrt{(2\pi)^n |\det V|}} \exp\left[ -\frac{(\mathbf{x}-\mu)V^{-1}(\mathbf{x}-\mu)^T}{2}\right] \\ &= \frac{1}{2\pi} \exp \left[-\frac{(x_1-10, x_2-5) \left(\begin{array}{} 1 & -1 \\ -1 &2 \end{array}\right) (x_1-10, x_2-5)^T}{2} \right] \\ &= \frac{1}{2\pi} \exp(-(x_1^2 -2x_1x_2 - 10x_1 +2x_2^2 + 50)) \end{aligned}$$
が成立する.

(b)
$$\begin{aligned} cov(Ax, Bx) &= E[(Ax-E[Ax])(Bx-E[Bx])^T] \\ &= E[(Ax-AE[x])(Bx-BE[x])^T] \\ &= E[Axx^TB^T - AxE[x]^TB^T - AE[x] x^T B^T + AE[x]E[x]^T B^T] \\ &= AE[xx^T]B^T =Acov(x)B^T \end{aligned}$$

6

Gram-Schmidtの直行化法を使って,
$(0,0,0,0,0,1)^T, (1,2,3,4,5,6)^T, (1,4,9,16,25,36)^T, (1,0,0,0,0,0)^T$を正規直行化せよ

答案.
>

import numpy as np
def GS(arrays):
    n = len(arrays)
    dim = len(arrays[0])

    us = []

    for i in range(n):
        u_proto = arrays[i]
        for j in range(i):
            u_proto = u_proto - us[j] * np.dot(us[j],arrays[i])
        us.append(u_proto/np.linalg.norm(u_proto) )

    return us

GS([np.array([0,0,0,0,0,1]), np.array([1,2,3,4,5,6]), np.array([1,4,9,16,25,36]), np.array([1,0,0,0,0,0])])

->

[array([ 0., 0., 0., 0., 0., 1.]),
array([ 0.13483997, 0.26967994, 0.40451992, 0.53935989, 0.67419986, 0. ]),
array([-0.40396119, -0.54653573, -0.42772361, -0.04752485, 0.59406057, 0. ]),
array([ 0.9047837 , -0.28420368, -0.25125253, -0.10159938, 0.16475576, 0. ])]