%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	tani_resume.syt �g�p��
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%#! platex midi_mid.tex
\documentclass[a4paper]{jarticle}

\usepackage{tani_resume_last}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{epsfig}
\usepackage{color}

\renewcommand{\labelenumi}{(\alph{enumi})}
\alignbeforeskip -5mm
\alignafterskip -5mm
\eqnarraybeforeskip -5mm

\eqnarrayafterskip -5mm

\jptitle{Kolmogorov�L�q�ʂ�p����MIDI�̕���}
\etitle{Clustering of MIDI with Kolmogorov Complexity
\\{\tt http://www.tani.cs.chs.nihon-u.ac.jp/g-2006/fukumori/}}
\jpauthor{���X�@��}
\eauthor{Tsutomu Fukumori}
\course{�J ������}
\year{17}
\abstract{%
����܂łɉ��y�������I�ɕ��ނ���l�X�Ȏ�@����Ă���Ă����DMing Li���
Kolmogorov �L�q�ʂɊ�Â���similarity metric���Ă��CRudi Cilibrasi
���similarity metric��p���ĉ��y���������ނ����@���Ă����D�{������
��Similarity Metric��p���āCMIDI�̎������ނ�ړI�Ƃ���D}

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

% �y�[�W�̎n�߂̔ԍ�
\setcounter{page}{29}

\begin{document}

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

\begin{multicols}{2}
\section{�͂��߂�}
�ߔN�R���s���[�^�Z�p�̔��B�ɔ����C�l�X�Ȏ������d�q�I�ɕۑ������悤��
�Ȃ����C���̒��ŉ��y���u�f�[�^�v�Ƃ��Ĉ�����悤�ɂȂ��Ă����D���݈ꕔ��
���Ƃɂ���āA�蓮�Ńf�W�^�������ꂽ���y�͕��ނ���Ă������ŁC�����
�̎������މ������߂��Ă���D
Ming Li�CXin Chen�CBin Ma�CPaul
M.B. Vit\'{a}nyi��́CKolmogorov�L�q�ʂɊ�Â��ăf�[�^�Ԃ̋�����\
��similarity metric���Ă����D����ɂ��u�f�[�^�v�Ƃ����ϓ_
���特�y�𕪗ނ��邱�Ƃ��\�ɂȂ�C���܂Ŗ��֌W���Ƃ���Ă��������ɑ΂��ĐV�����֌W�̔��������҂����D
Rudi Cilibrasi�CPaul Vit\'{a}nyi�CRonald de Wolf��̐�s�����ł́C
similarity metric��p���āCClassic��Rock�ȂǕ��L���W�������̉��y����舵
���C�����̏��Ƃ��Ă̋߂����O���t�ŕ\�����D�{�������̎O��ɂ��ǎ���
�ł͂́A���j�I�w
�i��n���I�w�i��MIDI�Ɋ܂܂�Ă��邩�����؂������C���҂�����
���Ȍ��ʂ͏o�Ȃ������D�����ŁC�{�����ł́C�Ώۂ�MIDI�ɒ�
�ڂ��Crubi�����̎������Č����邱�Ƃɂ��C�O��̌��ʂ̖��_�����؂���D

��2�߂ł�MIDI�̒�`�ɂ��āC
��3�߂ł�Kolmogorov�L�q�ʂɂ��āC
��4�߂ł�similarity metric�ɂ��ďq�ׁC��5�߂ł́C���ʂ̕\�����@�ɂ�
�ďq�ׁC��6�߂ł́C�������ʂɂ��ďq��,��7�߂ł�,����̉ۑ���q�ׂ�D

\section{MIDI�̒�`}
���̐߂ł́CMIDI�̊�{�I�ȍ\���ɂ��ďq�ׂ�D
\subsection{�O����}
����̎����Ŏ�舵�����f�[�^��MIDI�ƌĂ΂�鉹�y�t�@�C���ł���DMIDI�Ƃ�
Musical Instrument Digital Interface�̗��ŁC�y��Ԃ̃f�[�^�ʐM���@�̋K�i
���w���D�����f�W�^�������邱�Ƃɂ���āC���F�Ƃ������͉̂���(�s�b�`)�E�g
�`�E���ʂƂ���3�̃f�[�^�Ƃ��ċL�������D���̋L�����ꂽ�f�[�^��MIDI���b
�Z�[�W�ƌĂсC�����16�i���ŕ\������D���b�Z�[�W�̓��e�ɂ���Ă͕����̃o
�C�g�ɂ܂����邽�߁C�ŏ�ʃr�b�g(Most Significant Bit�C�Ȍ�MSB)���t���O
�̂悤�ȋ@�\������Ă���DMSB��1�̏ꍇ�C���̃o�C�g���X�e�[�^�X�E�o�C�g�C
0�̏ꍇ�f�[�^�E�o�C�g�ƌĂԁD�X�e�[�^�X�E�o�C�g�ɂ̓��b�Z�[�W�̎�ނ���
����Ă���C�f�[�^�E�o�C�g�ɂ̓f�[�^�̏�񂪏�����Ă���D�ȉ���MIDI���b
�Z�[�W�̒���������Љ�Ă����D

�O��ɂ��ǎ����ł́C�m�[�g�E�I���^�m�[�g�E�I�t�𔲂��o���CMIDI�`�����l
�����Œ肷
��O�������s���Ă���C
rubi�����ɂ��I�l�����ł́C�x���V�e�B�𕽋ω����CMIDI�`�����l�����Œ肷
��C�O�������s���Ă���D

\paragraph{�m�[�g�E�I���^�m�[�g�E�I�t}
�m�[�g�E�I���^�m�[�g�E�I�t�Ƃ͉����o��MIDI���b�Z�[�W�ł���D�����͕K���y�A�ő��݂��C����3�o�C�g�K�v�ł���D�ȉ��Ƀ��b�Z�[�W���e�������D
\begin{center}
\begin{tabular}{|c|c|c|}
\multicolumn{3}{l}{�m�[�g�E�I��} \\ \hline
9n & kk & vv \\ \hline
{\scriptsize ���b�Z�[�W���} & {\scriptsize �m�[�g�ԍ�} & {\scriptsize �x���V�e�B} \\ \hline
\end{tabular}

\begin{tabular}{|c|c|c|}
\multicolumn{3}{l}{�m�[�g�E�I�t} \\ \hline
9n(8n) & kk & 00 \\ \hline
{\scriptsize ���b�Z�[�W���} & {\scriptsize �m�[�g�ԍ�} & {\scriptsize �x���V�e�B} \\ \hline
\end{tabular}
\end{center}
\paragraph{n:MIDI�`�����l��}
�y��̐ݒ���s���D�m�[�g�E�I���^�m�[�g�E�I�t�ɂ�����C�X�e�[�^�X�E�o�C�g�̉���4�r�b�g(0�`F)�ŕ\�����D
\paragraph{kk:�m�[�g�ԍ�}
������\���Ă���D�f�[�^�E�o�C�g�ɂ����邽�߁CMSB��0�Őݒ肳��Ă���D���
�āC00�`7F�܂łŕ\�����D�m�[�g�ԍ�60�Ƃ̓h�̉�(261.6Hz)�ɓ�����D
\paragraph{vv:�x���V�e�B}
���̋����`����p�����[�^�̂��ƁD�m�[�g�ԍ��Ɠ��l�Ƀf�[�^�E�o�C�g���邽
�߁C00�`7F�ŕ\�����D00�Ƃ́C�����܂肻�̉����~�߂邱�Ƃł���D�m�[�g�E
�I�t���b�Z�[�W�ɂ�9n�`��8n�`��2��ނ����邪�C��ʓI��9n�`���g���Ă���D
\\


���ۂ�MIDI�t�@�C���́C���̉��t�f�[�^�Ɏ��ԏ���������SMF(Standard MIDI File)�ƌĂ΂��W���t�@�C���t�H�[�}�b�g�ƂȂ��Ă���D14�o�C�g�ŕ\�����ꂽ�u�w�b�h�`�����N�v����n�܂�C�u�g���b�N�`�����N�v�ƌĂ΂��g���b�N���������A�Ȃ��Ĉ�̃t�@�C�����\�����Ă���D���ꂼ��̃t�@�C���ŒP�ʎ��Ԃ���`����Ă���CSMF�͂��̎��Ԃ����MIDI���b�Z�[�W�𑗐M���鏇�Ԃ��L�����Ă��邾���ł���D�܂�C�v���C���[�ł́u�҂v���u���M�v���J��Ԃ��s���Ă���̂ł���D\\


\section{Kolmogorov �L�q�ʂ̒�`}
���̐߂ł́CKolmogorov�L�q�ʂ̊�{�I�Ȓ�`�ɂ��ďq�ׂĂ����D
\subsection{Kolmogorov �L�q��}
���鎖���Ɋ܂܂�Ă�����ɂ��čl����D�^����ꂽ�L���̑Ώ�(���Ƃ��Ε�����)�Ɋ܂܂����ʂ��C���̑Ώۂ𐶐�����v���O�����̃T�C�Y(���Ȃ킿�r�b�g��)�ƒ�`����D�������C���̏ꍇ�v���O�����Ƃ́C��̏�Ԃ���X�^�[�g���C���ׂĂ��o�͂�����̂Ƃ���D�ǂ�ȃv���O���~���O�����I��ł��C���ꂪ�Ó��ł���΁C���ʂ͒萔���̍������Ȃ����Ƃ��ؖ�����Ă���D

�Ώۂ̏W������Ȃ��`��$D\ni x$�ɂ��āCs���v���O��������C|p|���v���O�����̃T�C�Y�CS(p)��n=S(p)�ƂȂ�֐��Cn(x)��񋓂�����@�����肵���Ƃ���x�̏��ʂƂ���ƁC�L�q�ʂ͈ȉ��̂悤�ɒ�`�����D
\begin{center}
\begin{math}
K_{s}(x)=min\{|p|:S(p)=n(x)\}
\end{math}
\end{center}
�������Cx�𐶐�����p�����݂��Ȃ��Ƃ��́C
\begin{center}
$K_{s}(x)=\infty$\\
\end{center}
�ƂȂ�D


�܂��C����Ώ�y���^�����Ă���Ƃ��̑Ώ�x�̋L�q�ʂ��`����D������x���C�v�Z�\�֐�f�C����ɕ�����p��y�ɂ��$f(p,y)=x$�ƋL�q���邱�Ƃ��l����D�����ŁC�C�ӂ̌v�Z�\�֐�f���C���^�v�����^�֐����邢�͕����֐��ƁC�C�ӂ�$p\in\{0,1\}^{\ast}$���v���O�����ƌĂԂ��Ƃɂ���D�C���^�v�����^�֐� f �̂��ƂŁC�⏕��� y �ɑ΂��� x �̋L�q�� $K_{f}$ ���ȉ��̂悤�ɒ�`����D
\begin{center}
\begin{math}
K_{f}(x|y)=min\{|p|:p\in\{0,1\}*\&f(p,y)=x\}
\end{math}
\end{center}
�������C�����𖞂��� p ���Ȃ��Ƃ��́C
\begin{center}
$K_{f}(x)=\infty$\\
\end{center}
�ƂȂ�D


�܂��Cx��y����ʂł���`�ŏo�͂�����ŒZ�̃v���O���������C$K(xy)$�ƕ\���D$O(\log K(xy))$�̌덷�͈͂ł́C
\begin{center}
$K(xy)=K(x)+K(y|x)$\\
\end{center}
�ƂȂ邱�Ƃ��ؖ�����Ă���D

\subsection{K�̃A���S���Y���I����}
K(x)�𐳂̐������琳�̐����ւ̊֐��ƍl����D�@
\\

\noindent\textbf{�藝}
\begin{enumerate}

		\item �֐�K(x)�͋A�[�I�ł͂Ȃ��D�������C�ǂ̂悤�ȋA�[�I�����֐�$\phi(x)$���l���Ă��C�������̒l�������̓_�Œ�`����Ă���Ȃ�΁C���̒�`��̂ǂ����̓_��$\phi(x)\neq K(x)$�ƂȂ�D

		\item ���� t �ɑ΂��ĒP��������(�S��I��)�A�[�I�֐� $H(t,x)$ �����݂��C$\lim_{t \to \infty}H(t,x)=K(x)$ �D���Ȃ킿�C K(x) �̂悢�ߎ��͌v�Z�\�D����������͈�l�ߎ��ł͂Ȃ��D
\end{enumerate}

\subsection{����}
���΋L�q��K(x|y)����΋L�q��K(x)��肩�Ȃ菬�����ꍇ�C�uy��x�ɂ��Ă̏��𑽕��Ɋ܂�ł���v�ƍl���邱�Ƃ��ł���D���������āC�萔���̍��ق𖳎�����΁C�gy�Ɋ܂܂��x�̏��ʁh��
\begin{center}
\begin{math}
I(x:y)=K(y)-K(y|x)
\end{math}
\end{center}
�Ƃ݂Ȃ����Ƃ��ł���D�܂��C$K(x|x)$�ƂȂ�x��I�ׂ΁C
\begin{center}
\begin{math}
I(x:x)=K(x)
\end{math}
\end{center}
�ƂȂ�D�����ōl����ׂ����Ƃ́C���̑Ώ̐��ł���D$O\log K(xy)$�͈̔͂ł́C
\begin{center}
$K(xy)=K(x)+K(y|x)$\\
\end{center}
�����藧�̂ŁC�����p����ƁC
\begin{center}
$I(x:y)=I(y:x)$\\
\end{center}
�����藧�D
\\

\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 �L�q�ʂ͋A�[�I�łȂ����߁C�v�Z�s�\�ł���D
\item ���p�I�ȕ��@�ŏ�񋗗����ߎ�����ہC���k���@�̈�ł���gbzip2�h��p����D
\end{enumerate}
�ȏ���Abzip(x)�𕶎���x��bzip2�ň��k�����Ƃ��̃t�@�C���T�C�Y�Ƃ���Ə�񋗗�d(x,y)�͈ȉ��̂悤�ɋߎ������D\\
\begin{eqnarray}
d(x,y)/approx\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{��������}
tranceform�̉񐔂��Œ肷����@�ŁC�������s�����D
\subsection{�����P}
���E�e�n�̖������y�f�[�^���e��1�Ȃ���27�W�߁C�������s�����D
tranceform��50,000��ŌŒ肵���{����͒���Ƌ��s��2�Ȃ̖������y��I�o�����D
\\

\begin{center}
\includegraphics[width=10cm]{new_work2.eps}
\end{center}
\centerline{Figure4 �{����:tranceform:50,000 $S(T)=0.6167$}

\begin{center}
\includegraphics[width=10cm]{mitu2.eps}
\end{center}
\centerline{Figure5 �O��ɂ��ǎ���:tranceform:50,000 $S(T)=0.64777$}



�����C�אڂ��Ă��鍑���m�ł̓���������ꂽ���C�{�����ł��C�O�䓯�l�ɍۗ���
���n�悲�Ƃ̓����͌����Ȃ������D
�܂�,�f�[�^������������S(T)�̒l���オ���Ȃ��Ă���D

\subsection{����2}

�X�R�b�g�����h�C���{�C�A�����J�C�t�����X�C�X�y�C�����炻�ꂼ��2�`3�Ȃ̖�
�����y���W�߁C�������s�����D
tranceform��70,000��ŌŒ肵���D\\

\begin{center}
\includegraphics[width=8.3cm]{new_work3.eps}
\end{center}
\centerline{Figure6 :tranceform:70,000 $S(T)=0.81024$}


S(T)�̒l�͍����Ȃ��Ă���̂ɂ��C������炸����1�Ɠ��l�ɁA�n�悲�Ƃɍۗ������������o�Ȃ������D\\


\section{����̉ۑ�}
�{�����ł́CMIDI�t�@�C������n�悲�Ƃ̗ގ����������邱�Ƃ͏o���Ȃ�����
��,�Ⴄ�O�������s�����Ƃɂ��,�n�悲�Ƃ̗ގ����������邱�Ƃ��o����\
��������D\
�܂�,MIDI�t�@�C���ȊO�̉��y�t�@�C����ΏۂƂ��Č���Ȃ��,�n�悲�Ƃ̓���
���o��\��������D

\begin{thebibliography}{4}
\bibitem{}
	Ming Li�CXin Chen�CBin Ma and Paul M.B. Vit\'{a}nyi.\quad
The Similarity Metric.In Proceedings of the 14th annual ACM-SIAM
	symposium on Discreat algorithms(SODA),pp.863-872,Baltimore,Maryland,2003.
\bibitem{}
	Rudi Cilibrasi�CPaul Vit\'{a}nyi and Ronald de Wolf.\quad
Algorithmic Clusteringof Music(2003)
\bibitem{}
	Ming Li and Paul M.B. Vit\'{a}nyi. �n�� �� �|��\quad
Kolmogorov Complexity and its Applications.�R���s���[�^��b���_�n���h�u�b
	�N(1994)
\bibitem{}
	���b�g�[�~���[�W�b�N�o�ŕҏW���y�ҁz\quad
MIDI�o�C�u��I MIDI1.0�K�i ��b��(1997)
\bibitem{}
	http://www.momo-mid.com/\\
\bibitem{}
	http://www.tani.cs.chs.nihon-u.ac.jp/g-2005/taako/

\end{thebibliography}
\end{multicols}
\end{document}
