%#! platex %f && dvipdfmxm -d 5 project230627hmm
%
%
\documentclass[a4paper,11pt,dvipdfmx]{jarticle} 
\usepackage{fancybox}
\usepackage{fancybox,ascmac}
\usepackage{array}
\usepackage[dvips,usenames]{color}  % for revise color 
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{bm}
\usepackage{slashbox}
\usepackage{ascmac} % itembox
\usepackage{amsmath} % bmatrix
\usepackage{amssymb} % leqq
\usepackage{fancybox}
\def\maru#1{\textcircled{\scriptsize#1}}
\pagestyle{empty}
\topmargin = -5mm
\oddsidemargin = 4mm
\textwidth = 150mm
\textheight = 230mm
\pagestyle{fancyplain}
\renewcommand{\footrulewidth}{0pt}
\renewcommand{\headrulewidth}{0pt}
\bmdefine{\bmu}{\mu}
\bmdefine{\bm}{m}
\bmdefine{\bx}{x}
\bmdefine{\br}{r}
\bmdefine{\bw}{w}
\bmdefine{\by}{y}
\bmdefine{\bz}{z}
\bmdefine{\ba}{a}
\bmdefine{\bb}{b}
\bmdefine{\btheta}{\theta}
\everymath{\displaystyle}
\begin{document}
\setlength{\baselineskip}{7mm}
\rhead{\small 最適化理論\\2023年6月27日
% 更新 2023年6月26日
}
\lfoot{}
% \cfoot{}

\begin{center}
{\large\bf レポート課題: ~隠れマルコフモデル}\\
提出締切 7月24日（月） 18:00
% 18日の講義までに一度はシミュレーションプログラムを作成しておくこと）
\end{center}
\vskip 3mm

口頭試問は7月14日（金）までには終わらせること．
コンピュータ・プログラムの
バグがなかなか発見できず，
課題解決が数日進まない場合がある．
そういう場合を想定して，はやめに課題に取り掛かること．


\begin{figure}[h]
\begin{center}
\includegraphics[width=.22\linewidth]{./1d-hmrf303.eps}
\caption{確率変数の依存性を描いたグラフ}
\end{center}
\end{figure}


