%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%�@�������W����2008 �L�m�V�^�^�J�V
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%#! platex resume.tex
\documentclass[a4paper]{jarticle}

\usepackage{tani_resume_last}
\usepackage{epic}
\usepackage{eepic}
\usepackage{graphicx,amsmath}

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

\usepackage{amssymb}
\bibliographystyle{plain}
\usepackage{natbib}

\jptitle{���{��L�[���[�h�̊֘A�x�Ɋ�Â������G���W���uGoogle�v�uYahoo!�v�̐��\��r}
\etitle{Comparison between Google and Yahoo! based on similarity method}
\jpauthor{�؉� �F�j}
\eauthor{Takashi kinoshita}
\course{�J�@������}
\year{20}
\abstract{%
  Kolmogorov�L�q�ʂɊ�Â����f�[�^�Ԃ̗ގ��x�Ɋւ��鋗������Normalized Information Distance�����Ă��ꂽ�B��������p�����A�P��Ԃ̊֘A�x�����߂����Normalized Google Distance���Ă��ꂽ�B�{�����ł͂����p���āA�����G���W���uGoogle�v�uYahoo!�v�̐��\��P��Ԃ̊֘A�x���猟�؂���B 
}



\begin{document}

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

\begin{multicols}{2}
 \section{�͂��߂�}
 ���݁A�C���^�[�l�b�g��ɂ͑��푽�l�ȏ�񂪎U��΂��Ă���B�C���^�[�l�b�g��ŕK�v�ȏ��𓾂悤�Ƃ���Ƃ��A��X�͌����G���W����p����B��\�I�Ȍ����G���W���Ƃ���Google,Yahoo!,msn�Ȃǂ��������A�����ɂ���Č����G���W���̃V�F�A�̑唼���߂Ă���B�č��ł̌����G���W���̃V�F�A��07�N12�����݁AGoogle65.98��,Yahoo!20.88��,msn7.94���B���{�ł�08�N1��20�����݁Ayahoo!61.2��,Google30.3��,msn2.0���ƂȂ��Ă���B

 �ߔN�AMing Li�B��Kolmogorov�L�q�ʂɊ�Â��f�[�^�Ԃ̗ގ��x�Ɋւ��鋗��������킷�����𔭈Ă����B���̌�ARubi L. Cilibrasi�B\cite{one}�ɂ���āA�ގ��x�Ɋւ��鋗�����������p���A�����G���W����p����2�P��Ԃ̊֘A�̓x���𐔒l������������Ă����B

 �{�����ł́A���̌�����p���āA�����G���W���uGoogle�v\cite{three}�uYahoo!�v\cite{four}��ΏۂƂ��A�P��̃J�e�S���[���łǂ���̗D��Ă��邩��r�]������B

 2�߂ł�Kolmogorov�L�q�ʂɂ��āA3�߂ł�Normalized Information Distance�ɂ��āA4�߂ł�Normalized Compression Distance�ɂ��āA5�߂ł�Normalized Google Distance�ɂ��āA�U�߂ł͎����ɂ��āA�V�߂ł͌��ʍl�@�A�W�߂ł͍��x�̉ۑ�ɂ��ĉ������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�s�\�B
 \section{Normalized Information Distance}
 �܂��������`����B\\
\fbox{��`}\\
�@����W��$X$��̋����Ƃ́A�񕉎����l�֐�$d:X \times X \rightarrow R$�ŔC�ӂ�$x,y,z \in X$�ɑ΂��Ď��̂悤�Ȑ����𖞂����B
\begin{eqnarray*}
 & &x=y\rightarrow d(x,y)=0\\
 & &d(x,y)\geq 0\\
 & &d(x,y)=d(y,x)\\
 & &d(x,y)\leq d(x,z)+d(z,y):\mbox{�O�p�s����}
\end{eqnarray*}
�������ɁA���̋������l����B\\


 ����x����o��y�𐶐�����ŏ��̃v���O�����̃T�C�Y��information distance�Ƃ����B���̂Ƃ��Ax��y��information distance�͈ȉ��̂悤�ɕ\�����B
 \begin{displaymath}E(x,y)=K(x,y)-min{K(x),K(y)}\end{displaymath}
information distance E(x,y)�͔C�ӂ�$x,y,z$�ɑ΂��Ď��̂悤�Ȑ����𖞂����B

\begin{eqnarray*}
 & &E(x,x)=0\\
 & &E(x,y)>0\\
 & &E(x,y)=E(y,x)\\
 & &E(x,y) \le E(x,z)+E(z,y):\mbox{�O�p�s����}
\end{eqnarray*}
   \subsection{Normalized Information Distance}
 ����information distance�ɂ͌��_������B�Ώۂ̑傫���ɂ���āAinformation distance�������ł����Ă����Ă��邩�ǂ����͕ς���Ă���B�����ŁA����information distance�𐳋K������B���̐��K������information distance��
NID(Normalized Information Distance)�Ƃ����A�ȉ��̂悤�ɕ\���B
\begin{displaymath}NID(x,y)= \frac{K(x,y)-min(K(x),K(y))}{max((K(x),K(y)) }\end{displaymath}


 \section{Normalized Compression Distance}
 NID�ɂ��Ax��y�̗ގ��x�𓾂邱�Ƃ��ł��邪Kolmogorov�L�q�ʂ͌v�Z�s�\�ł��邱�Ƃ���ANID���v�Z���邱�Ƃ͂ł��Ȃ��B���������ۂɂ́AKolmogorov�L�q�ʂ��ߎ����鈳�k�v���O�����𗘗p���邱�Ƃ��ł���B

���k�A���S���Y�����v�Z�\�Ȋ֐��ƒ�`����BC�����k�@�AC(x)���A������x�����k�@C�ň��k�����Ƃ��̃T�C�Y�Ƃ���B����ƁANormalized Compression Distance���ȉ��̂悤�ɕ\�����Ƃ��ł���B
\begin{displaymath}NCD(x,y)= \frac{C(x,y)-min(C(x),C(y))}{max((C(x),C(y)) }\end{displaymath}



\section{Normalized Google Distance}
 \subsection{Google}
�R�[�p�X�͕�����t���[�Y�̊֌W�p�x���`����B�O�[�O���ɂ͂P�O�O���̃R�[�p�X������B�O�[�O���ɃC���f�b�N�X����Ă���E�F�u�y�[�W��$10^10$�ł���A����P��͂P�O�O���̃y�[�W�Ɍ����Ƃ���Ă���B����͏\���ȑ傫���ł���A�O�[�O�������ɂ���ē����錟�����ʂ̐��͎��ۂ̕p�x���ߎ��ł���ƍl������B
����𗘗p���āA�֘A�x�����߂�B
 \subsection{Normalized Google Distance}
�ȉ��ɁA�O�[�O����p�����֘A�x�ANGD(Normalized Google Distance)���`����B

 $N$:�O�[�O���C���f�b�N�X��\\
 $x,y$:�P��\\
 $X,Y$:�P��$x,y$�ɂ���ē����邻�ꂼ��̃E�F�u�y�[�W�̏W��\\
 $|X|,|Y|$:$X,Y$���ꂼ��̏W���̐�\\
 $g(x)= \frac{|X|}{N}$\\
 $G(x)= log \frac{1}{g(x)}$\\
\begin{eqnarray*}
 NGD(x,y) &=& \frac {G(x,y)-min(G(x),G(y)} {max(G(x),G(y)} \\
   &=& \frac { \{logf(x),logf(y)\}-logf(x,y)} { logN-min \{ logf(x),logf(y)\} } 
\end{eqnarray*}

 \subsection{NGD�̐���}
NGD(x,y)�͔C�ӂ�$x,y,z$�ɑ΂��Ĉȉ��̐��������B
\begin{eqnarray*}
 & &NGD(x,y)�̒l��:[0,��)\\
 & &NGD(x,x)=0\\
 & &NGD(x,y)=NGD(y,x)\\
 & &NGD(x,y) \le NGD(x,z)+NGD(z,y)�𖞂����Ȃ�
\end{eqnarray*} 
���̌����͑��̌����G���W���ł����l�Ɉ�����B\\


\section{����}
 \subsection{�����T�v}
 Google��Yahoo!���ꂼ��ɒP��𑗂�A���̌����ɂ���ē����錏�����f�[�^�Ƃ��Ĉ����B
 �{�����ł́A�Ώۂ������G���W���Ƃ��Ă��邪�A�����G���W���̐��\�𒼐ڕ]������͔̂��ɍ���ł���B�����ŁA�J�e�S���[�𗘗p���邱�Ƃ�Google��Yahoo!���r����B

 \subsection{�J�e�S���[}
 �J�e�S���[�̓T�u�J�e�S���[����\������A�T�u�J�e�S���[�͂���Ɋ܂܂��P�ꂩ��\�������B\\
 �J�e�S���[�͔�r���s�������\���A�T�u�J�e�S���[�̓J�e�S���[�Ɋ܂܂�镪���\���B\\

 \subsection{�J�e�S���[�̗�}
 �ȉ��ɃJ�e�S���[���u���w�U�B�v�ɂ����Ƃ��̗�������B
  \begin{center}
   \includegraphics[width=6cm,height=5cm]{categ1.eps}
  \end{center}

 \subsection{���_�t��}
 �{�����ł͓���ꂽNGD��p���ē��_�t��������B
 ���_�̕t�������ȉ��̂��̂Ƃ���B\\

 �P��x,y�ɂ�����Google��NGD��$NGD_g$,Yahoo!��NGD��$NGD_y$�Ƃ���B\\
 $\frac{NGD_g}{NGD_y}$��Yahoo!�̓��_�Ƃ��A���̒P��Ԃ̓��_�Ƃ��� \\
 $\frac{NGD_y}{NGD_g}$��Google�̓��_�Ƃ��A���̒P��Ԃ̓��_�Ƃ��� \\
 $\frac{NGD_g}{NGD_y}=1$�̂Ƃ��A���̒P��Ԃ̓��_��0�Ƃ���\\
 �eGoogle�ւ̓��_�AYahoo!�ւ̓��_�̑��a�����߁A��������̃T�u�J�e�S���[�̓��_�Ƃ���B

\subsection{�������@}
 \begin{enumerate}
  \item �T�u�J�e�S���[�̒P��S�ɂ����āA�S�Ă̒P��Ԃɂ�����NGD���uGoogle�v�ƁuYahoo!�v��p���ċ��߂�B
  \item �uGoogle�v�ƁuYahoo!�v�ŋ��߂�NGD��p���āA���҂̑Ή�����NGD���瓾�_�t��������B
  \item Google�ւ̓��_�̑��a�AYahoo!�ւ̓��_�̑��a���Ƃ��ɃT�u�J�e�S���[�̓��_�Ƃ���B
  \item �e�T�u�J�e�S���[�œ�����Google�̓��_�AYahoo!�̓��_�̂��ꂼ��̑��a���J�e�S���[�̓��_�Ƃ��A�]������B
 \end{enumerate}

\section{���ʥ�l�@}
  \begin{center}
   \includegraphics[width=8cm,height=5cm]{categ_1.eps}
   \includegraphics[width=8cm,height=5cm]{categ_2.eps}
   \includegraphics[width=8cm,height=5cm]{categ_3.eps}
   \includegraphics[width=8cm,height=5cm]{categ_4.eps}
  \end{center}
 ����͂S�̃J�e�S���[�Ə����ł͂��邪�A���炩�ȈႢ������Ă���B�ގ��x�A�Ƃ����ϓ_���猩��ƁA���|�I�ɁuGoogle�v�������Ă���Ƃ������Ƃ��킩��B�e�T�u�J�e�S���[�ł̒P��̑I�ѕ��ɂ��Ⴂ�����邾�낤���A�������l�����Ă������G���W���Ƃ��ẮuGoogle�v���D���Ƃ����X���͂��邾�낤�B

\section{����̉ۑ�}
 ����̎����ł̓J�e�S���[���S�Ə��Ȃ��������߁A��葽���A���L�������f�[�^�T���v�������A�J�e�S���[�𑝂₵�A�ēx���؂���B�܂��A�T�u�J�e�S���[�̒P��̑I�ѕ��A�]���̎d���ɂ���Ăǂ̂悤�ɈႢ������邩�����؂���B



    \begin{thebibliography} {4}
     \bibitem{one} 
	     Rubi L.Cilibrasi and Paul M.B. Vitanyi\\
	     IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING\\
	     The Google Similarity Distance (2007)
     \bibitem{two}
	     �J ����\\
	     �f�[�^�̕��G���E�f�[�^�\���̕��G��
     \bibitem{three}
             Google\\
	     http://www.google.co.jp/
     \bibitem{four}
             Yahoo!Japan\\
	     http://www.yahoo.co.jp/

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



