\documentclass[10pt]{article}
\usepackage{rotating}
\usepackage{lineno,times,graphicx}
\usepackage{url}
\usepackage{alltt}
\title{\vspace{1cm}\includegraphics[width=2in]{HamletSkullHCSealous.jpg}\\\vspace{1cm}
About The HAMLET Project: Year 2,  Report1\vspace{1cm}}
\author{Tim Menzies\\LCSEE, WVU\\\url{tim@menzies.us}}
\date{}
\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}}
\usepackage{lastpage,fancyhdr}
%\footrulewidth 0.0pt\headrulewidth 0.1pt
\lhead{}\rhead{}\chead{}\rfoot{}\lfoot{}\cfoot{}
\rhead{ {\scriptsize 
\date{\today}
}}

\rhead{{\scriptsize 
\date{\today}
}}
\lhead{\includegraphics[width=6cm]{wvulogo.jpg}}

\usepackage{eso-pic}
\usepackage{color}
\usepackage{type1cm}
%\makeatletter
%  \AddToShipoutPicture{%
%    \setlength{\@tempdimb}{.5\paperwidth}%
%    \setlength{\@tempdimc}{.5\paperheight}%
%    \setlength{\unitlength}{1pt}%
%      \makebox(600,900){\rotatebox{45}{\textcolor[gray]{0.9}{\fontsize{3cm}{3cm}\selectfont{Not for release}}}}}
%\makeatother
\usepackage{graphicx}

\begin{document}
%\linenumbers
\maketitle
\thispagestyle{fancy}
\pagestyle{fancy}

\vspace{1cm}{\bf About this document:}
This document reports:
\bi
\item
 deltas from previous reports (including clarifications and corrections).
This report describes progress on the HAMLET ``anything browser''.
It updates a prior version of this document, released mid-year.
See the {\em Change Log} 
on page 3 for a list of differences.

\newpage
\rhead{\thepage\ of \pageref{LastPage}}
\lhead{Menzies: HAMLET - progress report}
\tableofcontents

~\\
~\hrule~ 
~\\

\noindent
{\bf Change log:}

\begin{center}{\small

\begin{tabular}{|p{0.5in}|p{4in}|}\hline
September 30,2008&
\vspace{-0.3cm}
\begin{description}
\item[page 3] Change log added
\item[page \pageref{sect:newview}] New concept of operations 
and, on page \pageref{fig:HAMLEThotel}, a  new concept of operations graphic
\item[page \pageref{sect:whyHAMLET}] Overview section \tion{whyHAMLET}
motivating the use of this tool. 
\item[page \pageref{sect:session}] The example in \tion{session}
has been complete overhauled. Previously, our STEP parser was incomplete
and we presented an example using JAVA. Now, our STEP parser
is functioning and we can present detailed STEP examples.
For other information on our new
STEP cases studies, see
 also \fig{trim} (on page \pageref{fig:trim})
and the clustering analysis of 
\fig{ap203} (on page \pageref{fig:ap203})
and 
\fig{ap214} (on page \pageref{fig:ap214}).
\item[page \pageref{fig:vis3d}] Our prior distance functions
had some nonlinearities that now been fixed. \fig{vis3d} shows
a new design (in red) floating near its nearest related concepts
(in green).
\item[page \pageref{sect:parsing}] \tion{parsing} describes
our new generic parsing protocol. The goal of this protocol
is to enable the rapid creation of new new parsers for a wide
range of technical document types.
\item[page \pageref{sect:clustering}] 
HAMLET now contains three working tools.
\tion{clustering} describes the K-Means, canopy, and GENIC clustering
algorithms.
\item[page \pageref{fig:ap203} and \pageref{fig:ap214}]  We are very pleased with the 
clustering results reported here. Our new clustering algorithm (GENIC)
runs hundreds to thousands of times faster than conventional methods
(K-MEANS).
In theory, we now have the tool kit that will scale (and this optimism
will be tested in future reports).

\end{description}
\\\hline
August 18,2008
&
Preliminary progress report released
\\\hline
\end{tabular}}
\end{center}


\newpage
\listoffigures
\newpage
\section{Summary}
WVU's work into long-term document retention divides into immediate and long-term
investigations:
\bi
\item The immediate concern is for an assessment of the STEP/EXPRESS language for handling
long-term data retention.
For information on the immediate work, see the reports
from Victor Mucino.
\item Other, more long-term work, is exploratory in nature.
This paper is about HAMLET, which is one example of the exploratory work. 
\ei

HAMLET is an ``anything browser'' that aims to offer advice on what engineering parts are
relevant to a partially complete current design. 

HAMLET makes minimal assumptions about the 
nature of the engineering documents being explored
and  is designed to be ``glue'' that permits the searching of
technical data in large
heterogeneous collections.

Using technology from
AI,
information retrieval, program comprehension, and text mining,
HAMLET allows designers to dig up prior designs, study those designs,
and apply any learned insights to new tasks.

\begin{figure}[!b]
\begin{center}
\includegraphics[width=5in]{archeology.jpg}
\end{center}
\caption{Digging up old designs. From \protect\cite{booch04}.}
\end{figure}

\newpage
\section{What is HAMLET? (overview)}
\subsection{A New View on HAMLET}\label{sect:newview}

HAMLET was originally conceived as a single application.
This ``anything browser'' was designed to glue  together and search
technical data in large
heterogeneous collections.
To achieve this goal, HAMLET offers the following operations:
\bi
\item Provides an import facility from a variety of artifacts. The generic
parsing facility is designed to be extensible so, in theory, it would be possible
to extend the range of artifacts processed by HAMLET.
\item
Provides standard visualization techniques for those artifacts; e.g. 
fast graphical browsing of used and  used-by links.
While state-of-the-art, these standard visualization techniques quickly
overload and exhaust the user (for example,
see 
\fig{fig8}). Hence, HAMLET uses  
AI, text mining, program comprehension techniques, and information retrieval techniques to offer
a set of filtered views on the data.
\ei
\begin{figure}
\begin{center}
\includegraphics[width=5in]{screens/8.jpg}
\end{center}
\caption[Too many neighboring concepts]{
Too many neighboring concepts: note the overdose
of information resulting from a simple visualization
of the query ``what terms are used by the code
in the left-hand-side screen?'' 
This figure shows the terms referenced by the code
sample on the left-hand-side to a depth of eight links
(i.e. directly references, referenced by something referenced
in the left-hand-side code, referenced by something referenced by
something referenced in the left-hand-side code and so on to
a nested depth of maximum eight links). 
The depth of nesting for the query is controlled by the 
slider at bottom right.
The code snippet is in JAVA but a similar query on an EXPRESS
schema would result in a similar information overload.
The lesson of this figure is that special tools are required:
we should not show {\em all} the nested references; just the
{\em relevant} ones.
HAMLET's display of relevant local information is shown in \fig{sample}.
}\label{fig:fig8}.
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[width=5in]{hamlet_label.png}
\end{center}
\caption[Our toolkit]{Our toolkit is a
set of libraries, on top of which we can implement
multiple user-level tools.
}\label{fig:HAMLEThotel}
\end{figure}

HAMLET's concept of operation has since changed. It has been realized
that the above operations can support a wide variety of activities:
\bi
\item Originally, we were targeting a  ``what else'' and ``what not'' design
agent that found the delta between a partial description of 
a current design to other designs.
\item
Now, we view HAMLET as a reconfigurable library of technical specification
comprehension tools. This library supports ``what else'' and ``what not''
but could be made to support many other specification comprehension 
applications such as concept location, validation, etc.
\ei
\fig{HAMLEThotel} shows the new concept of operations. The application
previously known as HAMLET is built on top of a large library of
other tools that can be mixed and matched as required.

This new view of HAMLET is very recent and we have yet to take advantage
of this new HAMLET-as-library architecture.
Future versions of this document will try to exploit this new view.
The rest of this document focuses on the use of this architecture
for our standard ``what else'' / ``what not'' task.

\clearpage

\subsection{What Else, What Not}
HAMLET was named after the famous Shakespeare quote
``to be or not to be?'' For the designer of an technical 
product, the analogoous question is ``to do or not to do?''
HAMLET finds the deltas between the current design and
old design to compute:
\bi
\item ``What else'': what is {\em absent} from
 the current design but is usually {\em present} in older designs.