確率的生成モデルを用いた
パターン認識について考えよう．
ここでは
与えられたデータ $\by$ からそのデータの表している内容
$\bx$ を当てるパターン認識を考える．
$\bx = (x_1,x_2,x_3)$, 
$\by = (y_1,y_2,y_3)$, 
$ x_i, y_i \in \{ 0, 1 \}$,
$ i=1,\cdots,3$ として，確率分布
$p(\bx), p(\by|\bx)$ が以下のように与えられているとする．
%
%
\begin{eqnarray}
p(x_1) = 
\mathrm{Prob} (X_1 = x_1)
%\Pr (X_1 = x_1)
& = & \left\{ \begin{array}{ll}
0.5 &  \mathrm{if}~\hspace*{1em} x_1 = 0  \\
0.5 &  \mathrm{if}~\hspace*{1em} x_1 = 1 
\end{array}
\right.
\\
p(x_{i+1} | x_i) 
& = & \left\{ \begin{array}{ll}
0.9 &  \mathrm{if}~\hspace*{1em} x_i = 0, x_{i+1}=0   \\
0.1 &  \mathrm{if}~\hspace*{1em} x_i = 0, x_{i+1}=1   \\
0.7 &  \mathrm{if}~\hspace*{1em} x_i = 1, x_{i+1}=1   \\
0.3 &  \mathrm{if}~\hspace*{1em} x_i = 1, x_{i+1}=0 
\end{array}
\right.
\\
p(y_i | x_i) 
& = & \left\{ \begin{array}{ll}
0.8 &  \mathrm{if}~\hspace*{1em} x_i = y_i \\
0.2 &  \mathrm{if}~\hspace*{1em} x_i \neq y_i
\end{array}
\right.
\end{eqnarray}
%
したがって
\begin{eqnarray}
p(\bx) & = & p(x_1, x_2, x_3) = p(x_1)p(x_2|x_1)p(x_3|x_2) =
 p(x_1) \mathop{\prod}_{i=1}^{2} p(x_{i+1} | x_i )\\
p(\by|\bx) & = & p(y_1, y_2, y_3 | x_1, x_2, x_3) \\
& = & p(y_1|x_1)p(y_2|x_2)p(y_3|x_3)\\ 
& = & \mathop{\prod}_{i=1}^{3}p(y_i|x_i) \\
p(\bx,\by) & = & p(\bx)p(\by|\bx)
\end{eqnarray}
とかける．
これらの式は図1をイメージすると理解しやすい
（各項が一本の枝に対応）．


確率分布$p(\bx)$について考えよう．
ベクトル$\bx = (x_1,x_2,x_3) $の
各要素 $x_i$は$0,1$の値をとる．
したがって $\bx$は8通りの「状態」を取り得る．
それぞれの状態が出現する確率を足すと$1$になるため，
確率分布$p(\bx)$は，7つのパラメータの値を決めれば，どんな分布であっても指定できる．
しかし，ここでは
$0.5,0.9,0.7$という3つのパラメータ値だけを指定したことに注意したい．
音や画像のような高次元データを扱う場合には，
場合の数が大きくなり，一つ一つの状態の確率を指定することは
現実的にはできないため，このようなモデル化がよくおこなわれる．
なお $p(\bx)$をモデルもしくは事前確率，
$p(\by|\bx)$をデータモデルとよぶ．


\vskip 10mm

\noindent
{\gt 練習問題（手計算．理解度合いの確認用．提出する必要なし）}

\begin{enumerate}
\item $\bx=(0,0,0) $ とする．確率 $p(\bx)$ を求めよ．

\vskip 10mm

\item $\bx=(0,1,0) $ とする．確率 $p(\bx)$ を求めよ．

\vskip 10mm

\item $\bx=(0,0,0), \by=(0,1,0) $ であった． 同時確率 $p(\bx, \by)$ を求めよ．

\vskip 10mm

\item $\bx=(0,1,0), \by=(0,1,0) $ であった． 同時確率 $p(\bx, \by)$ を求めよ．

\vskip 10mm

\item $ \by=(0,1,0) $ であった．$\bx_0 = (0,0,0)$ とするとき
事後確率 $p(\bx_0 | \by)$ を求めよ．

\vskip 10mm

\item $ \by=(0,1,0) $ であった．$\bx_2 = (0,1,0)$ とするとき
事後確率 $p(\bx_2 | \by)$ を求めよ．


\vskip 10mm


\item  $ f(x) = -(x-1)^2 $ とする
\begin{enumerate}
\item $\mathop{\rm max}_x  f(x) $ を求めよ．
\item $\mathop{\rm argmax}_x  f(x) $ を求めよ．
\end{enumerate}

\item $ \by=(0,1,0) $ であった．事後確率を最大にする$\bx_{\mathrm{MAP}}$を求めよ．
%
\begin{eqnarray}
\bx_{\mathrm{MAP}}
& = &
{\displaystyle \mathop{\rm argmax}_{\bx} p( \bx | \by ) }
\end{eqnarray}

\end{enumerate}


\rhead{}


\vskip 20mm


\noindent
{\gt 基本課題 （必須）}

以下では $\bx, \by$ともに，
$n=200$次元のベクトルとする．
$ x_i \in \{ 0, 1 \}, i=0,\cdots,199$，
$ y_i $ は実数とする．
確率分布
$p(\bx)$，確率密度関数
$p(\by|\bx)$ が以下のように与えられているとする．
%
%
\begin{eqnarray}
p(x_0) = 
\mathrm{Prob} (X_0 = x_0)
%\Pr (X_1 = x_1)
& = & \left\{ \begin{array}{ll}
0.5 &  \mathrm{if}~\hspace*{1em} x_0 = 0  \\
0.5 &  \mathrm{if}~\hspace*{1em} x_0 = 1 
\end{array}
\right.
\\
p(x_{i+1} | x_i) 
& = & \left\{ \begin{array}{ll}
0.99 &  \mathrm{if}~\hspace*{1em} x_i = 0, x_{i+1}=0   \\
0.01 &  \mathrm{if}~\hspace*{1em} x_i = 0, x_{i+1}=1   \\
0.97 &  \mathrm{if}~\hspace*{1em} x_i = 1, x_{i+1}=1   \\
0.03 &  \mathrm{if}~\hspace*{1em} x_i = 1, x_{i+1}=0 
\end{array}
\right.
\\
p(y_i | x_i ) & = &
\frac{1}{\sqrt{2\pi} \sigma}
\exp \left \{ -\frac{(y_i-x_i)^2}{2\sigma^2} \right \} %  \Delta y
\end{eqnarray}
ここで以下の課題では，特に指定しない限り $ \sigma = 0.7$とする．

\begin{enumerate}
\item  確率分布$p(\bx)$にしたがう$\bx=(x_0,\cdots,x_{199})$ を確率的に生成せよ．
10例を生成し，まとめて1枚の図に表示しなさい．
       一つ一つのグラフが重ならないように，
       $\alpha$番目の$\bx$は，縦軸の値を
       $ x_i + 3\alpha $ として表示せよ（$\alpha=0,\cdots,9$）．
\vskip 5mm

 \item 前問と同様に$\bx$を一つ生成し（これを$\bx_{\mathrm{org}}$とする），
上記 $p(\by|\bx)$を用い，$\by_{\mathrm{obs}}$ を生成せよ．
$\bx_{\mathrm{org}}$としては，
なるべく異なる状態に遷移する回数が多いものを用いることが望ましい．
$\bx_{\mathrm{org}}$は線で，$\by_{\mathrm{obs}}$は点で，重ねて1枚の図に描きなさい．

\vskip 5mm

\item 事後確率を最大にする$\bx_{\mathrm{MAP}} = 
{\displaystyle \mathop{\rm argmax}_{\bx} p( \bx | \by_{\mathrm{obs}} ) }
$
を動的計画法を用いて求める方法を，簡潔に説明できるようにしなさい．
できるようになったら口頭試問を受けること．
      
\vskip 5mm

 \item 事後確率を最大にする
$\bx_{\mathrm{MAP}} $ 
%{\displaystyle \mathop{\rm argmax}_{\bx} p( \bx | \by_{\mathrm{obs}} ) }
を動的計画法を用いて求め，
$ \bx_{\mathrm{org}}$, $\by_{\mathrm{obs}}$,
$ \bx_{\mathrm{MAP}}$ を
重ねて1枚の図に描きなさい．
ここで $\bx_{\mathrm{MAP}}$については，
% 重なり合って判別しにくいため
各要素の値に $+2$を
加えたものを表示せよ．
%
また $\bx_{\mathrm{org}}$と$\bx_{\mathrm{MAP}}$ のハミング距離
$d (\bx_{\mathrm{org}}, \bx_{\mathrm{MAP}})$ を求めよ．
ここで
\begin{eqnarray}
d (\ba , \bb)
& = & \sum_{i=0}^{199} | a_i - b_i | 
\end{eqnarray}
とする．
最低 3例について図を作成せよ．

 % \item 4. について，

	     \vskip 5mm


\item[***] web上に，作成したプログラムが正しく作動しているかチェッ
	   クする，テスト用のデータを用意している．\\
\hspace*{-10mm}{\footnotesize\tt https://raw.githubusercontent.com/date333cs/courses/master/optimization\_theory/r20190702\_20\_test\_cases}

\newpage
\noindent
\hspace*{-10mm}{\gt 応用課題 （できるところまででOK）} 

\item  確率分布$p(\bx,\by)$にしたがう$\bx_{\mathrm{org}}$ と
$\by_{\mathrm{obs}}$ を生成し，
$\by_{\mathrm{obs}}$とモデル$p(\bx), p(\by|\bx)$ のみを用い
$\bx_{\mathrm{MAP}}$を求め，
       ハミング距離$d (\bx_{\mathrm{org}}, \bx_{\mathrm{MAP}})$ を計算せよ
       （ここまでは 4. と同じ）．
これを1000回繰り返し，
ハミング距離のヒストグラムを描きなさい．
また，ハミング距離の平均値と分散を求めよ．


\item $\sigma$ の値を $0.3$ から $2.0$ の $0.1$ 刻みで変え，
前問の実験をおこない，横軸に$\sigma$，
縦軸にハミング距離の平均値$\pm$標準偏差をプロットした図を作成せよ．



\item 
$\bx_{\mathrm{org}}$ を生成したモデルと異なるモデルを用いて
$\bx_{\mathrm{MAP}}$を求めた場合，
認識性能が低下することが期待される．
どのくらい性能が低下するか調べてみよう．
たとえば，
$\bx_{\mathrm{org}}$ を生成したときの$p(\bx)$を使って
$\bx_{\mathrm{MAP}}$を求めた場合と，
それとは異なるモデル
\begin{eqnarray}
q(x_{i+1} | x_i) 
& = & \left\{ \begin{array}{ll}
\theta &  \mathrm{if}~\hspace*{1em} x_i = 0, x_{i+1}=0   \\
1-\theta &  \mathrm{if}~\hspace*{1em} x_i = 0, x_{i+1}=1   \\
\theta &  \mathrm{if}~\hspace*{1em} x_i = 1, x_{i+1}=1   \\
1-\theta &  \mathrm{if}~\hspace*{1em} x_i = 1, x_{i+1}=0 
\end{array}
\right.
\end{eqnarray}
を使って
$\bx_{\mathrm{MAP}}$を求めた場合を比較してみればよい．
ここでは，$\sigma=0.7$とし，データモデルは$p(\by|\bx)$は固定しておく．
前問と同様に，同じ条件で1000回実験を繰り返し，
横軸に$\theta$を
$ 0.7 < \theta < 1.0 $ において$0.05$きざみで，
縦軸にハミング距離の平均値$\pm$標準偏差をプロットした図などを
描けばよい．

 \item 一つのプログラミング言語でプログラムが書けたら，
       プログラムを美しく書き直したり，
       別のプログラミング言語で書き直したりしてみよ．
       GUI を作るのもよい．
       

\item 事後確率 $ p(\bx_{\mathrm{MAP}} | \by) $ を計算するプログラムを書
      く．（A-333まで相談しにくる）
       
 \item そのほか自分で考えた問題設定，講義で紹介した問題など．
       

\end{enumerate}




\vskip 5mm

レポートの最後には，感想，質問などを記述してほしい．
理解しにくい点があった場合は，
このプリント中の，どこの部分が
分かりにくかったか，
具体的に，指摘してもらえれば大変助かる（来年度向けに改善するため）．
\vskip 5mm



\noindent
{\gt レポート提出先：} ~ {\tt WebClass}：
% 「学籍番号＋名前」をファイル名にした 
pdf ファイル
% （例：60217777date.pdf）
をアップロード\\




\end{document}

