\documentclass{article}
\usepackage[section]{algorithm}
%\usepackage[section]{algorithm}
\usepackage[noend]{algorithmic}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}

\def\myboxA#1{\vbox{\hrule height0.8pt\hbox{\vrule width0.8pt\kern1pt
      \vbox{\kern1pt#1\kern1pt}\kern1pt\vrule width0.8pt}\hrule height0.8pt}}

\def\myboxB#1{\vbox{\hrule height0.8pt\hbox{\vrule width0.8pt\kern2pt
      \vbox{\kern2pt#1\kern2pt}\kern2pt\vrule width0.8pt}\hrule height0.8pt}}
\def\titlebox#1{\myboxA{\myboxB{\vbox{\hsize \textwidth \noindent #1}}}}
\def\AlgTitle#1#2{\centerline{\titlebox{%
CS6200 Information Retreival 
 \hfill #1}}}

\def \lecturetitle {IR Evaluation} 
 
\title{\lecturetitle}
\date{ \today}
\author{Sanjiv Kumar, Jesse Anderton, Virgil Pavlu}



\begin{document}
\AlgTitle{\lecturetitle}{}
\bigskip
\vspace{15ex}
\begin{centering}
\textsf{\huge{\lecturetitle}} \\
\vspace{3ex}
% \textsf{based on a document by Andrew Ng}
\begin {center} \today \end{center}
\end{centering}
\vspace{5ex}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{IR Ranking, Search Engine Output}
\subsection{comparing search engines}
Web search engines have their ancestors in the information retrieval (IR) systems developed during the last fifty years. IR methods include (among others) the Boolean search methods, the vector space methods, the probabilistic methods, and the clustering methods [BelCroft87]. All these methods aim at finding the relevant documents for a given query.

One of the primary distinctions made in the evaluation of search engines is
between effectiveness and efficiency.Effectiveness, loosely speaking, measures the
ability of the search engine to đnd the right information, and efficiency measures
how quickly this is done. For a given query, and a speciđc deđnition of relevance,
we can more precisely deđne effectiveness as a measure of how well the ranking
produced by the search engine corresponds to a ranking based on user relevance
judgments. Efficiency is deđned in terms of the time and space requirements for
the algorithm that produces the ranking.Carrying out this type of holistic
evaluation of effectiveness and efficiency, while important, is very difficult because of the many factors that must be controlled. For this reason, evaluation is
more typically done in tightly deđned experimental settings and this is the type
of evaluation we focus on here.

To measure ad hoc information retrieval effectiveness in the standard way,
we need a test collection consisting of three things:
\begin{enumerate}
\item A document collection
\item A test suite of information needs, expressible as queries
\item A set of relevance judgments, standardly a binary assessment of either
relevant or non-relevant for each query-document pair.
\end{enumerate}

Given these ingredients, how is system effectiveness measured? The two
most frequent and basic measures for information retrieval effectiveness are
precision(the number of relevant retrieved documents divided by the number of retrieved documents) and recall(the number of relevant retrieved documents divided by the number of relevant documents). One main use is in the TREC (Text retrieval conference, http://trec.nist.gov), where many research groups get their system tested against a common database of documents.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{ Set measures}
There are several matrices that are used to measure the effectiveness of the IR system. The matrices are True Positive (TP), False Positive (FP), True Negative (TN), False Negative (FN). 

First, Let us take a look at precision and recall in more detail. As an example, in an information retrieval scenario, the instances are documents and the task is to return a set of relevant documents given a search term; or equivalently, to assign each document to one of two categories, "relevant" and "not relevant". In this case, the "relevant" documents are simply those that belong to the "relevant" category. Recall is defined as the number of relevant documents retrieved by a search divided by the total number of existing relevant documents, while precision is defined as the number of relevant documents retrieved by a search divided by the total number of documents retrieved by that search. We have the formula for precision and recall as follows:

\begin{equation}
Precision = \frac{num(relevant\ items\ retrieved)}{num(retrieved\ items)} = P(relevant|retrieved)
\end{equation}
\vspace{5mm}
\begin{equation}
Recall = \frac{num((relevant\ items\ retrieved))}{num((relevant\ items))} = P(retrieved|relevant)
\end{equation}

\vspace{5mm}
These notions can be made clear by examining the \textit{confusion matrix}.Given a ranking of documents, we can create a \textit{confusion matrix} that counts the
correct and incorrect answers of each type.

\begin{table}[h!]
\centering
\begin{tabular}{|c|c|c|}
\hline
 & Relevant & Non-Relevant \\ [0.5ex]
 \hline
 Retrived & TP & FP  \\
 \hline
 Non Retrived & FN & TN \\ [1ex]
 \hline
\end{tabular}
\caption{Confusion Matrix}
\label{Table 1:}
\end{table}
\begin{itemize}
\item True Positives(TP) are relevant documents in the ranking
\item False Positives(FP) are non-relevant documents in the ranking 
\item True Negatives(TN) are non-relevant documents missing from the ranking 
\item False Negatives(FN) are relevant documents missing from the ranking
\end{itemize}

Now, we can express precison and recall in terms of confusion matrices terms:

\begin{equation}
Precision = \frac{TP}{TP + FP}
\end{equation}
\vspace{5mm}
\begin{equation}
Recall = \frac{TP}{TP + FN}
\end{equation}

\vspace{5mm}

An obvious alternative that may occur to the reader is to judge an information retrieval system by its \textit{accuracy}, that is, the fraction of its classification that are correct. In terms of the contingency table above,

\begin{equation}
accuracy = \frac{(TP + TN)}{(TP + FP + FN + TN)}
\end{equation}

This seems plausible, since there are two actual
classes, relevant and non-relevant, and an information retrieval system
can be thought of as a two-class classifier which attempts to label them as
such (it retrieves the subset of documents which it believes to be relevant).
This is precisely the effectiveness measure often used for evaluating machine
learning classification problems. 
There is a good reason why accuracy is not an appropriate measure for
information retrieval problems. In almost all circumstances, the data is extremely skewed: normally over 99.9\% of the documents are in the non-relevant
category. A system tuned to maximize accuracy can appear to perform
well by simply deeming all documents non-relevant to all queries. Even if the
system is quite good, trying to label some documents as relevant will almost
always lead to a high rate of false positives. However, labeling all documents
as non-relevant is completely unsatisfying to an information retrieval system
user. Users are always going to want to see some documents, and can be assumed to have a certain tolerance for seeing some false positives providing
that they get some useful information. The measures of precision and
recall concentrate the evaluation on the return of true positives, asking what
percentage of the relevant documents have been found and how many false
positives have also been returned.

\vspace{5mm}

A single measure that trades off precision versus recall is the \textit{F measure},which is the weighted harmonic mean of precision and recall:


* accuracy

* precision

* recall

* F1


\section{Ranking Measures}
* precision, recall @k

* relevant ranks

* Average Precision

* R-precision

* Reciprocal rank

\subsection{ROC and Precision-recall curves}


\subsection{nDCG}
* gains - transform grade in usefulness/benefit. What do grades mean? Essentially a benefit model

* discounts - transforms ranks into utility. How much gains still matter as we go down the list? Essentially a user model

* DCG = dot product between gains and discounts

* nDCG = DCG normalized




\section{Test Collections}
* why we ned them

* how do we create them

* QREL files

* utility of datasets

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Significance tests}

* why we need them

* popular tests

\section{Manual Assessment}
* create your own QREL

* assessment disagreemnts, fatigue

* experts vs users vs random people

\subsection{Crowdsourcing}
* cost vs benefit

* noise

* quality assurance 

\section{User Studies}

* users vs metrics

* selecting users

* IRB

* types of studies

* types of measurements
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{document}