\item ``What not''; what is {\em present} in the
current design but is usually {\em absent} in older designs.
\ei
\fig{sample} offers an example of these two lists.
\begin{figure}[!b]
\begin{center}
\includegraphics[width=5in]{screens/2.jpg}
\end{center}
\caption[A sample HAMLET screen]{A sample HAMLET screen. To the left are the nearest concepts to your new design. 
The right side contains information from the chosen nearby design. This includes the original text as well as attributes 
pulled by the parser. 
In the nearest concepts, there exists certain concepts not found in the new
design.
These are  shown in the {\em what else} list in the center.
Also, the new design  contains certain concepts not found in the nearest
concepts. These are shown in the {\em what not} list (also, center).
}\label{fig:sample}
\end{figure}
Note that designers are not obliged to always add the ``what else'' results or always avoid the 
``what not'' results. However, those two queries will allow a designer to assess their current 
design with respect to the space of prior designs.

Once HAMLET returns these lists,
the designer and HAMLET enter a feedback loop where the designer reviews HAMLET's ``what else'' and ``what not'' list. HAMLET learns the designer's preferences and, subsequently, uses
that knowledge to offer results relevant to that user's current design task. 

From the feedback loop, preference knowledge can be learned. Given a community of designers
working on related tasks, HAMLET will be able to quickly learn what prior designs are relevant
for that community.
\subsection{Related Work}
HAMLET draws on much of the literature on AI, information retrieval, text mining,
and program comprehension.
Formally, HAMLET is a 
{\em suggestion system} that augments standard queries
with (a)~suggestions that near to the current partially incomplete
design and (b)~suggestions of additions to the current design
that would make it very unusual with respect to the space
of all prior designs~\cite{pu06}.

Having said that,
the comprehension of archival technical documentation
has certain attributes that make HAMLET's task different to other systems:
\bi
\item
Zhai et al.~\cite{Zhai04across-collection}
discuss  cross-collection mixture models that seek to discover latent common themes
from large document collections.
This work assumes that all documents are expressed in a simple ``bag of words''
model (i.e. no links between documents). In HAMLET, on the other hand,
documents are stored in  a connected graph showing neighborhoods of related terms. 
\item
The HIPIKAT system of \v{C}ubrani\'{c} and Murphy~\cite{murphy03} explores
comprehension of heterogeneous
technical products.
 Software development projects produce a large number of artifacts,
 including source code, documentation, bug reports, e-mail, newsgroup
 articles, and version information. The information in these artifacts
 can be helpful to a software developer trying to perform a task,
 such as adding a new feature to a system. Unfortunately, it is
 often difficult for a software developer to locate the right
 information amongst the huge amount of data stored.
