\documentclass{article}
\usepackage[russian]{babel}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage[dvips]{graphics}
%=============================================================================
\newcounter{dx}
\newcounter{dy}

\newcommand{\lmessagevector}[3]
{
	\put(#1, #2){\vector(-4, -1){41}}
	\setcounter{dx}{#1}\addtocounter{dx}{-50}
	\setcounter{dy}{#2}\addtocounter{dy}{-2}
	\put(\value{dx}, \value{dy}){\scriptsize#3}	
}

\newcommand{\rmessagevector}[3]
{
	\put(#1, #2){\vector(4, -1){41}}
	\setcounter{dx}{#1}\addtocounter{dx}{15}
	\setcounter{dy}{#2}\addtocounter{dy}{-2}
	\put(\value{dx}, \value{dy}){\scriptsize#3}	
}

%=============================================================================
\uchyph = 0
\sloppy
%=============================================================================
\title{������������� �������}
\author{�. ������\thanks{���������������� �. ���������.}.}

\begin{document}
\maketitle
\tableofcontents
%=============================================================================
\section{���������� ������, ������� � ����������}
\subsection{������������ ��������}
\qquad
������ ������� � ���, ����� \textbf{������������� ����������������} �����
������� �� ����������. C�� ������� ������ ���� ������
\textbf{��������������}: ������������� ���������� ��� ������
���������� ��������� ���������, ������� ����� ����������, ��������
��� ��� ���� �������� � ������������ ������, �������� ������� ������ �������.
\textbf{�������������} �� ����� ������ � ��������������, �� ����
������������ �������. ������ �������������� ������������� ����� ���������
�������, �� �� �� ����� �� �����������.

��� ����� ������������ ������ �������������� ������� �������. ��������� - ���
����� ���� ������������� ������, ������� �������������� ����������, ��������.
�������� - ����� ���� ��� �����-���� ������� ������, � �������, ���� 
����������, ���� ���������, ���������� � �.�. 

����� �������������� ��� ������: 
\begin{itemize}
\item ��������������� ������ (Information Retrieval)
\item ��������� �������� (Machine Learning)
\end{itemize}

\subsection{���������� ���������� ������}
\qquad
��������� ������ ���������.
����� ������ ��������� �������� ��������� ���������
$\mathfrak{C}=\{c_1,\dots,c_{|\mathfrak{C}|}\}$,
�������� ��������� ����������
$\mathfrak{D}=\{d_1,\dots,d_{|\mathfrak{D}|}\}$
� ����������� ������� ������� $\Phi$, ������� ��� ������
���� $<$��������, ���������$>$ ����������, ������������� �� ��� ����
�����:
$\Phi:\mathfrak{D}\times\mathfrak{C}\rightarrow \{0,1\}$.

������ ������� � ���, ����� ����� ����������� ������� � ������� $\Phi$ 
������� $\Phi'$. ������� $\Phi'$ �������� \textbf{���������������}. 

�������� �������� ������������� �� ��������� ��������� ���������� 
$\Omega=\{d_1,\dots,d_{|\Omega|}\}\subset\mathfrak{D}$. ��� ����,
�������� ������� ������� $\Phi$ �������� ��� ������ ���� 
$<d_j, c_i>\in \Omega\times\mathfrak{C}$. ��������� �� $\Omega$ 
��������� �� ��� ���������������� ���������:
\begin{itemize}
 \item \textbf{''�������''} $Tr=\{d_1,\dots,d_{|Tr|}\}$. ��������� ����������, � ������� ������� ��������� 
	   ������������� $\Phi'$. $\Phi'$ ���������� ����������, ����������� �� ���������� ��������������� 
       ���� ����������. 
 \item \textbf{''��������''} $Te=\{d_{|Tr|+1},\dots,d_{|\Omega|}\}$. ��������� ����������, �� ������� 
	   ����������� ������������� ������������ ��������������. ������ "��������" �������� �������� �� 
	   ���� �������������� $\Phi'$, � ����� ��������e��� ��������� �������������� $\Phi'(d_j, c_i)$ � 
	   ��������� ��������� ������� $\Phi(d_j, c_i)$. ������������� ��������� ��� �����������, ��� ���� 
	   ��� �������� ���������.
\end{itemize}

�������� $d\in \Omega$ ���������� \textbf{�������������} ��� \textbf{�������������} �������� ��� ��������� 
$c$, ���� �������� ������� $\Phi(d, c)$ ����� 1 ��� 0, ��������������.

\subsection{���� �������������}
\qquad
���������� ��������� ��������� ����� �������������. � ����������� �� ������, �������������
������:
\begin{itemize}
 \item ������ : $\Phi': \mathfrak{C}\times\mathfrak{D}\to\{0,1\}$
 \item ������������� : $\Phi': \mathfrak{C}\times\mathfrak{D}\to[0,1]$
\end{itemize}
���� �� ������������� ������ \textbf{������ �������������}, ������� ������ ���� $<$��������,
���������$>$ ������������ ������ �������� 1 ��� 0 (������������� �������� ��������� ���
���). ������ �����������, ��� ������������� $\Phi'$ ����� ���������� ������� ��������������
��������� � ���������, ������ ��� ������� ��������� ������, ������� � ��������� �� 0 �� 1 (���
������ ������� ��������������, ��� ������ �������� �������� ���� ���������). ����� ���
������������� ���������� \textbf{�������������}.

���������� ��� ��������� ������� ��������� ����������. ������, ����� ���� ����� ���������, � ���������
����� ��������, ��� �������� ����� ���������� ������ ���������� ��� ���������. ������, �����, ��������, ���� 
��������� ����������, � ��������� ����� ���������. ���������� ����� ��� ���������, ���������������
������ ����� ���������. ��� ��� ���� ������������� �������� �����������, ���� ���������� ������, �������
�������� ��� ������ �� ��� � �� �������� ��� �������, �� ��� ������ ����������, ��� �������.

����� ���������� ��������� $\mathfrak{C}$ �������� ��������� �����������:
\begin{itemize}
 \item ��������� �� ������������,
 \item ��������� ����� ������������,
 \item ��� ���������������� ���������.
\end{itemize}
���������� ������� ������������ ���������� �� ���, ������� ����� ��������������� ��������
\textbf{�������� �������������}. � �������� ������������� ����� ������ ��� ���������:
��� ����� ��������� $c\in\mathfrak{C}$ ����� ����������, ����������� �������� 
��������� $c$ ��� �� ���������� $\overline{c}$.

\subsection{���������� ������������� �������}
\begin{itemize}
 \item ���������� ����������, ������������� �����
 \item �������������� �������������
 \item ������ ��������������� (�������������� �����������)
 \item ����������� ��������-���������
 \item ������������� ��������
 \item ������������� �������
 \item ������������ �������
\end{itemize}

\subsection{�������� ����}
\qquad 
������������� ����� ��������� �� ��� �������� �����:
\begin{itemize}
 \item ���������� ����������,
 \item �������� ��������������,
 \item ������ �������� �������������.
\end{itemize}
\qquad
\textbf{�����������} ���������� ������� ���������� ���������� � �������� �������. 
�������� ����������� ����� ���� � �������� �������� ����������, ������� ��� 
���������� ���������� ��������� � ���������� ��� ������. � �������, ��������� ����� 
(����� ���������) ����� ����� ����� ����������� �� ���� ����������, �� ��� ���� ��� 
�� ����� ������� ��������� ��������.

\textbf{�������� ��������������} ������� � ������ ����� ����� ����������������� �������
�� ���������� ��������� ����������. ����� ������������ ��������� ���������� �� ''���������''
������ ����������.

���������� ��� ������� � \textbf{������ �������� �������������}. ������ - ��� ���������
��������������� ����� �����, ������ - ���������� ������ ��������.
������ ������, �������� ������ ������� �������� �������������. ����� ���� �������
�������� �� ����� ���������� � ����� ��������� ������� ���������� ��������, �� ���
��������� ���� ���������� ������� ����� ���������� ��������� �������� ������ �����������
�������� �������������. ������ �� ��� ����� ���� ''�������'' � ''������'' �������. 
���������� ��� ���� ����� ����� ��������.

\section{���������� ����������}
\subsection{����������� ������}
\qquad
����� �������, ��� ������ �������� - ��� ������ ����� ���� (������). ��������� ���� ������ ��������� �� 
$\mathcal{T}$. ������ ���� $t_i\in\mathcal{T}$ ����� ��� $w_{ij}$ �� ��������� � ���������
$d_j\in\mathfrak{D}$. ����� �������, ������ �������� ����� ����������� � ���� ������� �����
��� ������ $\overrightarrow{d}_j=<w_{1j},\dots,w_{|\mathcal{T}|j}>$. ���� ���������� ���������
���, ����� $0\le w_{ij} \le 1$ ��� $\forall i, j: 0 \le i \le |\mathcal{T}|, 0 \le j \le |\mathfrak{D}|$.

��� ����� � ��������� ����� ���������� ��������� �������:
$$
 w_{ij} = TF_{ij} \cdot IDF_i
$$
���� $TF_{ij}$ - ��� ��������� ����� ������ $t_i$ � ��������� $d_j$ � ������ ����� ������ � ����
���������, � $IDF_i$ - �����, �������� ���������� ����������, � ������� ����������� ���� $t_i$.
����� �������, ��� ���� ����� ����������� � ���������, �� ���� ����������� ������ ��
���� ����������, ��� ������ ��� ����� ����� � ������ ���������. 

������������� ��� ����� � ��������� ����� ��������� ����������� ��������:
$$
 w_{ij} = \frac{TF_{ij} \cdot IDF_i}{\sqrt{\sum_{s=1}^\mathcal{|T|}(TF_{sj} \cdot IDF_s)^2}}
$$

\subsection{���������� �����������}
\qquad
��������� ������ ������� �� ����� �������� ����� ����. ���������� ��� �������, ������� ���������
��������� �� ����������. ��� ������ ��������� ����� ������������ �� ����������� �����, ��
���� ���������� ���� ������ ����� ��� ���� ���������. ������ ����� ����� �������� ����������� �����.
�����, ������� ����������� ����� ����� ������ ����� ��������� ''�������'' (��������, ����� � �.�.),
�� ��� ����� ����������. �� �� ����� �������� ����, ������� ����������� ������� �����, �.�. ������
����� ��� �� ����� ������� ��������� ��������. ����� ������� ������� ��������� ������ 
''������-�������������'' �����. 

������ ������� ������� � ����������� ''������������� ����������'' ������. ����� �� ����� ���� � 
�������� ��������������. �����������, ��� ����������� ��������� ���� $t$ � ��������� $d$, 
���� �������� $d$ ����������� ��������� $c$ ������ � ����������� ��������� ���� $t$ � ���������
$d$, ���� �������� $d$ ����������� ��������� $\overline{c}$. �����, ���� �������� ��������
���� $t$, �� �� (��������) ����� ������������� ������� ��� � ��������� $c$, ��� � � �� ����������. 
������� ����� ������� ����� ����� ������������. ''����������� ����������'' � ������ ������ �����
���������� ��� ������ �������� ���� ���� �������� ������������.

��������� ���� ������� � �������� ������������� ������. ��������� ������ ����� ���������� � ����
(\textbf{������������� ������}). ��������, ��� ������������ ����� ����� �������� �� ���� �����.
����� ������������ ������� ���������, ���, � ����� ������, ���������� ������� �������������� ����.
��� �� ����� ������������ ������� \textbf{������������} ����������, ������� ���� ����������� ��
���������� ������.

\section{���������� � �������� ��������������}
\subsection{������������ � ������ �������������}
\qquad
�����������, ��� ��� ������ ��������� $c_i$ ��������� ������� $CSV_i:\mathfrak{D}\to[0,1]$, �������
������ ������� �������������� ��������� ���������. ������ ������� � ���, ����� �� �������������
������� ������� � ������ �������������. �������� ������� ������ - ��� ������ ��������� $c_i$ ������� 
��������� �������� $\tau_i$. ���� $CSV_i(d)>\tau_i$, �� �������� $d$ ������������� ���������
$c_i$. ������ �����: ��� ������� ��������� $d$ �������� $k$ ��������� ���������, �.�. $k$ ���������,
�� ������� $CSV_i(d)$ ��������� ���������� ��������.

\subsection{����� Rocchio}
\qquad
��������� �������������� ����������, ��� ����������, \textbf{�������} (��� �������� ���������) ���
���������. ������� - ��� ������ ���������� ������, ����������� ��� ���������� ������� ��������
������ �������� ��������� $c_i$ �� ������ ���������. ����� Rocchio ������������ ��� ��������
���������������, �� ���� ��������������� ������� ������������ ������ �������� � ���� ������� ����� 
������ (��. 2.1). ������� $\overrightarrow{c_i}=<w_{1i},\dots,w_{\mathcal{|T|}i}>$ ��� ���������
$c_i$ � ������ Rocchio ��������������� �� ��������� �������:
$$
	w_{ki}=\beta  \cdot \sum_{\{d_j\in POS_i\}}\frac{w_{kj}}{|POS_i|} -
		   \gamma \cdot \sum_{\{d_j\in NEG_i\}}\frac{w_{kj}}{|NEG_i|},
$$
��� $w_{kj}$ - ��� ��� ����� $t_k$ � ��������� $d_j$, $POS_i=\{d_j\in Tr|\Phi(d_j, c_i)=1\}$ �
$NEG_i=\{d_j\in Tr|\Phi(d_j, c_i)=0\}$. � ���� �������, $\beta$ � $\gamma$ - ����������� ���������,
������� ������������� ���������� ������������� � ������������� ��������. ��������, ���� $\beta=1$
� $\gamma=0$, $\overrightarrow{c_i}$ ����� ������� ���� ���� ������������� �������� ���������
$c_i$.

������� $CSV_i(d)$ ������������ ��� �������� �������� ���������� �� ��������� $d\in\mathfrak{D}$ �� 
�������� ��������� $c_i$. ����� Rocchio ���� ������� ����������, ����� ��������� �� ����� ��������� 
������ ���� ����� (� ������ ����������). �� ����, ��������, ��������� $c_i$ ������������� ������ �� 
���� ������ ������ (���������� � �������), �� ���������� �� ������� ��������� $c_i$ �� ��������� �� 
����� ����� ����� ����� �������, ������� �������� ������� $CSV_i$ ����� ���������, � �� ���� ��������
�� ������� � ��� ���������.

\subsection{����������� �������}
\qquad	
���� ������� ������ ������� � ���������� \textbf{������������ ������} �� ''���������'' ������ ����������. 
������ �������� �� ���������� �������: �������� ����, ��������� ���������� ��� ������ �������, ��������� 
������. ����� �������, ��������� ����������� �� ��� ���������������� ��������. ��� ������ ��������� ���������� 
����� ���� � ����������� ��������� ���� ���������. ��� ������������ �� ��� ��� ���� �� ��������� ���������� 
���������, �� ���� ���������, � ������� ���� ��� ��������� ������������� ���������, ���� ��� ��������� 
������������� �� ����������. ��� ������� ������� ���������� ������ ��� ��������� ''������''.
\linebreak

\begin{picture}(310, 90)
	\put(155, 85){\circle{5}}
	\lmessagevector{145}{85}{������$\notin$}
	\rmessagevector{165}{85}{������$\in$}
	
	\put(100, 70){\circle{5}}
	\lmessagevector{ 90}{70}{�������$\notin$}
	\rmessagevector{110}{70}{�������$\in$}
	\put(205, 65){1}

	\put(45, 55){\circle{5}}
	\lmessagevector{35}{55}{���$\notin$}
	\rmessagevector{55}{55}{���$\in$}
	\put(-5, 35){0}
	\put(90, 35){1}

	\put(155, 55){\circle{5}}
	\lmessagevector{145}{55}{���$\notin$}
	\rmessagevector{165}{55}{���$\in$}
	\put(105, 35){0}
	\put(205, 35){1}
\end{picture}

�� ������� �����, ��� ��� ''���������'' ���������, ���������� ����� ''������'', ������������� ���������.
���� � ��������� �� ����������� ����� ''������'' , �� ����������� ����� ''�������'' � ''���'', �� ��������
���� �������� ������ ���������, ���� ������ ����� ''�������'' �� ����������. ��� ��������, ��� ����
''���������'' ���������, � ������� ���� ����� ''�������'', �� ��� ��������� � ���������� ���������. �������, 
�������� ����� �� ��������� ���� ''������'' � ''�������'', �� ���� � ��� ������������ ����� ''���'', �� ��� 
��� �� ������� � ��������� ''������''.

� ������� ������ ����� ���������, ������� ��� ����� ������ ������������, ���� ��������� ''���������''
���������� ������. � ���� �� � ''�����������'' ������� ������ ��������������. ������ ������, ��� �� ��������� 
�������� �����, ����� ������ �� ������������? ��� ������ ������ ����� ������������ ''����������� ����������'' 
�����, ������� �� ��� ������������� � ������ 2.2.

\subsection{����� k �������}
\qquad
�������� ����� � �������� ���������������. ����� k ������� ������� � ���, ����� ���������� �������
$CSV_i(d)$ ����� ��������� (� ������ ����������) � d ''���������'' ���������.
$$
	CSV_i(d)=\sum_{d_z\in Tr_k(d)}\frac{\Phi(c_i, d_z)}{\rho(d, d_z)},
$$
��� $Tr_k(d)$ - k ��������x � ��������� d "���������" ����������, a 
$\rho:\mathfrak{D}\times\mathfrak{D}\rightarrow\mathcal{R}$ - ������� ���������� (�������) 
� ������������ ����������. ������������� ����� k $\sim$ 20-50.

\subsection{������ ������}
\qquad
���������� ��� ��� �������, ������� �� ���� ��������� �� ������:
\begin{itemize}
	\item ������������� ��������������,
	\item ��������� ����,
	\item Support Vector Machines.
\end{itemize}
� ��� ����� ���������� �� ��������� ������.

\subsection{�������� ���������������}
\qquad
�������� ��� ��������� ��������� ���������������. �������� �� ����� ���������� ��� ��������������
� ���� ����� �����������. ������ �������� ������, ������ �������������� �������� ������������, ����
�� ���������� ��������? ���������� ��������� ������� �����������:
\begin{itemize}
 \item \textbf{����� �����������} - ����� ���������, ������� ���� ����������� ���������������.
 \item \textbf{���������� �������� ����������} - ��� ������� �������������� $\Phi'_i$ ������� ����������� ����� $n_i$, 
	   ������� ����� ��������������� ���� ������� ������� �������������� (��� ������ �����, ��� �� �������
       ������������� ����� � $\Phi$, � ��� ��� ����� ����� �������). ����� ������������ ��� ����������
	   ����� ������� �� ������� $\sum_{i}n_i\cdot\Phi'_i(d, c)$.
 \item \textbf{������������ ����� ��������������} - ��� ������� �������������� ���������� ���������, � �������
       �� �������� "�����������". � ����������� �� ��������� �������� ��� ��� ���� �������������.
 \item \textbf{������������ ���������� ���������������} - ����������� ''���������� �������� ����������'' �
	   ''������������� ������ ��������������'', �� ���� � ����������� �� ��������� ���������� ������� �������
		��������������. � �����, ��� � �����, ������������ ����� �������.
\end{itemize}

\section{������ �������� �������������}
\subsection{������ �� ��������������� ������}
\qquad
��� ������ �������� ������������� ������������ ������� �� ��������������� ������, ������� ���� �����������
�� ������� ������.
\begin{itemize}
	\item \textbf{�������:} ��������� ���������� ��������� ���������� �� ��������� � ������ ����������
		  ���������� ���������.
	\item \textbf{��������:} ���� ���������� ������������� �� ��������� � ����� ���������� ��������� 
		  ����������.
	\item \textbf{Benchmarks:} ���������� ������� �� ����������� �������� � ����������� ���������� ����������.
	\item \textbf{������������:} ���� ����� ������������ ���������� �� ���� ����������.
\end{itemize}

� �������, ����� ���� 100 ����������, � ���������� ��������� ����������.
\linebreak
\begin{tabular}{|c|c|c|}
\hline				   &  $\Phi(d, c)=1$ & $\Phi(d, c)=0$ \\
\hline	$\Phi'(d,c)=1$ &  10			 & 15             \\
\hline	$\Phi'(d,c)=0$ &  5			     & 70             \\
\hline   
\end{tabular}

\begin{itemize}
	\item �������      ����� $\frac{10}{10 + 5}  =\frac{2}{3}$.
	\item ��������     ����� $\frac{10}{10 + 15} =\frac{2}{5}$.
	\item ������������ ����� $\frac{70 + 10}{100}=\frac{4}{5}$.
\end{itemize}
���������� ������, ��� ������������� ������ ����� ��������� 0, �� ���� ���������� ���
��������� � ���������� ��������� �, ����� �������� ������������ ����� �����
$\frac{80 + 5}{100}=\frac{17}{20}$. ��� ����� ��������, ������������ ����� ����
������� ��� ��������� �������������� ��������������, ������� �� ����� ������������
� �������������. 

������������� ����� ��������� ��� ������ ������, ������� �������� � ���������, ����� ��������
�� ����������� ���������, �, ��������, �������, ��� �������� �� ������������� ���������, �����
�� �� �����������. ���������� ���� ������ ����� ���� ������, � ����������� �� ��� ��������
�� ��� ���� �������.

\subsection{��������� ���� �������}
\qquad
������ ������, ��������� ���� ������ ��������������� �������� ������� ������, ��� ��� � �����������
�� ������ ������� ������ ��� ����� ������ ��������� ����������. ������� ������
���������� �������������� � ����������� ������������, �� ���������� ���������� ����������, � ����������
''���������'' �������. ��� �� �����, ��� ����� �������� �� �����, ����� ����� ���������, ���� ��
�������� ��������� ����������. ������ ��������, ��� ''���������'' ������������� ������� ''�����������''
�� ����� ������ ����������.

������ ����� ������� � ���, ����� ������� ����� ''���������'' ����������� ��������, � ����� ����������
��� �������������� � ���.
\end{document}
