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/totalbirthday_prob(23)
-> 0.50729723432398542
X1,...,Xn はi.i.d.で,(0,1)上のUniform distributionに従うとする.
(a)E[max(X1,...,Xn)], (b)E[min(X1,...,Xn)]を求めよ.
答案
確率論でやった.
(a) X=max(X1,...,Xn)とする.
X≤x⇔(X1≤x)∧...∧(Xn≤X)
独立性よりP(X≤x)=P(X1≤x)P(X2≤x)...P(Xn≤X)=xn
PDFはnxn−1a.e.よって
E[X]=∫10xnxn−1=nn+1
(b) Y=min(X1,...,Xn)とする.
X≤y⇔P(x≤X1)P(x≤X2)...P(x≤Xn)=(1−P(X1<x))...(1−P(Xn<x)) (独立性)=(1−P(X1≤x))...(1−P(Xn≤x))CDFの連続性=(1−x)n
PDFは−n(1−x)n−1 a.e.よって
E[Y]=∫10−n(1−x)n−1xdx=1n+1
3.
16の二人組があって,計32人のうち4人が風邪を引いてしまう.このときまだ組める二人組の数の期待値を求めよ.
答案
全ての事象の場合の数 32C4=35960
- 2つの組が全員風邪を引く場合の数: 16C2=120
- 1つの組が二人風邪を引き,もう２つの組が一人づつ風邪を引く場合の数: 16× 15C2×2×2=6720
- 4つの組で一人づつ風邪を引く場合の数: 16C4×24=29120以上より求める期待値は(14×120+13×6720+12×29120)/35960=37831
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.
P(A=1|B=−1)=P(A=1∧B=−1)/P(B=−1)=(13×12)/(13×(12+1))=13
P(C=1|B=−1)=P(C=1∧B=−1)/P(B=−1)=(13×1)/(13×(12+1))=23
∵P(B=−1)=∑X∈{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)=(2111)
とする. Xのpdfを,joint PDF P(x1,x2)の形で書け.
(b) A,Bはp×q行列で,xはq次元のrandom variable vectorとする.
cov(Ax,Bx)=Acov(x)BT
を示せ.
答案.
(a)
確率論で学んだ定義(def. 15-2)を書くと,
fX(x)=1√(2π)n|detV|exp[−(x−μ)V−1(x−μ)T2]=12πexp[−(x1−10,x2−5)(1−1−12)(x1−10,x2−5)T2]=12πexp(−(x21−2x1x2−10x1+2x22+50))
が成立する.(b)
cov(Ax,Bx)=E[(Ax−E[Ax])(Bx−E[Bx])T]=E[(Ax−AE[x])(Bx−BE[x])T]=E[AxxTBT−AxE[x]TBT−AE[x]xTBT+AE[x]E[x]TBT]=AE[xxT]BT=Acov(x)BT
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. ])]
