%\documentclass{article}
%\usepackage{graphicx}

%\newcommand{\be}{\begin{enumerate}}
%\newcommand{\ee}{\end{enumerate}}
%\newcommand{\bi}{\begin{itemize}}
%\newcommand{\ei}{\end{itemize}}
%\newcommand{\tion}[1]{\S\ref{sect:#1}}
%\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
%\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
%
%\newcommand{\setuptabs}{
%\hspace*{.3in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.1in}
%\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}
%\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\=\hspace*{.2in}\kill
%}
%
%\begin{document}


\section{User Feedback Mechanisms}

\subsection{Motivation}

Without any sort of user feedback mechanism, the use of HAMLET is a one-time static process.
The user will enter their input design and look at the space of similar objects. Some of those
similar artifacts will be useful in the design process. However, it is equally likely that some of these
"similar" objects will be unhelpful. This is why some form of a user feedback mechanism could be helpful. 

A user feedback mechanism could make this static process into a repeatable interactive one. 
The preferences expressed during one stage of the design process could bias future iterations of the same
design. During a single session, a query could be run over and over, with the user rating additional items each time.  

As a user searches the space of similar artifacts, they could mark these items as "liked" or "disliked."
This set of preferences could be used on subsequent iterations of the same query to bias the results. 
In HAMLET, the Rochio user feedback formula is used to move the point in space that the query represents to
another spot. Ideally, this new location is "closer" to more relevant results. 
As more items are rated, this point will continue to move within the space of document results.

\subsection{What is the Rochio Formula?}
All information retrieval systems, including HAMLET, suffer from false alarms; i.e.
returning query results that the user does not find relevant.

The Rochio algorithm
is a standard method for
pruning the results of an informational retrieval
search with user feedback~\cite{hayes06,hayes07}
The 
algorithm reports the delta between
the positive document vectors (that related to membership of the positive examples
approved by the user)
and the negative ones (that relate to membership of the negative examples
disapproved by the user).

Given a set of documents $D_{q}$ encompassed by query $Q$, you can separate the documents into two distinct subsets of liked ($L_{q}$) and disliked ($U_{q}$)
documents. 
The normalized TFIDF vectors of those two subsets are summed and weighted by tuning parameters ($\alpha$,$\beta$, and $\chi$) that are determined via experimentation
but Joachims recommends weighting the positive information four times higher than
the negative~\cite{joachims97}.
They are then divided by the size of each set.
These summations are then used to tune the original query vector as follows:

\begin{equation}\label{eq:rochio}
{Q_n = \alpha Q_{n-1} + \frac{\beta}{|L_q|} \sum_{d{\in}L_q} d - \frac{\chi}{|U_q|} \sum_{d{\in}U_q} d 
}\end{equation}

According to Dekhtyar et al /cite{hayes07}, placing emphasis on the positive elements (liked documents in our example) may improve the recall (new relevant articles may be found) while emphasizing the negative (disliked documents) may affect precision (false positive may be removed).

This equation is recursive in nature. When a new query is supplied by the user, 
the formula uses that as $Q_{n-1}$. The resulting query, $Q_{n}$ becomes $Q_{n-1}$ during the next
iteration. Each round, the point in space moves slightly more in a direction taken from the centroid of the
liked documents and the centroid of the disliked documents.  

\subsection{HAMLET and Rochio}

Although the Rochio formula has not been used in prior HAMLET-like systems, it seemed to be the most 
appropriate user feedback mechanism for the purposes of this project. The Rochio formula is a standard 
technique in the information retrieval field because it is based on the 
concept of TF*IDF, which is a concept used heavily within HAMLET.  
Rochio has yielded strong results in systems that share common IR and machine learning techniques with HAMLET.
It is for this reason that Rochio was chosen as the initial user feedback mechanism. 

\begin{figure}[!h]
\begin{center}
\includegraphics[width=3.5in]{screens/feedback/cycle.png}
\end{center}
\caption{The user-feedback cycle}
\label{fig:cycle}
\end{figure}

This chart illustrates the user feedback cycle during a session with HAMLET. 
The user supplies a query in text form in the HAMLET browser window. 
Once the run button is clicked, this query is cleaned up and any unnecessary terms are removed. 
The TF*IDF scores are calculated and normalized for the remaining terms. 
At this point, the Rochio formula is applied to the user's query as explained in the previous section. 
This modified query is saved in memory then passed off to the classifier, which returns a set of results. 

\begin{figure}[!h]
\begin{center}
\includegraphics[width=4.5in]{screens/feedback/1.png}
\end{center}
\caption{Initial Query Run}
\label{fig:queryStart}
\end{figure}

\begin{figure}[!b]
\begin{center}
\includegraphics[width=2.25in]{screens/feedback/2.png}
\end{center}
\caption{Results after items have been rated.}
\label{fig:queryRated}
\end{figure}
 
\begin{figure}[!t]
\begin{center}
\includegraphics[width=4.5in]{screens/feedback/3.png}
\end{center}
\caption{User Preferences Tab}
\label{fig:queryPrefs}
\end{figure}

\fig{queryStart} represents the initial state when HAMLET is started 
and the dataset is loaded. 
A query is entered by the user. In this case, the query is a bug report for HAMLET itself 
and the dataset is the JAVA codebase of HAMLET. At this point, no user preferences have been recorded.
Therefore, the results in the left panel are based solely on the text content of the query. 

At the point depicted in \fig{queryRated}, several items have been rated as "liked" or "disliked" by the user. 
The query has been 
re-run with these preferences in mind, and a new set of results has been generated. As you can see in the left 
panel, results that have been recorded during previous runs are marked with a + (helpful) or a - (unhelpful).
The total number of returned results is displayed at the bottom, along with counts of old liked and old 
disliked results that are still considered to be nearby. 

As you can see in \fig{queryPrefs}, a seperate tab displays a complete list of rated documents.
The number next to the name is the vertex's unique identifier in the dataset's graph.  
A set of buttons along the bottom let you "rerate" a document or reset it to neutral as desired. 

\subsection{Future Plans}

Now that the Rochio user feedback loop is in place, the next step 
is to begin with user trials. We know that the implementation works. 
What we don't know is whether or not the altered results are useful. 
This is what real-life trials will tell us. 

Current plans call for a local user trial using university students. 
JAVA will be the technical document of choice because 
every student in the Computer Science program will have a certain level 
of expertise with the language. Another reason to favor JAVA is that there are 
a large number of open-source JAVA projects that could be used for data sets.
Our current JAVA data set is based on the HAMLET code base, but future sets could
include data from the Eclipse project or the jEdit program. 

For each data set, a certain number of queries will be prepared. In general, these queries will
be taken from the text of bug reports. Users will be given a 
random data set and query to test. They will interact with HAMLET over multiple cycles of the user
feedback loop, taking notes about the results returned. Although the queries and data sets are
controlled, the individual like/dislike decisions made by the user will be unique and will
depend on their level of domain knowledge. 

The purpose of user trials is to test the usefullness of the feedback mechanisms. 
These trials mirror real-life use of the HAMLET software, and the data recorded by these users
should yield interesting results. Some of this data could include the number of new documents returned, the number of rated documents that remain in the list, and how many of those are liked or disliked. 
Knowing how many rounds of feedback that a user has to go through to find the class they are looking for 
should provide a good starting place for the future improvement of these mechanisms. 

Because of the recursive nature of the Rochio formula, fewer new results will be found as more items have been
rated. Over time, the point in space that your query represents will move less and less. 
Eventually, no new results will be returned. To escape this trap, Viapianni et al ~\cite{pu06} have found
it useful to always replace a certain percentage of your results with "suggestions." These suggestions should
be similar items, but different enough that they would not normally be returned with the nearest neighbors. 
They propose several different ways to generate these suggestions. Any of the methods that they suggest
could be implemented in the HAMLET system.


