%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	g-2008 �r�x�@�a�L
%	tani_resume_last.syt �g�p��
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%#! platex resume.tex
\documentclass[a4paper]{jarticle}

\usepackage{tani_resume_last}

\alignbeforeskip -5mm
\alignafterskip -5mm
\eqnarraybeforeskip -5mm
\eqnarrayafterskip -5mm

\jptitle{���k�ɂ��ގ��x��p���������̎�������}
\etitle{Automatic classification of Japanese dialects using based Compression
similarity distance}
\jpauthor{�r�x�@�a�L}
\eauthor{Arahori Kazuhiro}
\course{�J�@������}
\year{19}
\abstract{%
Kolmogorov�L�q�ʂɊ�Â����f�[�^�Ԃ̗ގ��x�Ɋւ��鋗������`����ADNA�̗ގ��x�⌾��̗ގ��x�A���y�̗ގ��x����ɗL�p���Ƃ����������ʂ������Ă���B�{�����ł�Kolmogorv�L�q�ʂɊ�Â����k�������̗ގ��x���͂ɑ΂��ėL�p���ǂ����������s���B}

% �ŏI�X�V�����̑}��
\compheading

\begin{document}

% �^�C�g����\��������
\maketitle

\begin{multicols}{2}

\section{�͂��߂�}
�}���ȃR���s���[�^�[�Z�p�̔��B�ɂ��l�X��
�������d�q�I�Ƀf�[�^�Ƃ��Ĉ�����悤�ɂȂ��Ă���
����. ���̒���, ���͂≹�������R�u�f�[�^�v�Ƃ��Ĉ���
���悤�ɂȂ��Ă��Ă���B�{�����ł́A�ߔNMing Li �炪Kolmogorov �L�q�ʂɊ�Â��f�[
�^�Ԃ̗ގ��x�Ɋւ��鋗����\��similarity metric ��
�āi����DNA �̗ގ��x�⌾��̗ގ��x�A���y�̗ގ��x
����ɗL�p���Ƃ������Ƃ��������Ă���B�j���ꂽ���Ƃɂ��A��N�x�����A���쎁�A�֍����ɂ��uKolmogorov�L�q�ʂɊ�Â��ގ��x��p���������̎������ށv�œ���ꂽ�f�[�^�ƐV�����h���S���X�s�[�`�iScanSoft�j�Ƃ��������F���\�t�g�ŉ����f�[�^���e�L�X�g���������̂Ƃ̔�r�A�܂����k���@�ł�bzip2��gzip�̐��\�ɂ��ω��̔�r�A�������s���ǉ������Ƃ���B\\
�@��Q�͂ł�Kolmogorov�L�q�ʂɂ��āA��R�͂ł�Similarity metric�ɂ��āA��S�͂ł́A�N���X�^�����O�ɂ��Ă̐��������A��T�͂ł͎����T�v�A�����f�[�^�ɂ��āA��U�͂ł͎������ʂ��q�ׂ�B\\
\section{Kolmogorov�L�q�ʂ̒�`}
Kolmogorov�L�q�ʂ̊�{�I�Ȓ�`���q�ׂĂ����B

\subsection{Kolmogorov�L�q��}
�@����f�[�^$x$�����݂��A�f�[�^$x$��Kolmogorov�L�q�ʂƂ͂���v���O���������$x$�𐶐�����ŏ��̃v���O�����̃T�C�Y�ł���B������, �����Ō����f����
����v���O�����f�Ƃ͑S�Ẵ���������̏�����Ԃ���
�X�^�[�g��, ���̑Ώۂ��o�͂��Ē�~����v���O������
���Ƃł���. ���̏ꍇ, �ǂ�ȃv���O���~���O�����I
��ł�, ���ꂪ�Ó��ł���΂��̏��ʂ̍�, ���Ȃ킿
�e�v���O�����̃T�C�Y�̍��͒萔���̍������Ȃ����Ƃ�
�ؖ�����Ă���.$S$���v���O��������A$|p|$���v���O�����T�C�Y�Ƃ���ƁA�f�[�^$x$��Kolmogorov�L�q��$K_s(x)$�́A�ȉ��̂悤�ɒ�`�����B
\begin{displaymath}
  K_s(x)=min|p|:S(p)=x
\end{displaymath}
�@���Ȃ킿$K_s(x)$�́A�h�v���O��������$S$�ɂ�����$x$�𐶐�����ŏ��̃v���O�����̒����h�ƍl���Ă������낤�B\\
�@���ɑΏ�$y$���^�����Ă���Ƃ��̑Ώ�$x$�ɂ��Ă̋L�q�ʁi���΋L�q�ʁj�ɂ��čl����B������$x$���A�v�Z�\�֐��i�C���^�v���^�֐��j$f$�A����ɕ�����$p$��$y$�ɂ��$f(p,x)=x$�ƋL�q���邱�Ƃ��l����B�C���^�v���^�֐�$f$�̂��ƂŁA�⏕�֐�$y$�ɑ΂���$x$�̋L�q��$K_f$�����̂悤�ɒ�`����B
\begin{displaymath}
  K_f(x|y)=min\{|p|:P\in\{0,1\}*f(p,y)=x\}
\end{displaymath}
�@�܂��A$x$��$y$����ʂł���`�ŏo�͂�����ŒZ�̃v���O�����̒���$K(xy)$�Ƃ���킷�B$O(logK(xy))$�̌덷�͈͂ł́A
\begin{displaymath}
  K(xy)=K(x)+K(y|x)
\end{displaymath}
�ƂȂ邱�Ƃ��ؖ�����Ă���B


\subsection{����}
�@���΋L�q��$K(x|y)$����΋L�q��$K(x)$��肩�Ȃ菬�����ꍇ�A�u$y$��$x$�ɂ��Ă̏������Ԃ�Ɋ܂�ł���v�ƍl���邱�Ƃ��o����B���������āA�萔���̍��ق𖳎�����΁A�h$y$�Ɋ܂܂��$x$�̏��ʁh�� \\
\begin{displaymath}
  I(x:y)=K(y)-K(y|x)
\end{displaymath}
�Ƃ݂Ȃ����Ƃ��o����B�܂��A$K(x|x)$�ƂȂ�$x$��I�ׂ΁A
\begin{displaymath}
  I(x:x)=K(x)
\end{displaymath}
�ƂȂ�B�����ŏ��̑Ώې��Ƃ������Ƃ��l����B$OlogK(xy)$�̌덷�͈͂ł́A
\begin{displaymath}
  K(xy)=K(x)+K(y|x)
\end{displaymath}
�ł���B����������
\begin{displaymath}
  I(x:y)=I(y:x)
\end{displaymath}
����������B\\

\section{Similarity metric}
���w�ɂ����ċ�����ԂƂ́C�C�ӂ�2�_�Ԃŋ�������߂�ꂽ��Ԃ̂��Ƃ������D\\
\fbox{��`}\\
����W��$X$��̋����Ƃ́C�����l�֐�$d:X\times X\rightarrow R$�ŔC�ӂ�$x,y,z\in X$�ɑ΂��Ď��̂悤�Ȑ����𖞂����D\\
\begin{eqnarray}
&&d(x,y)\geq 0
\nonumber \\
&&d(x,y)=0\Leftrightarrow x=y
\nonumber \\
&&d(x,y)=d(y,x)
\nonumber \\
&&d(x,y)\leq d(x,z)+d(z,y) :�O�p�s����
\nonumber
\end{eqnarray}
\\
��������ƂɁC��񋗗��ɂ��čl����D

Ming Li��̌����ł́C���Ɋւ��鋗����W�������Ă���D�C�ӂ̕�����$x,y$�ɂ��āC�ȉ��̂悤�Ɍ��߂�D\\
\begin{eqnarray}
d(x,y)=\frac{max\{ K(x|y),K(y|x)\} }{max\{ K(x),K(y)\} }
\nonumber 
\end{eqnarray}
�܂��C$K(y)\geq K(x)$�Ƃ����Ƃ��C\\
\\
\begin{eqnarray}
d(x,y)&=&\frac{K(y|x)}{K(y)}
\nonumber 
\end{eqnarray}\\
����ɑ΂��Đ�ɏq�ׂ����ʂ̌�����p����ƁC\\
\begin{eqnarray}
d(x,y)&=&\frac{K(y)-I(x:y)}{K(y)}
\nonumber 
\end{eqnarray}\\
�ƂȂ�D�܂�2�߂Ŏ������ʂ�C$O(\log K(xy))$�͈̔͂ł�$K(xy)=K(x)+K(y|x)$�����藧�̂ŁC\\
\begin{eqnarray}
d(x,y)=\frac{K(xy)-K(x)}{K(y)}
\nonumber 
\end{eqnarray}\\
�ƕ\�����Ƃ��ł���D

\renewcommand{\labelenumi}{(\arabic{enumi})}

���ۂ̎����ł́C���̎��ƂƂ��Ɉȉ���3�̗��z���_�̂��Ƃɍs��ꂽ�D
\begin{enumerate}
\item �v�����ꂽ��񋗗�$d(x,y)$�͔��R�ƒ���������$x,y$�ɂ���ē�����D
\item Kolmogorov Complexity�͋A�[�I�łȂ����߁C�v�Z�s�\�ł���D
\item ���p�I�ȕ��@�ŏ�񋗗����ߎ�����ہC���k���@�̈�ł���gbzip2�h��p����D
\end{enumerate}
�ȏ���A$bzip(x)$�𕶎���$x$��bzip2�ň��k�����Ƃ��̃t�@�C���T�C�Y�Ƃ���Ə�񋗗�$d(x,y)$�͈ȉ��̂悤�ɋߎ������D\\
\begin{eqnarray}
d(x,y)��\frac{bzip(xy)-bzip(x)}{bzip(y)}
\nonumber 
\end{eqnarray}
���̋����֐������ƂɁC�f�[�^�̕��ނ�i�߂Ă����D\\

\section{�N���X�^�����O}
\subsection{NJ�@}

���ɁC���ʂ̕\�����@�ɂ��ďq�ׂ�D���̎����ł́C�gNJ�@�h�Ƃ�
���n�����̈��p���Ă���D
%\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm,height=8cm,clip]{algo.eps}
%\caption{nj-remake-preprocess2}
%\label{fig:}
\end{center}
%\end{figure} 

\subsection*{Step1}
$L$��S�Ă̗t�̏W���Ƃ��ď�����
\subsection*{Step2}
����$D_{ij}$���ŏ��ƂȂ�y�A$i,j$��I��
\begin{displaymath}
  D_{ij}=d_{ij}-(r_i+r_j)
\end{displaymath}
\begin{displaymath}
  r_i=\frac{1}{|L|-2}\sum_{k\in L}d_{ik}
\end{displaymath}
\subsection*{Step3}
�V�����ړ_$k$�����A$L$�̂��ׂĂ̗t$m$�Ƃ̋��������߂�
\begin{displaymath}
  d_{km}=\frac{1}{2}(d_{im}+d_{jm}-d_{ij})
\end{displaymath}
\subsection*{Step4}
$k$��$i,j$�Ƃ̋����́A
\begin{displaymath}
  d_{ik}=\frac{1}{2}(d_{ij}+r_i-r_j)
\end{displaymath}\begin{displaymath}
  d_{jk}=d_{ij}-d_{ik}
\end{displaymath}
\subsection*{Step5}
$i,j$��$L$���珜���A$k$��ǉ��A�Q�֖߂�
\subsection*{Step6}
$L$��$i,j$�̂Q�����ɂȂ�����A�}�𒣂��ďI��\\ 

\section{�����T�v�E�����f�[�^}

\subsection*{�����f�[�^}
1,��N�̖x���玁�̎g�p�����e�L�X�g�f�[�^.
2,�����������낤�i�x�m�ʃr�[�G�X�V�[�j��V�����h���S���X�s�[�`�iScanSoft�j�Ƃ��������F���\�t�g�Ńe�L�X�g�������f�[�^.

\subsection*{�����R�[�h}
��ʂɎg���Ă���EUC�AJIS�ASHIFT-JIS�AUTF-8���g�p����B�Ȃ����s�R�[�h�́A�S��unix�ɌŒ肳�����BEUC�AJIS�ASHIFT-JIS�͂Q�o�C�g�AUTF-8�͂R�o�C�g�̕����R�[�h�Ȃ̂Ńt�@�C���T�C�Y���ς���Ă���͓̂��R�ł���B������bzip2�Ɉ��k��simirality metric�ŗގ��x�̋��������߂�ƁA�����ɈႢ�������Ă��܂��B�����ň��k����ۂɗ]�v�ȏ�񂪓���Ȃ��悤�ɑO�����Ƃ��āA1�o�C�g�̃R�[�h�ɕϊ������邱�Ƃɂ����B\\
�@���̑O�������@���Q��ލl�Ă����B�O�����P��50������1����Ή������ĕϊ�����B�O�����Q�́A�g�p�p�x����������1����Ή������ĕϊ�����B\\
�@�����R�[�h�ɂ����EUC�AJIS�ASHIFT-JIS�AUTF-8�A�O�����P�A�O�����Q�̂U��ނ̃f�[�^�����݂��邪�Abzip2�Ɉ��k����Ƃ��ł����k�ł��Ă�����́i�ł����k��̃t�@�C���T�C�Y���������j���̂�����̌����f�[�^�Ƃ��邱�Ƃɂ����B�Ȃ��Ȃ�Akolmogorov�L�q�ʂ͈��k������̃t�@�C���T�C�Y���ł����������̂��A���kolmogorov�L�q�ʂɋߎ��ł��邩��ł���B�U��ނł͑O�����Q����Ԉ��k����Ă����邱�Ƃ��A���؂ɂ�蕪�������̂Ńf�[�^�͑O�����Q���������̂ɂ��N���X�^�����O�������B\\ \\ 

\section{��������}
\begin{center}
\includegraphics[width=7cm,height=7cm]{nj-dora-nc2.eps}\\
\figurename{nj-dora-nc2}
\end{center}
��}�̓h���S���X�s�[�`�Ńe�L�X�g�������f�[�^�ɑO�����Q���{���Anj�@�ŃN���X�^�����O�������O���t�ł���B\\ \\ \\ \\
�@
\begin{center}
\includegraphics[width=7cm,height=7cm]{nj-pre2-nc2.eps}\\
\figurename{nj-pre2-nc2}
\end{center}
��}�͖x�������e�L�X�g�����f�[�^�ɑO�����Q���{���Anj�@�ŃN���X�^�����O�������O���t�ł���B\\ \\ \\ \\ \\




\section{�Q�l����}
\begin{enumerate}
\item�@Rudi Cilibrasi and Paul Vitanyi and Ronald de Wolf�@Algorithmic Clustering of Music (2003)
\item�@Ming Li and Paul M.B.Vitanyi.�n�� �� �|��  Kolmogorov Complexity and its Applications.�@�R���s���[�^��b���_�n���h�u�b�N(1994)
\item�@�J ����@�f�[�^�̕��G���E�f�[�^�\���̕��G��
\item�@�x�� �K�i�@Kolmogorov�L�q�ʂɊ�Â��ގ��x��p���������̎������ށ@(2007)
\end{enumerate}
\end{multicols}

\end{document}