HIPIKAT recommends relevant software development artifacts based on the context in which a developer requests help from HIPIKAT. While a landmark system, HIPIKAT is hard-wired into
a particular set of development tools (ECLIPSE) and the scalability of the tool
has not be demonstrated by the authors.
\item
Hill et al.'s DORA system~\cite{1321637}
stores JAVA programs using a combination of
``bag of words'' as well as neighborhood hood information. Searching in DORA
is two-fold process where:
\bi
\item
Information retrieval on the bag of words
finds candidate connections
\item
Topology queries on  the candidates' neighbors returns 
the strongly related terms.
\ei
The drawback with DORA is that it assumes a homogeneous corpus
(everything in DORA is a JAVA class) and its search algorithms
will not scale to very large examples (since they are slower
than linear time and memory).
\ei
\section{Why HAMLET? (motivation)}\label{sect:whyhamlet}
\subsection{Background}
A recent NSF-funded workshop\footnote{
Collaborative Expedition Workshop \#74, June 10, 2008, at NSF.
``Overcoming I/O Bottlenecks in Full Data Path Processing: Intelligent, Scalable Data Management from Data Ingest to Computation Enabling Access and Discovery''.
\url{http://colab.cim3.net/cgi-bin/wiki.pl?ExpeditionWorkshop/TowardScalableDataManagement_2008_06_10}
} 
 highlighted current directions
in long term technical document retention. While much progress was reported
on:
\bi
\item
systems issues of handling and sharing very large data collection (e.g. SLASH)
\item
scalable methods of building customization views (e.g. iRODS),
\ei
there was little mention of the cognitive issues of 
how users might 
browse and  synthesize
data from massive data collections of technical documents.

For example, here at WVU, we are mid-way through a review of the
use of STEP/EXPRESS for long term technical document retention\footnote{See
reports from Mucino.}.  STEP/EXPRESS is commonly used as an
inter-lingua to transfer technical data between CAD/CAM packages.
Strange to say, while STEP/EXPRESS is useful for transferring and
understanding technical documents {\em today}, it does not appear
to be suitable for understanding technical documents from {\em
yesterday}.

In theory, there is nothing stopping STEP/EXPRESS from
recording and storing
all aspects of a project.  In many ways, STEP/EXPRESS is
as expressive as other technical document standards (e.g. UML).
STEP/EXPRESS offers a generic method for storing part-of and isa
information, constraints, types, and the rules associated with a
technical document.
However,
in practice, the theoretical potential of STEP/EXPRESS is not realized for
the following reasons.
 
\subsubsection{Heterogeneity}
The reality of archival
systems is that  STEP/EXPRESS documents
are stored {\em along side} a much larger set of supporting documents in multiple formats.
A recent study\footnote{\url{http://www.b-eye-network.com/view/2098}} concluded that
\bi
\item
     80 percent of business is conducted on unstructured information.
\item     85 percent of all data stored is held in an unstructured format
(e.g.  the unstructured text descriptions of issues found in PITS).
  \item   Unstructured data doubles every three months.
\ei
That is, if we can learn how to understand large heterogeneous collections
that include
STEP/EXPRESS knowledge as well as numerous other products
in a wide
variety of formats,
it would be possible to reason and learn from a very wide range of
data.
\subsubsection{Incomplete meta-knowledge}
A lot of work has focused on the creation
of cached sets of EXPRESS schemas. Forty such {\em application protocols} (AP) have been defined~\cite{jardim06}
including 
AP-203 (for geometry)
and AP-213 (for numerical control).  The list of currently defined application protocols
is very extensive (see \fig{aps}).
These APs are the cornerstone of STEP tools: the tools offer specialized support and screen
 import/export facilities for the APs.
While much effort went into their creation of these APs, very few have been stress-tested
in the information systems field. That is, the majority of these APs have 
been {\em written} more than they have
been {\em read} (exceptions:  the above-mentioned AP-203 and AP-213 are frequently used and reused in 
$21^{st}$ century CAD/CAM manufacturing processes),
\subsubsection{Incomplete tool support}  Perhaps because of the relative immaturity of the APs, current
CAD/CAM tools offer limited support for the STEP APs. While most tools support geometry (AP-203), the
support for the other  APs in \fig{aps} is minimal (to say the least).
\subsubsection{ Incomplete design rationale support} 
From a cognitive perspective, STEP/EXPRESS does not support the entire design cycle.
Rather, it only supports the last stages of design and not all of the interim
steps along the way. 
\subsubsection{Limited Historical Use}
For all the above reasons, highly structured technical documents in formats like STEP/EXPRESS
are in the minority in the archival systems
we have examined.  We are aware of large STEP/EXPRESS repositories
but these are often inaccessible for a variety
of reasons.

While this situation might change in the future (e.g. if
all the above issues were suddenly fixed and all organizations switch to using highly
structured technical documentation), the historical record would still be starved
for large numbers of examples.

\begin{figure}
\begin{center}
\begin{tabular}{ll}
AP & area\\\hline
201  &   	Explicit Drafting\\
202  &   	Associative Drafting\\
203  &   	Configuration Controlled Design\\
204  &   	Mechanical Design Using Boundary Representation\\
205  &   	Mechanical Design Using Surface Representation\\
206  &   	Mechanical Design Using Wireframe Representation\\
207  &   	Sheet Metal Dies and Blocks\\
208  &   	Life Cycle Product Change Process\\
209  &   	Design Through Analysis of Composite and Metallic Structures\\
210  &   	Electronic Printed Circuit Assembly, Design and Manufacturing\\
211  &   	Electronics Test Diagnostics and Remanufacture\\
212  &   	Electrotechnical Plants\\
213  &   	Numerical Control Process Plans for Machined Parts\\
214  &   	Core Data for Automotive Mechanical Design Processes\\
215  &   	Ship Arrangement\\
216  &   	Ship Molded Forms\\
217  &   	Ship Piping\\
218  &   	Ship Structures\\
219  &   	Dimensional Inspection Process Planning for CMMs\\
220  &   	Printed Circuit Assembly Manufacturing Planning\\
221  &   	Functional Data and Schematic Representation for Process Plans\\
222  &   	Design Engineering to Manufacturing for Composite Structures\\
223  &   	Exchange of Design and Manufacturing DPD for Composites\\
224  &   	Mechanical Product Definition for Process Planning\\
225  &   	Structural Building Elements Using Explicit Shape Rep\\
226  &   	Shipbuilding Mechanical Systems\\
227  &   	Plant Spatial Configuration\\
228  &   	Building Services\\
229  &   	Design and Manufacturing Information for Forged Parts\\
230  &   	Building Structure frame steelwork\\
231  &   	Process Engineering Data\\
232  &   	Technical Data Packaging\\
233  &   	Systems Engineering Data Representation\\
234  &   	Ship Operational logs, records and messages\\
235  &   	Materials Information for products\\
236  &   	Furniture product and project\\
237  &   	Computational Fluid Dynamics\\
238  &   	Integrated CNC Machining\\
239  &   	Product Life Cycle Support\\
240  &   	Process Planning\\
\end{tabular}
\end{center}
\caption{STEP Application Protocols.}\label{fig:aps} 
\end{figure}


\subsection{Why Use HAMLET To Examine Data?}\label{sect:whyHAMLET}

\begin{figure}[!b]
\begin{center}
\includegraphics[width=3.5in]{whyhamlet.png}
\end{center}
\caption{Looking at data using HAMLET has several visualization advantages
}\label{fig:whyHAMLET}
\end{figure}

The most obvious reason for using HAMLET to look at a corpus of technical documents
is its
visualization value. Let's say that your collection
contains thirty STEP documents and the EXPRESS schema that they all
relate to.  If you just looked through those documents, you'd be
faced with a complete information overload.  That's thirty-one
separate text files to stare at, some with over a thousand lines
of code.

HAMLET provides an easy-to-use interface to visualize that data and
make deductions based on the raw content (see \fig{whyHAMLET}). The document panel lists
only the documents that are relevant to your query (which can be a
STEP design that you like). You can click on one of those documents
ans view the raw text as well as key attributes of that file. This
prevents the information overload associated with the raw files by
only giving you relevant information in a more organized fashion.

HAMLET's graph tools provide another key visualization advantage.
The two-dimensional graph shows the nearby documents and how they
relate to each other. For example, if your data is written in STEP, the graph maps how
the STEP designs relate to their associated schema. HAMLET's
three-dimensional graph provides a visual tool that allows you to
quickly look at how close certain designs are to your query.

The power of HAMLET is not just in the formatting of data, it is
also in the machine learning techniques that allow you to dive
deeper into the data.  Clustering algorithms and classifiers ensure
that only relevant data is displayed, and user feedback mechanisms
ensure that the experience is tailored to the individual user.

\subsection{Under the Hood}
\subsubsection{Generic Parsing}
Internally, HAMLET makes minimal assumptions about the form of the technical document:
\bi
\item 
A document
contains slots and slots can be atomic or point to other documents;.
\item
The network of pointers between documents presents the space of connected designs.
\ei
A generic parser class implements a standard access protocol for this internal model.
By sub-classing that parser, it is possible to quickly process new documents types.
Currently, HAMLET's parsers can import:
\bi
\item STEP/EXPRESS
\item Florida Law (XML)
\item Text documents structured as follows: sub-headings within headings, paragraphs
within sub-headings, sentences within paragraphs, words in sentences;
\item JAVA:  
This JAVA import allows ready access to very large corpora of
structured technical information (i.e. every open source JAVA program
on the web). Hence, in the sequel, we will make extensive use of
JAVA examples since that permits tests of scalability.
\ei
\subsubsection{The Geometry of Design}  
HAMLET treats technical document comprehension as a geometric problem:
\bi
\item
Old designs are clustered into groups. 
\item A new design can be placed at some point around those clusters. 
\item To compute ``what else,'' HAMLET finds the cluster nearest the new design and 
looks for differences between the new design and the average design in that cluster.
\item
To compute ``what not,'' HAMLET looks for parts of the current design that are not usually
found in the nearest cluster.
\ei
While simple in concept, the challenge of HAMLET is three-fold:
\be
\item Doing all the above in a scalable manner; i.e. linear or sub-linear time
processing. HAMLET handles this is a variety ways including methods borrowed from Google.
\item
Doing all the above for a heterogeneous corpus.
HAMLET handles multiple formats in the corpus by storing them all documents in a minimalistic
internal format
(a document
contains slots and slots can be atomic or point to other documents).
\item
While the minimal format permits rapid extension of HAMLET to other document types,
it raises the issue of false alarms.
Like any information retrieval task, HAMLET returns some false negatives (i.e.
incorrect ``what not'' results)
and false positives (i.e. incorrect ``what else'' results).
HAMLET therefore builds profiles for each user based on their particular preferences.
\ee

\newpage 
\section{A Session With HAMLET}\label{sect:session}

\subsection{The Preprocessor}
HAMLET contains several components other than the UI shown below. One such component is the
pre-processor, a tool used by HAMLET to generate datasets which
can then be loaded into the UI allowing the user to query,
rank, and visualize the documents found in the loaded dataset.
The majority of all machine learning takes place within the
pre-processor.  This is where tasks like term frequency / document
frequency generation, term selection, clustering, and learner
training occurs.  After being run through the pre-processor, each
document within a collection is assigned a vector representation
which describes what terms are present in the document and at what
frequency.
 

\begin{figure}[!h]
\begin{center}
\includegraphics[width=5in]{screens/blank.jpg}
\end{center}
\caption{A HAMLET screen.
}\label{fig:scream}
\end{figure}



\newpage
\subsection{HAMLET output}

Pictured below is HAMLET's output after running a given query (the
unit data text box).  The results are shown in the far left box.
The far right boxes (what else and what not) describe the deltas
between your query and the currently selected item in the list on
the left side.  {\em What else} can be described as ``what do I need to
add to my thing to make it more like the selected thing,'' while
{\em what not} is more like ``what do I need to remove from my thing to
make it more like the selected thing.''  The sample dataset being
run here was built from a corpus of STEP documents corrusponding to AP 203.



\begin{figure}[!h]
\begin{center}
\includegraphics[width=5in]{screens/2.jpg}
\end{center}
\caption{HAMLET output.
}\label{fig:out}
\end{figure}


\newpage
\subsection{A Web of Connections}
HAMLET is a framework that supports the both the {\em semantic} and
the {\em syntactic} structure inherent in data.  Displayed below
is an example of the former, a web of hyper-links connecting relevant
document to each other (generated from STEP/EXPRESS data).  When
this kind of information is combined with syntactic information
(the actual text of a document, e.g. term counts) a powerful
information retrieval system can be created that supports the ability
to {\em walk} through the data.  In our application, by clicking
on a document in the graph, you are shown all of the documents
connected to the selected document.  By hopping from document to
document and tweaking visualizations parameters along the way, it
is possible to truly walk through the dataset.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=5in]{screens/1.jpg}
\end{center}
\caption{Displaying connections.
}\label{fig:wb}
\end{figure}

\newpage
\subsection{3-D Visualization}
In addition to visualizing 2-D semantic information, HAMLET also
supports the ability to visualize each document vector as a point
in 3-D space.  To facilitate this, HAMLET utilizes dimensionality
reduction in two stages.  In the first stage, the list of all
possible terms in a given collection is analyzed to determine the
most relevant terms (this reduces the dimensionality from around
20,000 to 100).  In the second stage, the 100 dimension document
vectors are run through a fast (nearly linear) dimensionality
reduction algorithm called FastMap which finds the intrinsic geometry
in the 100 dimensional space and projects that into a 3-D space
capable of visualization.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=5in]{screens/3d_plot_4_ver2.jpg}
\end{center}
\caption[3-D visualization]{ 3-D visualization.
A new design (in red) floats near its nearest related concepts
(in green). The gray points show parts of specifications that are
less relevant to the new design. Note that this is a 2-D visualization
of a 100-D space.
}\label{fig:vis3d}
\end{figure}

