11/29 第8回 数値解析, パターン認識

前回までの補足

• 講義のスライド(PDF形式)は，cfiveの「情報科学(水4)」のコースの「教材」のところからダウンロード可能にしてある．講義受講者以外への再配布は許可されないので注意すること．

スライドの補足

• 木を使わない併合整列法の例をあげる．なお，xs[l..u]は配列xsの添字(負の時は後ろから何番目か)lか らuまでの部分配列を得る記法で，配列xsと配列ysに対して xs+ys のようにしている 部分は配列の連結を表している．

  def merge(xs1,xs2)
    if xs1.length == 0
      xs2
    elsif xs2.length==0
      xs1
    elsif xs1[0]< xs2[0]
      xs1[0..0] + merge(xs1[1..-1],xs2) 
    else
      xs2[0..0] + merge(xs1,xs2[1..-1])
    end
  end
  def merge_sort xs
    if xs.length <= 1
      xs
    else
      len2=xs.length/2-1
      merge (merge_sort xs[0..len2]),(merge_sort xs[(len2+1)..-1])
    end
  end
  

• Euler法とRunge-Kutta法のそれぞれでsqrt 2を計算するプログラムは以下のようになる(どのような微分方程式を解いているかは自分で考えること)．euler(100)とrunge_kutta(100)を計算して真の値とどの程度ずれているかを比較すること．

  def euler(n)
    y = 1.0
    h = 1.0/n
    for i in 0..n-1
       y = y + (1.0/(2*y))*h
    end
    y
  end
  
  def runge_kutta(n)
    y = 1.0
    h = 1.0/n
    for i in 0..n-1
       k1 = (1.0/(2*y))*h
       k2 = (1.0/(2*(y+k1)))*h
       y = y + (k1+k2)/2.0
    end
    y
  end
  

• 今日配布したスライドのサンプルプログラムでは，「一文字の類似度を表すメソッド」の名前がpになっているが，組み込み関数と名前が衝突するので，サンプルではqと置き換えた．

10/25の課題について

スライドに使われたプログラム

一文字の類似度を返すメソッドq

# s0のi-1文字目とs1のj-1文字目の
# 類似度を返す
def q(i,j)
  if $s0[i-1] == $s1[j-1]
    return 2
  else
    return -1
  end
end

トレースバック

i = m;  j = n
while i>0 && j>0
  if a[i][j] == a[i][j-1] + g
    gap0[i] += 1;  j -= 1
  elsif a[i][j] == a[i-1][j-1] + q(i, j)
    i -= 1;  j -= 1
  elsif a[i][j] == a[i-1][j] + g
    gap1[j] += 1;  i -= 1
  end
end

トレースバックの表示

for i in 0..m-1
  for k in 1..gap0[i]
    print "-"
  end
  print $s0[i..i]
end
puts ""

前向きアルゴリズム

for i in 0..nn-1
  a[0][i] = $init[i]*$out[i][input[0]]
end
for t in 1..tt-1
  for i in 0..nn-1
    p = 0.0
    for j in 0..nn-1
      p += a[t-1][j]*$trans[j][i]
    end
    a[t][i] = p*$out[i][input[t]]
  end
end
r = 0.0
for i in 0..nn-1
  r += a[tt-1][i]
end

Viterbiのアルゴリズム

for i in 0..nn-1
  d[0][i] = $init[i]*$out[i][input[0]]
end
for t in 1..tt-1
  for i in 0..nn-1
    p = 0.0;  k = 0
    for j in 0..nn-1
      if (d[t-1][j]*$trans[j][i] > p)
        p = d[t-1][j]*$trans[j][i];  k = j
      end
    end
    d[t][i] = p*$out[i][input[t]];  prev[t][i] = k
  end
end
r = 0.0;  m = 0
for i in 0..nn-1
  if (d[tt-1][i] > r)
    r = d[tt-1][i];  m = i
  end
end

今日の課題

• CFIVEに入って， コース選択で，「情報科学(水4)」を選択して下さい．
• 課題機能を使って，「11/29課題」(11/29 15:00から公開)に回答してください．
• 提出は12/20(水) 21:00まで．それ以降もcfiveを使って提出可能だが，6割を上限に採点する．