%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	g-2008 ���c�@�t
%	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{���c�@�t}
\eauthor{Kanaderu Fukuda}
\course{�J�@������}
\year{19}
\abstract{%
���k�ɂ��f�[�^�Ԃ̗ގ��x�Ɋւ��鋗������`����ADNA�̗ގ��x�⌾��̗ގ��x�A���y�̗ގ��x����ɗL�p���Ƃ����������ʂ������Ă���B��N�A�x���A����A�֍�����Kolmogorv�L�q�ʂ�p���������̗ގ��x���͂ɑ΂��āA�����R�[�h��O�������̈Ⴂ�̔�r�������s�������A�{�����ł͎����f�[�^�̎����Ǎ�����؂̕]�����@��A���k���@�̈Ⴂ�ɂ��ǉ��������s���B}

\begin{document}

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

\begin{multicols}{2}

\section{�͂��߂�}
���ݗl�X�Ȏ������f�[�^������Ă���B�������A���y�╶�͂��u�f�[�^�v�Ƃ��Ĉ�����悤�ɂȂ��Ă��Ă���B�ߔNMing Li�炪Kolmogorov�L�q�ʂɊ�Â��f�[�^�Ԃ̗ގ��x�Ɋւ��鋗����\��similarity metric�𔭈āi����DNA�̗ގ��x�⌾��̗ގ��x�A���y�̗ގ��x����ɗL�p���Ƃ������Ƃ��������Ă���B�j�����B\\
�@��N�A�x���A����A�֍�����Kolmogorv�L�q�ʂ�p���������̗ގ��x���͂ɑ΂��āA�����R�[�h�A�O�����A�N���X�^�����O�̈Ⴂ�ł̌������s�������A�{�����ł́A�����̎����œ���ꂽ�f�[�^���A�V�����h���S���X�s�[�`�iScanSoft�j�Ƃ��������F���\�t�g�ŉ����f�[�^���e�L�X�g���������̂Ƃ̔�r�A�؂̕]�����@�∳�k���@�ɂ��Ⴂ�AQuartet Method�̃v���O���������ǂ��A���������؂̃O���t��ǂݍ��݁A��������؂ɑ΂��đ�����s���ǉ������Ƃ���B\\
�@��Q�͂ł�Kolmogorov�L�q�ʂɂ��āA��R�͂ł�Similarity metric�ɂ��āA��S�͂ł́AQuartet Method�ɂ��Ă̐��������A��T�͂ł͖؂̕]���Ɋւ��Ă̒�`���A��U�͂ł͎����T�v�A�����f�[�^�ɂ��āA��V�͂ł͎������ʁA�l�@���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�ǂ�ȃv���O���������I��ł��A���ꂪ�Ó��ł���Ώ��ʂ͒萔���̍������Ȃ����Ƃ��ؖ�����Ă���B$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{K�̃A���S���Y���I����}
$K(x)$�𐳂̐������琳�̐����ւ̊֐��ƍl����B\\[0.5cm]
\fbox{�藝}\\[0.5cm]
(a) �֐�$K(x)$�͋A�[�I�ł͂Ȃ��B�������A�ǂ̂悤�ȋ@�\�I�����֐�$\phi(x)$���l���Ă��A�������̒l�������̓_�Œ�`����Ă���̂Ȃ�΁A���̒�`���̂ǂ����̓_��$\phi(x)\not=K(x)$�ƂȂ�B\\[0.5cm]
 (b)����$t$�ɑ΂��Ă͒P�������Łi�S��I�ȁj�@�\�I�֐�$H(t,x)$�����݂�,$\lim_{t \to \infty} H(t,x)=K(x)$�B���Ȃ킿�A$K(x)$�̗ǂ��ߎ��i��������l�ߎ��ł͂Ȃ��j�͌v�Z�\�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{Quartet Method}
���ɁC���ʂ̕\�����@�ɂ��ďq�ׂ�D���̎����ł́C�gquartet method�h�Ƃ�
���n�����̈��p���Ă���D�gquartet�h�Ƃ́C�Q�̗t�����Q��subtree
���A�������O���t���w��(Figure1)�D����n�̃f�[�^�W����S�Ƃ����Ƃ��C
$S\ni u,v,w,x$�ɑ΂���quartet��$uv|wx$�ƕ\������D
�g$|$�h��2��subtree�ɕ�������邱�Ƃ�\���Ă���D

\begin{center}
\includegraphics[width=5cm,height=5cm]{quartet.eps}
\end{center}
\centerline{Figure1:quartet}

quartet�ɑ΂���cost�����̂悤�ɒ�`����D\\
\begin{eqnarray}
C_{uv|wx}=d(u,v)+d(w,x)
\nonumber
\end{eqnarray}


�܂��C�����T���^����ꂽ�Ƃ��Cu����v�܂ł̕ӂ�w����x�܂ł̕�
�������Ȃ��悤��$uv|wx$�̂��Ƃ��gconsistent�h�ƌĂ�(Figure2)�D\\
\begin{center}
\includegraphics[width=5cm]{consistent.eps}
\end{center}
\centerline{Figure2:consistent�ȑg�ݍ��킹}

T����4�̗t��I�ׂ�3��quartet�ƂȂ�g�������l�����C���̂����̂P
���K��consistent�ƂȂ�D����consistent�ƂȂ邷�ׂĂ�quartet��cost
�̘a���C���̖؂�total cost�Ƃ���D������v�Z����ɂ�$n^{4}$�����邽�߁C
�f�[�^���������Ȃ�قǎ��Ԃ��������Ă��܂����Ƃ���_�ł���D
����total cost���������قǁC�ǂ��؂ł���D�����ŁC���̖؂ɑ΂���
minimum cost��maximum cost���v�Z���C��r���邱�Ƃɂ���D�؂�
minimum cost�Ƃ́C���ꂼ���quartet�ɑ΂���minimum cost�̘a��
���C���l��quartet��maximum cost�̘a�����̖؂�maximum cost�Ƃ�
��D�����ő�؂Ȃ��Ƃ́C���̑g�����Ŗ؂����Ȃ��Ă��悢�Ƃ������Ƃ��D
total cost�͕K���C����2�̒l�̊Ԃɑ��݂��邱�ƂɂȂ�D�����ŁC�����Ƃ�
�����؂̂Ƃ��C�܂�maximum cost�̂Ƃ�S(T)=0�C�����Ƃ��ǂ��؁C�܂�minimum
cost�̂Ƃ�S(T)=1�ƂȂ�]���֐���S(T)�Ƃ���D���̖ڕW�Ƃ��ẮC
S(T)=1�ƂȂ�؂𓾂邱�Ƃł���D�������C���̖���NP-����ł��邱�Ƃ��m���Ă���D

�����ŁC��s�����Ɋ�Â��Ė{�����͈ȉ��̂悤�ȃq���[���X�e�B�b�N��p���āCS(T)�̒l��������l�ȏ�ƂȂ�悤�Ȗ؂𓾂邱�Ƃɂ���D

\begin{enumerate}
\item n��leaf�Cn-2��inner node(����:3)�����؂������_���ɐ���
\item S(T)�̒l���v�Z
\item �ȉ���3�̂�����������_���ɑI�сC������s��(tranceform)
\begin{enumerate}
\item {\bf $leaf swap$}\\
	2��leaf�������_���ɑI�сC��������
\item {\bf $subtree swap$}\\
	2��inner node�������_���ɑI�сCsubtree���ƌ�������
\item {\bf $subtree transfer$}\\
	�����_���ɑI��leaf�C�܂���inner node��؂藣���C���̏ꏊ�ֈړ�������
\end{enumerate}
\item (2)�C(3)���J��Ԃ��CS(T)�̒l���傫���Ȃ�悤��T���X�V
\end{enumerate}

�����̑���������_���ɌJ��Ԃ��Ă��邽�߁CS(T)�̒l�̓v���O���������s���邽�тɕω�����D

\section{�؂̕]��}
�N���X�^�����O�����ďo�����؂�similarity metric�ŋ��߂��ގ��x�̋����ɉ����ďo���Ă��邩�����؂��邽�߂̕]���l���`����B\\
similarity metric�ŋ��߂��ގ��x�̋�����$sd(u,v)$�Ƃ��A�ŏ��l��$min(sd)$�A�ő�l
��$max(sd)$�Ƃ���B�܂��O���t�Ƃ��Ă݂��ꍇ�̒��_���m�̋����i�Q���_�Ԃ̕Ӑ��j��$td(u,v)$�Ƃ��A$td(u,v)$�̂����̍ŏ��l��$min(td)$�A�ő�l��$max(td)$�Ƃ���B\\
�@$td(u,v)$��ގ��x�̋����ɑΉ�������������$ntd(u,v)$�ƒ�`����B������
�ϊ��萔��$S$�Ƃ���B
\begin{displaymath}
  S=\frac{max(sd)-min(sd)}{max(td)-min(td)}
\end{displaymath}
\begin{displaymath}
  ntd(u,v)=min(sd)+S(td(u,v)-min(td))
\end{displaymath}
����炩��؂̕]���l��$TV_1$�A$TV_2$�ƂQ��ޒ�`����B$L$�͖��[�m�[�h�ł���B
\begin{displaymath}
  TV_1=\sqrt{\sum_{u,v\in L}(ntd(u,v)-st(u,v))^2}
\end{displaymath}
\begin{displaymath}
  TV_2=\sqrt{\frac{\sum_{u,v\in L}(ntd(u,v)-st(u,v))^2}{\sum_{u,v\in L}ntd(u,v)^2}}
\end{displaymath}
\\ \\ \\ \\ \\ \\ \\ \\ 
\section{�����T�v�E�����f�[�^}
�����̕��@�Ƃ��āC$S(T)$�̒l��������ȏ�ɂȂ�܂ŌJ��Ԃ����@�ōs���D
\subsection*{�����f�[�^}
��N�̖x���玁�̎g�p�����e�L�X�g�f�[�^�ƁA�����������낤�i�x�m�ʃr�[�G�X�V�[�j��V�����h���S���X�s�[�`�iScanSoft�j�Ƃ��������F���\�t�g�Ńe�L�X�g�������f�[�^���g�p����B
\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{enumerate}
\item �]�����@�ɂ��Ⴂ
\begin{center}
\includegraphics[width=7cm,height=7cm]{0.83-2_2-gyousei.eps}
\begin{displaymath}
\figurename{S(T)=0.839�@TV_1=4.554}
\end{displaymath}
\end{center}
��}�͖x�����̃e�L�X�g�f�[�^�ɑO�����Q���{���Aquartet-method�@(TV1�g�p)�ŃN���X�^�����O�������O���t�ł���B
\begin{center}
\includegraphics[width=7cm,height=7cm]{0.84-3_2-gyousei.eps}
\begin{displaymath}
\figurename{S(T)=0.849�@TV_2=0.288}
\end{displaymath}
\end{center}
��}�͖x�����̃e�L�X�g�f�[�^�ɑO�����Q���{���Aquartet-method�@(TV2�g�p)�ŃN���X�^�����O�������O���t�ł���B\\ \\
\subsection*{����1}
��̐}������ׂ�ƁA���}�Ƃ��n���I�Ɍ��ē����l�Ȓn�悪�W�����Ă����B\\
���ʓI�ɁATV2��TV1�𐳋K�����������̂��̂Ȃ̂ŁA�قƂ�Ǖς��Ȃ����Ǝv���B
\item ���k���@�ɂ��Ⴂ

\begin{center}
\includegraphics[width=7cm,height=7cm]{0.84-3_2-gyousei.eps}\
\begin{displaymath}
\figurename{S(T)=0.849�@TV_2=0.288}
\end{displaymath}
\end{center}
��}�͖x�����̃e�L�X�g�f�[�^�ɑO�����Q(bzip2)���{���Aquartet-method�@(TV2�g�p)�ŃN���X�^�����O�������O���t�ł���B
\begin{center}
\includegraphics[width=7cm,height=7cm]{0.85-3_2g-gyousei.eps}\
\begin{displaymath}
\figurename{S(T)=0.850�@TV_2=0.178}
\end{displaymath}
\end{center}
��}�͖x�����̃e�L�X�g�f�[�^�ɑO�����Q(gzip)���{���Aquartet-method�@(TV2�g�p)�ŃN���X�^�����O�������O���t�ł���B\\
\subsection*{����2}
�S�̓I�ɂ�bzip2�̕����ǂ��悤�Ɍ����邪�A\\
gzip�̕��͕����I�ɋ߂��n�擯�m���W�܂��Ă���悤�������B\\
�߂��n�擯�m���W�܂��Ă��Ă��A�����؂̌�����ړ��ɂ����
���ʓI�ɂ΂�΂�̂悤�Ɍ����Ă��܂����̂��Ǝv���B
\end{enumerate}
\section{����̉ۑ�}
\begin{enumerate}
\item �`����@�̉��P�B
\item �V���Ȗ؂̕]�����@���l����B
\item ���̊K�w�^�N���X�^�����O(NJ�@��)���Č��؂���B
\end{enumerate}
\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}