\newpage
\subsection{User Profiles}

HAMLET gives each user a unique profile that is stored on the local machine.
During a typical HAMLET session, the user can indicate 
whether they like or dislike a particular document. 
HAMLET utilizes the latest semantic analysis
techniques to bring documents similar to those rated as liked to
the top of query results, while filtering out the documents disliked.
The weights applied to whole documents by the user ratings are also applied to the terms within that document, and the "what-else/what-not" list is weighted by the sum of all ratings on each term in the list. 

\begin{figure}[!h]
\begin{center}
\includegraphics{screens/hello.jpg}
\end{center}
\caption{Logging in.
}\label{fig:logging}
\end{figure}

The user profile itself is stored in a comma-separated CSV file. 
Each row is a term and each column is a document 
(identified by its unique vector ID). Datasets are kept 
separate within the profile so that vector IDs do not overlap. 
A document that is liked receives a rating of 1, 
disliked are rated -1. A -2 means that the term is not found 
within that document. A total is kept at the end, 
which is used for ranking purposes.

\begin{figure}[!h]
~\hrule~
{\scriptsize
\begin{verbatim}
%Timothy Menzies

%dataset #1
Term,Vector,Vector2,Vector3,Total
Bob,-1,1,1,1
Alice,-2,1,-2,1
Jimmy,-1,-2,1,0\end{verbatim}}
~\hrule~
\caption{A simple user profile.
}\label{fig:up}
\end{figure}

\newpage
\section{How Does HAMLET Work? (the details)}
This section offers a technical description of the internals of HAMLET. 
In that description,
the term ``document'' will be used since that is consistent with the information
retrieval literature. Note that HAMLET's ``document'' may be much smaller than,
say, a Microsoft Word .doc file. 
A HAMLET ``document'' is just the smallest unit of comprehension for a particular
type of entry in  an archive.
Indeed, depending on the parser being used,
a ``document'' may be:
\bi
\item An EXPRESS data type
\item A JAVA method
\item A paragraph in an English document
\item Some XML snippet.
\item All text associated with an archived engineering project
\ei

The methods described in this section are in a state of flux. HAMLET is a prototype system
and we are constantly changing the internal algorithms. In particular:
\bi
\item All slower-than-linear algorithms are being replaced with linear algorithms.
\item Our preliminary experiments suggest that many common methods may in fact be
superfluous for comprehension of technical documents. For example: (a)~we may soon be dropping
the stopping and stemming methods described below; (b)~the value of discretization
during InfoGain processing is not clear at this time. 
\item
Any threshold value
described in this 
section (e.g. using the top $k=100$ Tf*IDF terms) will most probably change in the very near
future as we tune HAMLET to problem of archival storage.
\ei
\subsection{Parsing From Native Formats}\label{sect:parsing}

HAMLET utilizes a generic parsing framework that provides 
an interface between existing parsed data
and information retrieval, text mining and program comprehension 
methods supported by HAMLET. This
allows both safe access to the data at run-time, 
as well as easy implementation. A brief, high-
level overview of the main functions of this framework is discussed below.

\subsubsection{Parsed Languages}

Since HAMLET makes as few assumptions about a technical document 
as possible, any language could theoretically be parsed and used 
within the user interface.
The HAMLET parsing API provides an interface for creating the XML 
format that the HAMLET interface reads. 
Parsers have been provided that process data authored in the following formats: 
\bi
\item STEP/Express
\item Plain Text
\item Florida Law (XML)
\item HTML
\item Java
\ei
The above formats were chosen according to:
\bi
\item
Their relevance to 
this project- so STEP is highest;
\item
 As well the availability of  large
corpora- so we use JAVA class libraries and a large XML
dump pf 400 years of Florida real estate law.
\ei

\subsubsection{HAMLET Parsing API}

HAMLET's language-specific subparsers comb through individual files 
and pull out important bits of information (entities in STEP, methods in Java). 
While processing individual files, these subparsers collect information about each document. 
Some of that information includes pointers to the parsed information and information about what entities are used by others. 
The HAMLET generic parsing framework provides several methods to utilize
these data attributes.

The most important function of the API is the generation of the GraphXML file. 
This file is the intermediary between the data set and HAMLET. It
contains a list of each document (vertice) and the relationships between
them. Other pertinent information, such as file pointers and 
document statistics, is stored in the form of attributes for each 
document vertice. 
From a higher level, the collection of these pointers
to files gives a view of the region of interconnected designs, 
giving HAMLET the ability to make its
decisions and provide suggestions based on what it has already learned.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=4.5in]{screens/graph.png}
\end{center}
\caption{One vertice and the information associated with it.
}\label{fig:vertice}
\end{figure}

For certain language imports, such as Java or STEP, HAMLET utilizes edge
generation to determine the relationship of one design to another. 
For instance, if a call graph is generated
on a set of Java source files, 
an edge can be placed between a multitude of methods and calls made to
and from them. The XML graph generated by the parsing API includes 
both the document vertices and the edges that connect them. 
This is essential for visualization purposes and provides a 
wealth of syntactical information.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=2.5in]{screens/edge.png}
\end{center}
\caption{Edges in the graph XML file.
}\label{fig:edges}
\end{figure}

\newpage

\subsection{TF*IDF}
In order to perform mathematical operations and algorithms on documents and the text that they contain, we must first transform them into a representative mathematical object.  The standard representation of a document is a vector in the space of all available terms.  For example, the phrase:
\begin{equation}\label{eq:latent}
{\scriptsize
\begin{array}{r@{}c@{~}l}
The\: quick\: brown\: dog\: was\: very\: \\
quick,\: very\: brown,\: and\: very\: dog\: like.\\
\end{array}}
\end{equation}
Will be turned into a vector which looks something like this:
\begin{equation}\label{eq:latent}
{\scriptsize
\begin{array}{r@{}c@{~}l}
Phrase = [1\:2\:2\:2\:1\:3\:1\:1]
\end{array}}
\end{equation}
with each index of the above vector corresponding the a dimension which comes from the term list (in this case, 
the dimensions are {the, quick, brown, dog, was, very, like})

Tf*Idf is shorthand for ``term frequency times inverse document
frequency.'' This calculation models the intuition that jargon
usually contains technical words that appear a lot, but only in a
small number of paragraphs.  For example, in a document describing
a space craft, the terminology relating to the power supply may 
appear frequently in the sections relating to power, but nowhere
else in the document.

Calculating Tf*Idf is a relatively simple matter:
\bi
\item
Let there be $Words$ number of documents;
\item
Let some word $I$ appear $Word[I]$ number of times inside a set of $Documents$; 
\item
Let $Document[I]$ be the documents containing $I$.
\ei
Then:
\[
Tf*Id = Word[i]/Words*log(Documents/Document[i])
\]

The standard way to use this measure  is to cull all but the $k$ top Tf*Idf ranked
stopped, stemmed tokens. This study used $k=100$.

\newpage
\subsection{Dimensionality Reduction}
A major issue within  HAMLET is {\em dimensionality reduction}.
Standard AI learning methods work well for problems that are nearly all fully described
using dozens (or fewer) attributes~\cite{witten99}.
But a corpus of archival technical documents
must process thousands of unique words,
and any particular document may only mention a few of them~\cite{byrn99,salton83introduction}.
Therefore, before we can apply learning to technical document comprehension, we have to reduce the number
of dimensions (i.e. attributes) in the problem.

There are several standard methods for dimensionality reduction 
such as {\em tokenization, stop lists, stemming, Tf*IDF}, {\em InfoGain},
PCA, and FastMap.
All these methods are discussed below.
\subsubsection{Tokenization}
In HAMLET's parser,
words are reduced to simple tokens via (e.g.) removing all punctuation remarks, then sending all upper case to lower.


