\documentclass[portrait,letterpaper,10pt]{scrartcl}

\usepackage[top=1in,left=.25in,right=.25in,nohead,nofoot]{geometry}

\usepackage[utf8]{inputenc}
\usepackage[american]{babel}
\usepackage[T1]{fontenc}
\usepackage[pdftex]{graphicx}
\usepackage{amsmath}
\usepackage{enumerate} % Fancy enumeration styles

\usepackage{alg} % Typesetting algorithms

\title{Corpus Navigator Architecture}
\author{Jonathan Clark}
\date{Thursday, November 29, 2007}

% Custom commands
\newcommand{\dhat}{\hat{\delta}} % delta hat
\newcommand{\union}{\cup}
\newcommand{\intersection}{\cap}
\DeclareMathOperator*{\argmax}{argmax}
\DeclareMathOperator*{\argmin}{argmin}

% Custom algorithm commands
\newcommand{\algfor}[1]{\textbf{foreach} #1\\\algbegin} 
\newcommand{\assign}{\leftarrow}


\begin{document}
\maketitle

\section{Building the Search Space}

\begin{algorithm}[h]
\caption{Building the search space.}
\alginout{TODO... It will be a long, rather boring list.}
          {The best feature structure that should be elicited next.}
\algname{SearchLanguage}{$A,B$}
\begin{algtab}
$q \assign$  empty priority queue \\
let $h$ represent a hypothesis \\

\algfor{$s \in elicitedSentences$}
	$h \assign s $ \\
	$realization(h) \assign uneliciatedRealizations(h) \union NOT elicitedRealizations(h)$ \\
	$q \assign q \union h$ \\
	\algfor{$x \in ( clauses(s) \union participants(s) \union modifiers(s) \union conjunctions(s))$}
		$h \assign s - x$ // remove clause/participant \\
		$q \assign q \union ( h, score( h ) )$ \\
		\algfor{feature $f \in featureSetFor(x)$}
			\algfor{featureValue $v \in f \neq f(s)$}
				$h \assign s$ \\
				$f(h) \assign v$ \\
				$realization(h) \assign uneliciatedRealizations(h)$ \\
				$q \assign q \union (h, score(h))$ \\
			\algend
		\algend
	\algend
	
	// NOTE: the main clause is not compatible with itself \\
	\algfor{$x \in ( (allCompatibleClauses \union allCompatibleParticipants \union allCompatibleModifiers \union allCompatibleConjunctions) \notin (clauses(s) \union participants(s)))$}
		\algfor{$y \in seedSubFeatureStructures(x)$}
			$hypothesis h \assign s + y$ \\
			$realization(h) \assign uneliciatedRealizations(h)$ \\
			$q \assign q \union (h, score(h)) $ \\
		\algend
	\algend
\algend

\algreturn{$top(q)$}

\end{algtab}
\end{algorithm}

\begin{itemize}
\item NOTE: We can either build all hypotheses first and then rank later so that we can show a progress indicator or 
\item NOTE: We may have duplicate hypotheses in the search space, but this shouldn't matter; Alternatively, we can build the search space in terms of all combinations instead of in terms of minimal pairs.
\item NOTE: We will build hypotheses for sentences that have already been elicited, but we will specify that they must have a different realization.
\item NOTE: Since modifiers can occur infinitely many times per clause/participant and conjunctions can have infinitely many items, we might want to limit these to 2 and 3 each, respectively.
\end{itemize}

Upper bound on number of hypotheses for each state is: \\
O(numElicitedSentences $\cdot$ (maxNumCompatibleClauses! $\cdot$ numClauses $\cdot$ ( maxNumClauseSeeds + numClauseFeatures $\cdot$ maxClauseFeatureValues $\cdot$ maxNumCompatibleParticipants! $\cdot$ numParticipants $\cdot$ (maxNumParticipantSeeds + numNounFeatures $\cdot$ maxNumNounFeatureValues) ) ) ) \\

--OR-- \\

The total number of combinations possible, whichever is less. Therefore, our maximum number of hypotheses should be under 100 million, if previous estimates are correct.


%2000 * 6 * 5 * (5 + 20 * 10 * 6 * 7 * (5 + 30 * 10) ) = 153,720,300,000 = 153 billion hypotheses


\subsection{Using Seeds to Make the Search Space Tractable}

Consider the case of a participant with 3 features, each having 3 possible values. If we were to allow all combinations to be hypotheses, we would have 27 new hypotheses just in this contrived example. However, if the user can recommend a reasonable starting place (seed), then we reduce this to a single (or perhaps 2 or 3) hypotheses, preventing the combinatoric explosion.







\section{Scoring the Hypotheses}

Input here is the set of unscored hypotheses from above h. We then score them all and take the argmax. This is a theoretical formulation, since we might actually prune some of the hypotheses with small scores if the search space grows too large.

The Score function is defined as the following mixture model:
If we had a gold standard, we could theoretically run Expectation Maximization on the mixing weights of our scoring metrics.

(Should we make this log-linear?)


Score(k=currentKnowledge, f=featureStructure, m=metaContext, l=lexicalElements) = \\
     $\lambda_{0} \cdot booleanExploreIf(k,v,m)$ \\
     $\cdot ($ \\
     	$\lambda_{1} \cdot \sum_{v \in f} $ \\
		$\cdot ( $ \\
	
     			// General FEG's \\
			$\lambda_{a} \cdot \sum_{i=2}^{numInteractions + 1} weightForInterationLevel(i) \cdot \sum_{x \in affectedFEGs(k,v,m,i)} \\ \\
			\sum_{y \in assertedArcs(k,v,m,i,x)} likelihoodOfInteraction(y) \cdot redundancyFunction [ y ] (numAlreadyExplored(y)) / (i \cdot numAlreadyExplored(y))$ \\
		
			// Specific FEG's \\
			+ $\lambda_{b} \cdot \sum_{i=2}^{numInteractions + 1} weightForInteractionLevel(i) \cdot \sum_{w \in metaElements} \sum_{x \in affectedFEGs(k,v,m,i)} \\ \\
			\sum_{y \in assertedArcs(k,v,m,i,x)} likelihoodOfInteraction(y)$ \\
		
			// General Single Features \\
			+ $\lambda_{3} \cdot likelihoodOfExpression(v)$ \\
		
			// Specific Single Features \\
			+ $\lambda_{4} \cdot likelihoodOfExpression(v) \cdot metaContextWeight(v,m)$ \\
		
			+ $\lambda_{5} \cdot numFeatureValuesRemainingToBeExpanded(feature(v))$ \\
			+ $\lambda_{6} \cdot percentFeatureValuesRemainingToBeExpanded(feature(v))$ \\
		) \\
		+ $\lambda_{7} \cdot vocabularyCoverage(f, l)$ \\
		+ $\lambda_{8} \cdot morphologyGoodness(k,f,m,l)$ \\
		+ $\lambda_{9} \cdot goodnessOfStayingInThisSeedOrSwitching$ \\
		+ $\lambda_{10} \cdot haveRealizedSentence(f)$ \\
     ) \\
     
          Can we formulate this as a Bayesian model? A n-gram model similar to MT?
          Add value for task and frequency of occurrence in target domain/open domain.
          
\subsection{Counting Crossings, Reorderings, and Discontinuities}

targetDiscontinuity(X) = 0 if $(S_{i} \rightarrow T_{j}), \forall T_{j}, x \leq j \leq y, x = \argmin_{b} (S_{a} \rightarrow T_{b}), y = \argmax_{b} (S_{a} \rightarrow T_{b}), \{S_{i}, S_{a}\} \subseteq $ children(X) \\
else 1 \\
     
     
     
     
     


\section{Doing Inference on the Collected Evidence}

*** This section is still under construction. ***

We can label the expression of a feature value $v$ as:
\begin{enumerate}
\item \emph{fully expressed} if its minimal pairs are all have different target language translations
\item If any other value is expressed within this feature $f \ni v$, then we say $v$ is \emph{jointly expressed} with the other values that can be clustered with it.
\item \emph{unexpressed} if all feature values are identical.
\end{enumerate}

$t_{i}$ are translated sentences \\
$f_{i}$ are feature structures \\
$x,y$ are feature values \\
$x \vdash f$ indicates the substitution of another feature value $y$ for $x$ into a feature structure $f$ where $y$ is in the same feature as $x$. For example, we might substitute \emph{singular} for \emph{plural}. \\

$P_{x}( \Delta(t_{1},t_{2})\ |\ x \in f_{1} \intersection f_{2} \equiv x \vdash f_{1})$ \\
$= $ \\

$P_{x,y}( \Delta(t_{1}, t_{2})\ | \ x,y \in f_{1} \intersection f_{2} \equiv y \vdash f_{1})$ \\
\hspace{50pt} $= P_{x,y}( \Delta(t_{1}, t_{2})\ | \ y \in f1, f2 \intersection x \in f_{1} \intersection f_{1} \equiv x \vdash f_{2}) $ \\
$=$ \\

\begin{algorithm}[h]
\caption{Inferring expression of single features and the relationships between them.}
\alginout{TBA... It will be a longish list.}
          {A list of feature expressions and relationships along with collected statistics.}
\algname{InterRelations}{$A,B$}
\begin{algtab}

let $\theta$ be a user-defined threshold value
$e \assign $ empty set of expression values
	
\algfor{$a \in $ features}
	\algfor{$x \in $ values($a$)}
		$p \assign P_{x}( \Delta(t_{1},t_{2})\ |\ x \in f_{1} \intersection f_{2} \equiv x \vdash f_{1})$
		\algif{$p \geq \theta$}
			// TODO: Write clustering code \\
	\algend
\algend

$t \assign$  empty key-value table $(\{x,y\}, r)$ where $\{x,y\}$ is an unordered set of feature values and $r$ is a set of relationships \\

\algfor{$a \in $ features}
	\algfor{$b \in $ features}
		\algfor{$x \in $ values($a$)}
			\algfor{$y \in $ values($b$)}
				// add dependency for whichever direction creates fewer rules \\
			\algend
		\algend
	\algend
\algend

\end{algtab}
\end{algorithm}

NOTE: We are NOT finding dependence in the statistical sense, but instead just finding implications. Also, we report statistics rather than estimate probabilities.







\pagebreak
     
\section{Jargon}

\begin{enumerate}

\item Feature Value Dominance - 

\item Realization - The process of writing source language sentences given a feature structure.

\item Participants - Roles defined in a feature structure. e.g. Actor, Undergoer, Causer, Causee

\item Clause Types - e.g. main-clause, relative-clause, etc.

\item Inference - The process of determining which features are actually expressed in the target language.

\item Feature Interaction Level - The number of features that we will simultaneously examine for interactions between each other. I plan to start with 2.

\item Feature Expression Graph (FEG) - A graph containing one node for each feature combination being analyzed (during inference). When analyzing zero feature interactions, An arc is drawn between nodes to represent one or more pieces of elicited evidence for the existence of a difference between the two feature value combinations.

\item General FEG - A FEG that does not include participants or clauses as part of its combinations.

\item Specific FEG - A FEG that does include participants and/or clauses as part of its combinations.

\item Elicitation Search - For us, the process of determining which sentences to feed to the inference engine.

\item Hypothesis - A candidate feature structure for elicitation whose goodness will be scored and ranked. A hypothesis might or might not be associated with a realized source language string.

\item Seed Sentences - An ``opening book'' of feature structures with specified realizations that will always be explored during the search process. These seeds serve as baseline from which minimal pairs will be created.

\item Partial Feature Structure - An extracted portion (much like a constituent) of a feature structure. For example, we might extract the partial feature structure associated with just a relative clause just an actor.

\item Partial Seeds - Partial feature structures used for pruning the combinatoric explosion associated with adding a new clause/participant to a sentence.

\item Minimal Pair - During inference, During search, a minimal pair is made up of one sentence that has has already been elicited and a hypothesis.

\item Scoring Metric - A function used to determine the goodness of one particular aspect of a hypothesis.

\item Evaluation Metric - A function used to determine the performance of the system as a whole.

\item Mixing Weights / Lambdas - Weights used to combine the scoring metrics into a single score value.

\item Rule Implication - The ``then'' part of a rule in the production system.

\item Implicational Universal - A Greenbergian Typological Universal, most likely computed on the WALS feature set rather than on our MILES features.

\item Feature Relationships - Language facts that is the output of the inference stage of our system.

\end{enumerate}

\end{document}