2009-8 第4問 (2)

決定木の学習では訓練データを何らかの指標に基づいて幾つかの集合に分割し、分割したそれぞれのデータを部分木とする木を作成する。それぞれの部分木に対しても再帰的に分割を行い、最終的な木構造を得る。
良い決定木を得るためには訓練データの分割の指標の定め方が問題となる。この指標の定め方には様々な種類があり、例えばID3やC4.5と呼ばれる手法では情報量(エントロピー)を基に指標を定める。

2009-8 第4問 (1)

事象Aの確率(事前確率)をP(A)とし、条件Aの下で事象Bが成立する確率(事後確率・条件付き確率)をP(B|A)とする。
このとき、P(B|A)はP(A), P(B), P(A|B)を用いて次のように記述できる。
    P(B|A) = P(A|B) * P(B) / P(A)

ベイズの定理はベイズ統計学の基礎であり、迷惑メールのフィルタリングなど、様々な応用がなされている。

2009-8 第3問 (5)

X = { x_i }, Y = { y_i }, Z = { z_i }, Z = X + Y とすると、

z₀ = x₀ ∧ y₀
z₁ = x₁ ∧ y₀ ⊕ x₀ ∧ y₁
z₂ = x₂ ∧ y₀ ⊕ x₁ ∧ y₁ ⊕ x₀ ∧ y₂ ⊕ x₀ ∧ x₁ ∧ y₀ ∧ y₁
...

のように、任意のiに対してz_iはx₀,...,x_i-1とy₀,...,y_i-1で表せる。

各論理積の計算は並列的に計算可能であり、それぞれの計算コストはO(logN)
排他的論理和の計算コストもO(logN)なので、全体の計算コストはO(logN)

2009-8 第3問 (4)

 

2009-8 第3問 (3)