\subsubsection{Stop lists}
Another way to reduce dimensionality is to remove ``dull'' words via a 
{\em stop list}
of ``dull'' words. \fig{stop} shows a sample of the stop list used in HAMLET.
\fig{stop} shows code for a stop-list function.
\begin{figure}[!h]
\begin{alltt}\scriptsize
a           about    across   again      against
almost      alone    along    already    also
although    always   am       among      amongst
amongst     amount   an       and        another
any         anyhow   anyone   anything   anyway
anywhere    are      around   as         at
...         ...      ...      ...        ...  
\end{alltt}
\caption[Stop words]{24 of the 262 stop words used in this study.}\label{fig:stop}
\end{figure}

\subsubsection{Stemming}
Terms with a common stem will
usually have similar meanings. For example, all these words relate to the same concept.
\bi
\item
        CONNECT
    \item    CONNECTED
     \item   CONNECTING
     \item   CONNECTION
     \item   CONNECTIONS
\ei
Porter's stemming algorithm~\cite{porter80}
 is the standard stemming tool. It repeatedly replies a set of pruning rules to the end of words until
the surviving words are unchanged. The pruning rules ignore the semantics of a word and just perform syntactic pruning (e.g. \fig{stem1}).
\begin{figure}[!h] \scriptsize \begin{verbatim}
RULE                EXAMPLE
----------------    -----------------------------
ATIONAL ->  ATE     relational     ->  relate
TIONAL  ->  TION    conditional    ->  condition
                    rational       ->  ration
ENCY    ->  ENCE    valency        ->  valence
ANCY    ->  ANCE    hesitancy      ->  hesitance
IZER    ->  IZE     digitizer      ->  digitize
ABLY    ->  ABLE    conformably    ->  conformable
ALLY    ->  AL      radically      ->  radical
ENTLY   ->  ENT     differently    ->  different
ELY     ->  E       vilely         ->  vile
OUSLY   ->  OUS     analogously    ->  analogous
IZATION ->  IZE     vietnamization ->  vietnamize
ATION   ->  ATE     predication    ->  predicate
ATOR    ->  ATE     operator       ->  operate
ALISM   ->  AL      feudalism      ->  feudal
IVENESS ->  IVE     decisiveness   ->  decisive
FULNESS ->  FUL     hopefulness    ->  hopeful
OUSNESS ->  OUS     callousness    ->  callous
ALITY   ->  AL      formality      ->  formal
IVITY   ->  IVE     sensitivity    ->  sensitive
BILITY  ->  BLE     sensibility    ->  sensible
\end{verbatim} \caption{Some stemming rules.}\label{fig:stem1}
\end{figure}

Porter's stemming algorithm has been coded in any 
number of languages\footnote{\url{http://www.tartarus.org/martin/PorterStemmer}} such as the Perl {\em stemming.pl}
used in this study.

\subsubsection{InfoGain}

According to the $InfoGain$ measure,
the {\em best} words  are those that  
{\em most simplifies} the target
concept (in our case, the distribution of frequencies seen in the terms).
Concept ``simplicity'' is measured using information theory.
Suppose a data set has 80\% severity=5 issues and  20\% severity=1
issues.
Then that data set has a term distribution $C_0$ 
with terms $c(1)=cat$,  $c(2)=dog$ etc
with frequencies (say) $n(1)=0.8$, $n(2)=0.2$ etc
then
number of bits required to encode that 
distribution $C_0$ is $H(C_0)$ defined as follows:
\begin{equation}\label{eq:ent}{
\left.\begin{array}{rcl}
N&=&\sum_{c{\in}C}n(c)\\
p(c)& =& n(c)/N \\
H(C)&=& -{\sum}_{c{\in}C} p(c)log_2p(c)
\end{array}\right\}
}\end{equation}

After discretizing numeric 
data\footnote{E.g. given an attribute's
minimum and maximum values, replace a particular value $n$ with $(n - min)/((max - min)/10)$.
For more on discretization, see~\cite{dou95}.}
then if $A$ is a set of attributes, the number of bits required to encode
a class after observing an attribute is:
\[H(C|A) = -{\sum}_{a{\in}A} p(a) {\sum}_{c{\in}C} p(c|a)log_2(p(c|a)\]
The highest ranked
attribute $A_i$ is the one with the largest {\em information gain};
i.e the one that most
reduces the encoding required for the data {\em after}
using that attribute; i.e.
\begin{equation}\label{eq:infogain}
InfoGain(A_i) = H(C) - H(C|A_i)
\end{equation}
where $H(C)$ comes from \eq{ent}.
In this study, we will use InfoGain to find  the top $N=10$ most informative tokens. 

\subsubsection{TF*IDF Ranking}
A similar way of reducing the number of terms is by using the summation of the TF*IDF scores for each term.
This method gives each a term a ranking $tr_i$ each term using the following equation:
\begin{equation}
tr_i = \sum_{d{\in}D} TfIdf_{i,d}
\end{equation}
where D is the entire set of documents and $TfIdf_{i,d}$ is the Tf*Idf value for term $i$ and document $d$. After 
this has been computed for each term, a simple sort over all terms will give us the
most important terms, as defined by their Tf*Idf scores.  See \fig{tfidfTerms} for a list of real terms returned form a STEP dataset.

The benefit of using this method over InfoGain is not having to discretize the Tf*Idf values.  By
using the Tf*Idf values as they are, we can bypass an extra computational step.  Additionally, this approach
doesn't have to compute a new metric as InfoGain does, it simply sums the existing Tf*Idf scores which
is computationally faster than computing InfoGain.

\begin{figure}[!h]
\begin{alltt}\scriptsize
cartesian_point   type        oriented_edge   subtype         entity
label             sizeof      self            query           select
name              direction   edge_curve      where           wr1
text              real        set             not             description
for               rule        items           typeof          supertype
...               ...         ...             ...             ...  
\end{alltt}
\caption[Key Terms]{30 of the 100 key terms found in a STEP dataset using TF*IDF ranking}\label{fig:tfidfTerms}
\end{figure}


\subsubsection{PCA and FastMap}
Numerous data mining methods check if the available features 
can be combined in useful ways. These methods offer two useful services:
\be
\item
Latent important structures
within a data set can be discovered.
\item
A large set of features can be mapped to a smaller set, then it becomes
possible for users to manually browse complex data.
\ee
For example,
principal
components analysis (PCA)~\cite{Dil84} has been widely applied to
resolve problems with structural code measurements;
e.g.~\cite{Muns91}. PCA identifies the distinct orthogonal sources
of variation in a data sets, while mapping the raw features onto a set of
uncorrelated features that represent essentially the same
information contained in the original data. For example,
the data shown in two dimensions of \fig{pca} (left-hand-side)
could be approximated in a single latent feature
(right-hand-side).


\begin{figure}[!b]
\begin{center}
\includegraphics[angle=270,width=2in]{pca.pdf}
\end{center}
\caption[PCA: example]{The two features in the left plot can be transferred to the right plot via one latent feature.
}\label{fig:pca}
\end{figure}
Since  PCA combines many features into fewer latent features,
the structure of PCA-based models
may be very simple. For example, previously~\cite{me07c}, we have used PCA
and a decision tree learner to find the  following predictor for defective software modules:~\\

\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{minipage}{\linewidth}
{\footnotesize 
\begin{tabbing}
\setuptabs
\>if \>$domain_1 \le 0.180$\\
\>then NoDefects\\
\>else \>if $domain_1  >  0.180$\\
\> \>  then \>\> if $domain_1  \le 0.371$ then NoDefects\\
\> \>  else \>\> if $domain_1  >  0.371$ then Defects\\
\end{tabbing}}
\end{minipage}


Here, ``$domain_1$'' is one of the latent features found by PCA. This tree
seems very simple, yet is very hard to explain to business
clients users since ``$domain_1$'' is calculated using a very complex
weighted sum (in this sum,
$v(g), ev(g), iv(g)$ are 
McCabe or Halstead static code metrics~\cite{mccabe76,halstead77}
or variants on line counts): 
\begin{equation}\label{eq:latent}
{\scriptsize
\begin{array}{r@{}c@{~}l}
domain_1&=& 0.241*loc  +0.236*v(g) \\
      &&+0.222*ev(g)+0.236*iv(g)  +0.241*n  \\
      &&+0.238*v -0.086*l +0.199*d   \\
      && +0.216*i  +0.225*e  +0.236*b +0.221*t\\
     && +0.241*lOCode  +0.179*lOComment\\
     && +0.221*lOBlank +0.158*lOCodeAndComment \\
     && +0.163*uniq_Op +0.234*uniq_Opnd\\
     && +0.241*total_Op  +0.241*total_Opnd \\
     && +0.236*branchCount\\
\end{array}}
\end{equation}
Nevertheless, such  latent dimensions can be used to generate visualizations that show users
spatial distances between concepts in technical documents.
For example, \fig{3d} shows a 100-D space of prior designs
converted to a 3-D representation. In the conversion process,
the three top-most domains were computed and the 100-D space mapped to the 3-D space.
\begin{figure}
\begin{center}
\includegraphics[width=4in]{screens/3a.png}
\end{center}
\caption[Displaying a 100-D space of documents]{A 100-D space presented in 3-D.
The point in red shows the current design and the four points in green
show the nearest 4 technical documents (and the gray points show other documents
that have been ``trimmed'' away using the techniques discussed below).}\label{fig:3d}
\end{figure}

PCA is the traditional method of performing dimensionality reduction. It suffers from scale-up problems
(for large data sets with many terms, the calculation of the correlation matrix between all terms is
prohibitively computationally expensive). FastMap is a heuristic stochastic algorithm that performs
the same task as PCA, but do so in far less time and memory~\cite{faloutsos95fastmap}. Our own
experiments with the two methods showed that both yield similar structures.

\subsection{Clustering}\label{sect:clustering}
HAMLET adopts a geometric view of technical and other textual documents floating in an N-dimensional space (those dimensions maybe have also been
reduced by the above methods). The documents are clustered and new designs can be critiqued with respect to
their position relative to old designs.  The process of clustering allows similar designs (or textual documents) to be placed into groups
based upon some defined similarity measure in this N-dimensional space.  This is equivalent to asking, "What {\em types} of things are out there?"



\subsubsection{K-Means}
K-Means is a clustering algorithm that, when given a dataset of unidentified objects, it will 
group those items into $k$ groups based on some given similarity measure. 
The algorithm is described in \fig{kmeans}. For an example
of the algorithm in operation, see \fig{keg}.


\begin{figure}[!h]
\begin{tabbing}
\setuptabs
\>i=0\\
\>Partitioning the input points into k initial sets, either at random or using some heuristic data.\\
\>do\\
\> \>  Calculates the mean point, or centroid, of each set or cluster.\\
\> \>  Constructs a new partition, by associating each point with the closest centroid.\\
\> \>  Recalculate the centroids for the newly partitioned cluster\\
\> \>  i = i + 1\\
\>while($i \le maxIterations$ or no point changes set membership)\\
\end{tabbing}
\caption{K-Means algorithm}\label{fig:kmeans}
\end{figure}

\begin{figure}\small
Step1:
Here, we show some initial data points and the centroids generated based on random assignment
\begin{center}
\includegraphics{120px-K_Means_Example_Step_1.png}
\end{center}

Step2: Points are associated with the nearest centroid:
\begin{center}
\includegraphics{120px-K_Means_Example_Step_2.png}
\end{center}

Step3: Next, we
recompute centroid using new associations and update the stored centroid:
\begin{center}
\includegraphics{120px-K_Means_Example_Step_3.png}
\end{center}

Steps 2 \& 3 are repeated until one of the two convergences criteria are reached.
\begin{center}
\includegraphics{120px-K_Means_Example_Step_4.png}
\end{center}
\caption{Example of K-means}\label{fig:keg}
\end{figure}

While k-means may be sufficiently accurate, there are significant drawbacks.  Most notably is the speed (or lack thereof).  
Due to the k-means algorithm having to compute distances from every item to every cluster.  In situations where the cosine 
similarity distance measure is used, computing the distance between points can be an expensive operation (this is another place dimensionality reduction helps out).
In recent tests comparing clustering algorithm run-times, k-means was found to be up to 500 times slower than another algorithm, 
GENIC, which we discuss further down.

Another problem with k-means is determining what value of 
$k$ should be used.  Note the usability issues
with requiring a user to pre-specify $k$:
isn't this the kind of tedious detail
that  the computer should be telling us?  

There are many techniques for automatically discovering
an approximate value of $k$,
all of which include several rounds of initial guesses, trying
various values around the guess, then returning the $k$ value
that yields the best classification results.
The problem with 
these techniques is that K-Means is a slow
algorithm- requiring it to run many times is impractical for
large corpora.

\newpage
\subsubsection{Canopy Clustering}
A naive clustering algorithm runs in $O(N^2)$ where $N$ is the number of terms being clustered
and all terms are assessed with respect to all other terms. For large
archival collections, this is too slow. Various improvements over this naive strategy include ball trees,
KD-trees and cover trees~\cite{bey06}.  While all these methods are useful,
their ability to scale to very large examples is an open question.

An alternative to traditional clustering methods is {\em canopy clustering}~\cite{775116,347123}.
It is intended to speed up clustering operations on large data sets, where using another algorithm directly 
may be impractical because of the size of the data set.  In a standard
clustering algorithms, two items are compared to determine some measure of how similar or different they are. 
There are several distance measures used for different domains (euclidean, cosine, manhattan, etc.), the draw back 
to all of these is that they are all relatively computationally expensive.  
The secret to canopy clustering's greater performance
over conventional clustering techniques is it's use of two distance measures, one being approximately accurate but computationally cheap
and the other being more accurate, however more expensive.  To take advantage of the cheap distance metric, two passes are taken over
the dataset.  In the first pass, the cheap distance measure is used to determine {\em canopies}, which are groups of approximately close things.  In the second pass, the more expensive distance measure is used.  If any two items being compared do not share a canopy, then their distance is assumed to be infinite and no further comparison is done.  By doing this, canopy clustering prevents having to perform $n^2$ comparisons at each step through the clustering algorithm.

The algorithm proceeds as follows:
\bi
\item Cheaply partition the data into overlapping subsets, called 'canopies'
(see \fig{canopies});
\item Perform more expensive clustering, but only between these canopies.
\ei
\begin{figure}[!h]
\begin{center}
\includegraphics[width=3in]{canopies.png}
\end{center}
\caption[Canopies in 2-Dimensions]{The darker circle represents all points in a given canopy,
points in the smaller circles cannot be used as a new canopy center.}
\label{fig:canopies}
\end{figure}


In the case of text mining applications like HAMLET, the initial cheap clustering method
can be performed
using an inverted index; i.e.
a sparse matrix representation in which, for each word, 
we can directly access the list of documents containing that 
word. The 
great majority of the documents, which have no words in 
common with the partial design constructed by the engineering, need never be considered. Thus we 
can use an inverted index to efficiently calculate a distance 
metric that is based on (say) the number of words two documents 
have in common. 

\subsubsection{GENIC}
GENIC is a generalized incremental clustering algorithm developed by Gupta and Grossman~\cite{Gupta04}  that 
provides HAMLET with two useful services:
\bi
\item
Scalability:
 Since 
GENIC was designed with streaming data in mind, it only has a single pass through the data to work with.  Because of this,
it scales linearly, which is a requirement if HAMLET is to
scale to large corpora.
\item
 An likely estimate for $k$:
By using stochastic methods, GENIC can be given an initial $k$ equal to the number of items (each item is its own clusters) and prune away
unlikely clusters with each generation, giving a realistically estimated value for $k$ after the last generation.  
\ei

Here is how GENIC works:
\begin{enumerate}
\item \textbf{Select parameters}
\bi
\item Fix the number of centers $k$.
\item Fix the number of initial points $m$.
\item Fix the size of a generation $n$.
\ei

\item \textbf{Initialize}
\bi
\item Select $m$ points, $c_1, ..., c_m$ to be the initial candidate centers.
\item Assign a weight of $w_i$ = 1 to each of these candidate centers.
\ei

\item \textbf{Incremental Clustering} For each subsequent data point $p$ in the stream: do
\bi
\item $Count$ = $Count$ + 1
\item Find the nearest candidate center $c_i$ to the point $p$
\item Move the nearest candidate center using the formula \\
\begin{equation}
{c_i = \frac{(w_i * c_i + p}{w_i + 1} }
\end{equation}
\item Increment the corresponding weight \\
\begin{equation}
{w_i = w_i + 1}
\end{equation}
\item When $Count$ $mod$ $n$ = 0, goto Step 4
\ei

\item \textbf{Generational Update of Candidate Centers} \\
When $Count$ equals $n, 2n, 3n$, ..., for every \\
center $c_i$ in the list L of centers, do:
\bi
\item Calculate its probability of survival using the formula \\
\begin{equation}
{p_i = \frac{w_i}{\sum_{i=1}^n w_i}}
\end{equation}
\item Select a random number $\delta$ uniformly from [0,1]. If $p_i$ > $\delta$, retain the center $c_i$
in the list L of centers and use it in the next generation to replace it as a center in the list L
of centers.
\item Set the weight $w_i$ = 1 back to one.  Although some of the points in the stream will be implicitly assigned
to other centers now, we do not use this information to update any of the other existing weights.
\item Goto step 3 and continue processing the input stream
\ei

\item \textbf{Calculate Final Clusters} The list L contains the $m$ centers. These $m$ centers
can be grouped into the final $k$ centers based on their Euclidean distances.

\end{enumerate}

GENIC has been shown in the literature to have a clustering error
of less 1\% \cite{Gupta04}.  Further, when
tested on STEP schemas, it runs 100 to 1000s of  times
faster than k-means, as shown in \fig{ap203} and \fig{ap214}.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=4in]{ap203.pdf}
\end{center}
\caption[Clustering AP203]{Clustering results of STEP AP203 (configuration controlled design).}
\label{fig:ap203}
\end{figure}

\begin{figure}[!h]
\begin{center}
\includegraphics[width=4in]{ap214.pdf}
\end{center}
\caption[Clustering AP214]{Clustering results of STEP AP214 (core data for automotive mechanical design processes).}
\label{fig:ap214}
\end{figure}

\newpage

\subsection{Classification Within HAMLET}
A key task with HAMLET is recognizing which cluster is nearest the partial
design offered by HAMLET's user.  The challenge is doing this in both a quick and effective way.
However, as often is the case in problems of computer science, speed and accuracy are trade-offs.  

\subsubsection{Naive Bayes}

Bayesian classifiers, and more generally the Naive Bayes algorithm, 
are simple statistical learning schemes. 
They have seen a lot of use in the Machine Learning field because they are fast, 
use very little memory, and are trivial to implement. 

Naive Bayes is an application of Bayes' Theorem, relating the probability of event $H$ 
given evidence $E_i$, a prior probability for a class $P(H)$, and a posteriori probability $P(H|E)$:
\begin{equation}\label{eq:bayes}
P(H|E)= \prod_iP(E_i|H) \frac{P(H)}{P(E)}
\end{equation}

The classification with the highest probability is returned. The above assumes discrete attributes. 
To deal with numeric values, 
a features mean $\mu$ and standard deviation $\sigma$ are used in
a
Gaussian  probability
function~\cite{witten05}:
\[f(x) =
1/(\sqrt{2\pi}\sigma)e^{-\frac{(x-\mu)^2}{2\sigma^2}}\]

These classifiers are called "naive" because they assume that all attributes are equally important
and statistically independent. 
Although these assumptions are almost never correct, Domingos and Pazzini have shown that the 
independence assumption is a problem in a vanishingly small number of cases~\cite{domingos97optimality}.
On average, Naive Bayes classifiers perform as well, if not better than, more complex classification algorithms. 

\subsubsection{TWCNB}

Rennie et al.~\cite{Rennie03tacklingthe}
report a variant of a Naive Bayes classifier called Transformed Weight-normalized Complement
Naive Bayes (TWCNB) that uses normalized Tf*IDF counts with the following
properties:
\bi
\item It handles low frequency data sets;
\item It performs almost as well as more complex support vector machine implementations;  
\item Better yet, it is very simple to implement and
runs in linear time (which makes it suitable for scaling up to a very large corpus).
\ei

By using an optimization on the Naive Bayes classifier called the TWCNB we can achieve near-state-of-the-art accuracy with state-of-the-art speed.  This variant of Naive Bayes is highly optimized for text classification by doing the following:
\bi
\item Transforming inherently non-gaussian text distributions (power law) into a guassian to fit with Naive Bayes's normal assumption
\item Normalizes tfidf values to ensure the learner does not favor large or small documents
\item Reverses the standard Naive Bayes likelihood function so instead of looking for things that are like a given target, we look for things are {\em not} like the given target, by doing this, TWCNB is able to avoid clusters with relatively low counts
\ei


Because of the nature of the data we are dealing with, a key requirement for our 
classifier is that it handles low frequency counts: we anticipate that archival data sets will contain many terms, 
but only very few of them will appear in any particular document or the user's partial design.  This makes TWCNB an excellent candidate
for HAMLET.  We are currently experimenting with our own implementation of TWCNB.


\subsection{Trimming}
Trimming is a simple heuristic to prune 
remote points. It is a fast and simple method for focusing design reviews
on near-by concepts.

Trimming runs like this:
\bi
\item The user specifies some max distance measure $N$.
\item The $N$  nearest documents to the user's partially specified
design are accessed. These documents are sorted $1,2,3,4...N$ according to
their distance to the current design.
\item The delta between document $i$ and $i+1$ in the sort order
is computed and the document $i$ with the maximum delta (most difference between it
and $i+1$)
is declared ``the trim point''.
\item All documents $i+1,i+2,...N$  are trimmed away.
\ei
For example, \fig{trim} show the number of related documents before
and after trimming to a maximum depth of $N=25$. 
\begin{figure}
\begin{center}
\noindent
\includegraphics[width=5in]{screens/13.jpg}

~\\

\noindent
\includegraphics[width=5in]{screens/12.jpg}
\end{center}
\caption[Trimming]{ 
Trimming is a simple heuristic to prune 
remote points. It is a fast and simple method for focusing design reviews
on near-by concepts.
The top picture, left-hand-side, shows
in green the 25 documents closest to some partial design developed by the user. 
The contents of the third closest document, highlighted in blue, is shown
in the center screen.
The bottom picture shows the same set of nearby documents, with trimming enabled
(see the check box shown in red).
Note that now only four documents are displayed to the user.
}\label{fig:trim}
\end{figure}

\subsection{Query Results and What Else/What Not}
After classifying the user's design using the above mentioned bayesian method, we can drastically reduce
the search space of potentially similar designs.  This is possible
because after finding the most likely cluster (i.e. type of design), we only consider items within that cluster 
when finding designs similar to the user's query.  After all potentially similar designs have been identified, 
k-NN (k-Nearest Neighbor where k is part of the query) is used to determine the most relevant designs 
within the set of potentials.

After returning the ranked potentially similar items, the user is then given the option of exploring
the differences between the query (their design) and the results (designs indexed in HAMLET).  Comparisons can
be done between the query and either an individual item in the result list (ex. Product XYZ) or an item representative of all
items in the same cluster (type) (or at least the mathematical representation of one, as this item may not be tangible).
The delta generated by either of these comparisons comprises two lists:
\bi
\item What to add (the ``what else'' list).
\item What to remove (the ``what not'' list).
\ei
Given the treatment as designs as bags (documents) containing stuff (words), an algorithm to generate what else/what not
based in set theory was the easiest to conceive.  If each design is a set of words that appear somewhere in its documentation, 
then the formula's for what else and what not are as follows:
\bi
\item \begin{equation} WhatElse(D, T)=T-D \end{equation}
\item \begin{equation} WhatNot(D, T)=D-T \end{equation}
\ei
where T is a target design or document (bag of words) and D is the design or document currently being evaluated.


\begin{equation}\label{eq:bayes}
P(H|E)= \prod_iP(E_i|H) \frac{P(H)}{P(E)}
\end{equation}

\subsection{User Profiling with the Rochio Algorithm}
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 + \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).

We are currently exploring methods to augment Rochio with TWCNB. 

\newpage 
\section{Next Steps}
\begin{raggedleft}
{\em Plan to throw one away; you will anyhow.

 - "The Mythical Man-month" (1975)}

\end{raggedleft}


HAMLET is a tool suitable for in-house use in a research lab.
Much work is required before it can be released as a stand-alone tool for end-users, see \fig{todo}.

Note: The road-map in \fig{todo} has changed little from last time (Aug 30):
\be
\item 
As to point 1,
we have yet to hit the JAVA wall that makes us recode in ``C'' (the GENIC experience suggests that smart algorithms can take us further than changing 
the implementation language).
\item
We have some promising results
regarding point 2 (scalability: see
page \pageref{fig:ap203} and \pageref{fig:ap214}). 
\item
Point 3 (user studies) is the focus of the next few months.
\item
We'll address point 4 (linking between document types) if the need arises.
\item
As to point 5 (other applications of this toolkit), we exploring what value added these tools  add to Mucino's
``context discovery'' problem.
\ee
\begin{figure}[!b]\small
\begin{tabular}{|p{\linewidth}|}\hline
\be
\item
The current system was designed as a throw-away prototype to serve
as an experimental workbench for numerous implementation ideas.
For example, HAMLET is currently implemented in JAVA since this was  a language familiar
to the student programmers working on this project. The limitations of JAVA,
in terms of runtime, are becoming apparent. We wish to avoid a port to ``C'' 
and are looking into better internal JAVA-based data structures.
\item
As to other matters,
the scalability of HAMLET's queries has yet to be demonstrated.
Theoretically, the algorithms within HAMLET's current design run in  linear
time, or less. However, this scalability must be  empirically verified.
\item
Also, the user profile system that takes input from the users, then
dynamically tunes the results of each query, is still being designed.
Until that feature is designed, implemented, and tuned, then users of HAMLET
will suffer from too many false positives.
This user profile feature must be built.
\item
Further, HAMLET's ability to link between documents in 
heterogeneous collections has yet to be tested.
This test must be conducted.
\item
More generally, another useful question is ``what else is HAMLET good for?''. HAMLET
is a combination of feature extractors from technical documents,
numerous data \& text mining techniques, some AI tools, and some
information retrieval methods (including methods for learning from user feedback).  
While the current version answers the questions
``what else'' and ``what not'', it is an interesting question to ask if the toolkit could
be bent to another purpose.
\ee\\\hline
\end{tabular}
\caption{Our current todo list.}\label{fig:todo}
\end{figure}
\input{adam}
\input{andrew}
\input{greg}
%\newpage 
%\appendix 
%\section{Model for Early Life cycle
%Decisions} One reason that STEP/EXPRESS is not used more is that,
%from a cognitive perspective, it does not support the entire design
%cycle.  Rather, it only supports the last stages of design and not
%all the interim steps along the way.
%
%\subsection{Early Life cycle Models are Different}
%
%STEP/EXPRESS is a {\em heavy-weight} ontology designed to unambiguously represent
%categorical design decisions. There is much evidence that
%before human designers make 
%categorical decisions, they often prefer to ``play around a little''.
%Informal ultra-lightweight sketches
%are a common technique for illustrating
%and sharing intuitions. For example, in
%early life cycle requirements engineering,
%software engineers often pepper their discussions with
%numerous hastily-drawn
%sketches.
%Kremer argues convincingly that such visual forms
%have numerous advantages for acquiring knowledge
%\cite{kremer98}.
%Other researchers take a similar view: ``Pictures are superior to texts in a sense that they are abstract,
%     instantly comprehensible, and universal.''\cite{hirakawa94}.
%
%Normally, hastily-drawn sketches
%are viewed as precursors to some other, more precise
%modeling techniques which necessitate further analysis.  Such
%further
%formalization may not always be practical.
%The time and expertise required to build formal models
%does not accommodate the pace with which humans tend to revise
%their ideas.
%
%Also, such further
%formalization may not be advisable.
%Goel~\cite{goel92} studied the effects of
%diagram formalism on system
%design.  In an {\em ill-structured diagram} (such as a freehand sketch using
%pencil and paper), the denotation and type of each visual element is
%ambiguous.  In a {\em well-structured diagram} (such as those created using MacDraw
%or STEP/EXPRESS),
%each visual element clearly denotes one thing of one class only.  Goel
%found that ill-structured tools generated more design
%variants --- more drawings, more ideas, more re-use of old ideas --- than
%well-structured
%tools. 
%\subsection{Beyond STEP- Early Life cycle Models}
%The premise of the following early life cycle ultra-lightweight modeling
%frameworks is that (a)~this preference criteria is important;
%and that (b)~it is hence necessary to include
%preference constructs
%in the modeling language:
%\bi
%\item
%Mylopoulos' {\em soft-goal} graphs~\cite{mylo92,mylo99}.
%represent
%knowledge about non-functional requirements.
%Primitives in soft goal modeling include statements of partial
%influence such as {\em helps} and {\em hurts}.
%\item  A common framework in the design rationale
%community is a  ``questions-options-criteria'' (QOC)
%graph~\cite{shum94}. In  QOC
%graphs, questions suggest options and deciding on a certain option can
%raise other  questions.   Options   shown  in  a  box denote  selected
%options.  Options are assessed  by  criteria and criteria  are gradual
%knowledge;  i.e. they {\em  tend to support}  or {\em  tend to reject}
%options.  QOCs   can succinctly  summarize   lengthy debates; e.g. 480
%sentences  uttered in  a  debate between   two  analysts on  interface
%options  can be    displayed    in  a   QOC   graph  on    a    single
%page~\cite{maclean96}.
%Saaty's Analytic Hierarchy Process (AHP)~\cite{saaty80} is a variant of QOC.
%\item Another widely used framework is Quality
%Functional Deployment diagrams (QFD)~\cite{akao90}.
%Yet another framework is the DDP system developed by Cornford and Feather~\cite{feather03}
%Where as AHP and QOC  propagate influences over hierarchies,  QDF (and DDP) propagate  influences over matrices.
%\ei
%
%\subsection{Why Record Early Life cycle Models?}
%At first glance,
%the imprecision of the above modeling frameworks appears to make them inferior
%to precise and unambiguous STEP models. However, it is this very imprecision
%that makes then valuable. 
%
%Firstly, one reason for preferring the above ultra-lightweight ontologies over
%STEP/EXPRESS is that, at least for group design activities:
%\bi
%\item During fast-paced design discussions,
%only brief statements can be collected. Otherwise, the dialogue
%within a meeting would be hampered by the time required
%to record, in tedious detail, the exchange of ideas.
%\item If the ontology gets more elaborate, then experts
%may be unable to understand technical arguments from outside their
%own field of expertise. 
%\ei
%
%Secondly, experience at 
%NASA\footnote{This section 
%is based on numerous
%interviews with NASA designers working on 
%the reuse of old Apollo designs for NASA's next-generation 
%Mars rocket.
%} suggests that a vital missing component of any one design are all the
%other designs rejected before arriving at the final system.
%Researchers in the design rationale community~\cite{moran96} advise
%that these rejected dead-end designs are useful to determine the preference
%criteria used in selecting the appropriate design. 
%
%\subsection{Summary}
%Modeling languages that capture design option\underline{s} are different than modeling languages
%that record the final detailed design. One reason that STEP/EXPRESS is not used more is, we conjecture,
%that it is a ``final design capture'' tool and not an ``initial design options exploration'' tool.
%While ``final design capture'' tools are useful for transferring current designs between different CAD/CAM
%tools, such tools may not be preferred for reviewing and understanding designs decades after they are 
%created.
%
%Nevertheless, the above early life cycle modeling tools may be not indicated for the task of comprehending
%archival technical documents.
%The augmentation of large archival storage with detailed design alternative and preference knowledge
%(i.e. like that captured in DDP, AHP,  QFD, or soft goals) requires a detailed
%analysis of existing artifacts\footnote{e.g. see the {\em Software Archeology} example
%offered by Grady Booch~\cite{booch04}.}.
%Hence it may not be indicated for archival storage where the corpus size
%is very large and there is  a lack of access to the relevant domain experts.
%
%Recent advances in program comprehension and text mining indicate that it may be
%possible to infer
%such preference knowledge from multiple instances of finished designs.
%Hence, this work.
\newpage
\bibliographystyle{abbrv}
\addcontentsline{toc}{section}{References}
\bibliography{refs,refstimm}

\end{document}
