\documentclass[letterpaper, 11pt]{article}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{times}
\usepackage{float}
%\usepackage[in]{fullpage}
\usepackage{amsmath,amsfonts,amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{graphicx,booktabs}
%\usepackage{algorithm2e}
\usepackage{algorithm}
%\usepackage{algorithmic}
\usepackage{algpseudocode}
\usepackage[colorinlistoftodos]{todonotes}
\title{Phrase-Projection for Cross-Lingual JAMR training}
\author{Adithya Renduchintala}
\date{\today}
\begin{document}
\maketitle
\section{Introduction}
We are given spans of the target text which align to concepts in the AMR graph.These alignment do not cover every token in the target sentence. Typically function words are not aligned to any graph fragment. Next, we obtain word alignments between the target sentence and source sentence. Since we have word alignments between target and source, and phrase alignments between target and AMR graph, we must convert the word alignments into phrase alignments. The phrases on the source side will then be projected to the AMR concepts via the target sentence. When obtaining the phrases on the source side, two constrains that we are enforcing are:
\begin{itemize}
\item Every phrase/span in the target side that is associated with a concept/graph fragment there should be a phrase/span in the source side
\item The spans on the source side should be non-overlapping.
\end{itemize}
Below are diagrams showing phrases suitable for projection, and one phrase alignment that is not suitable.
\begin{figure}[ht]
\begin{minipage}[b]{0.32\linewidth}
\centering
\includegraphics[width=0.5\textwidth]{phrase-align1.jpg}
\caption{Acceptable Phrase Projection}
\label{fig:minipage1}
\end{minipage}
\quad
\begin{minipage}[b]{0.32\linewidth}
\centering
\includegraphics[width=0.5\textwidth]{phrase-align2.png}
\caption{Acceptable Phrase Projection}
\label{fig:minipage2}
\end{minipage}
\quad
\begin{minipage}[b]{0.32\linewidth}
\centering
\includegraphics[width=0.5\textwidth]{phrase-align3.png}
\caption{Violating Phrase Projection}
\label{fig:minipage2}
\end{minipage}
\end{figure}
\section{Model}
In our scenario the source sentence is Chinese and the target is English.
\begin{align*}
F &= [f_1, f_2, f_3, ... f_m]\\
E &= [e_1, e_2, e_3, .. e_n]
\end{align*}
We run JAMRs rule based alignment tool to obtain alignments between the English sentence and the AMR graph. These are phrase to subgraph alignments. These phrases are taken as a given segmentation of the target.
\begin{align*}
P_E = [p_{T1}, p_{T2},... p_{Tk}]
\end{align*}
Where $p_i$ is the $i^{th}$ phrase in the sentence. We want to find a segmentation and an alignment between phrases that maximizes the phrase alignments between the two sentences.
\begin{align*}
P_F &= [p_{F1}, p_{F2}, ... p_{Fk}]\\
A &= [a_1, a_2, a_3, ... a_n]
\end{align*}
Given a phrase in the target $p_{Ti}$ we know that each token in it has alignments $\{a_i, a_{i+1}, ... a_{i+j}\}$, this phrase has $j+1$ tokens. We define the corresponding phrase $p_{Fi}$ as the span created between $\min\{a_i, a_{i+1}, ... a_{i+j}\}$ and $\max\{a_i, a_{i+1}, ... a_{i+j}\}$.
\begin{align}\label{eq:solve}
p_{Fi} &=\min{a_i, a_{i+1}, ... a_{i+j}},\max{a_i, a_{i+1}, ... a_{i+j}}
\end{align}
In this manner we can define all the spans in $F$ as long as the two constraints defined are not violated. However, if the constraints are violated then we have to change the alignments forming the spans.
\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{phrase-align3-label.png}
\caption{\label{fig:violated}An example of phrase overlap }
\end{figure}
\begin{figure}[ht]
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[width=0.5\textwidth]{phrase-align3-solved.png}
\caption{removed alignment $a$}
\label{fig:removea}
\end{minipage}
\quad
\begin{minipage}[b]{0.45\linewidth}
\centering
\includegraphics[width=0.5\textwidth]{phrase-align3-solved2.png}
\caption{removed alignment $b$}
\label{fig:removeb}
\end{minipage}
\end{figure}
The example of a violation shown in \ref{fig:violated} can be corrected by dropping some subset of alignment edges.\\ For example we can arrive at two solutions by dropping either the alignment edges $a$ or $b$ (\ref{fig:removea}, \ref{fig:removeb}). The alignment edge $c$ can not be dropped because it mean that an entire phrase in the target can not be projected over to the source. The best alignment and segmentation can be obtained by using:
\begin{align}
&= \underset{\mathcal{A,K}}{\operatorname{argmax}} \prod_i^{\mid K \mid} P(P_{Fa_i} \mid P_{Ti})
\end{align}
Where $\mathcal{A} \subset A$ that ensures that the constraints are met.
\section{Algorithm}
One exponential time algorithm to solve the task is presented below. The algorithm is essential a Breath-First Tree search algorithm. Each node in the tree represents a set of alignments. These sets are all subset of the full set of word alignments $A$. The search process starts with checking if source phrases can be created using the using expression \ref{eq:solve}.\\
At each node, one alignment is removed and the set formed by removing one alignment forms a child node. During the search, each node (set of alignments) is checked for complying with the constraints. If the node is conforming, then the list of alignments is a solution. The CheckAlignment method checks for overlapping phrases on the source side. This will make sure that only alignments which comply with the non-overlap constraint will be accepted in the final list of solutions.\\
The RemoveAlignment method removes an alignment link from the set of alignments which is used to create a child node. In this method, the if statement ensures that if an alignment is the only alignment for a target phrase then it will not be removed. This make sure phrases in the target will have a projection in the source.\\
\subsection{Complexity}
This is an exponential algorithm, each step in the search opens a node in the graph. There is some amount of recombination but the middle layer of the tree will be very wide. The recombination happens because a node which has had the same alignments removed (in different orders) will be the same, i.e. different alignment removal orders can result in the same node. The fan out is exponential in the number of alignments.\\
In practice, however, most of the alignments are the only alignment from a target phrase. This is in turn because most of the target phrases are single words. This means most of the alignments can not be removed, this drastically reduces the search space. Only the small amount of multi-word phrases in the the target will have to be searched, if the alignments do not match the constraints.
\begin{algorithm}
\caption {Phrase Align}\label {phrasealign1}
\begin{algorithmic}
\Procedure{CheckAlignment}{alignments $A$}
\For {phrase $p_T$ in $P_T$}
\State $p_F$ = getSourcePhrase($p_T$)
\For {phrase $p_t$ in getAssociatedPhrase($p_F$)}
\If {$p_t$ != $p_T$}
\State return False
\EndIf
\EndFor
\EndFor
\State return True
\EndProcedure
\Procedure{RemoveAlignment}{Alignments $A$, alignment $a$}
\If {$a$ from $p_T$ of span 1}
\State return $A$ \Comment {Can not remove a single word phrase's alignment}
\Else
\State return $\hat{A}$
\EndIf
\EndProcedure
\Procedure{SolveAlignment}{alignment $A$}
\State $final$ = $[]$ \Comment {Final list of alignments}
\State $Q$ = $[]$ \Comment {Initialized Que}
\State $Q$.push($A$)
\While {$Q$ not empty}
\State $A$ =$Q$.pop()
\If {CheckAlignment($A$)}
\State $final$.add($A$)
\ElsIf
\For {alignment $a$ in $A$}
\State $\hat{A}$ = RemoveAlignment($A$,$a$)
\If {$A$ != $\hat{A}$}
\State pass \Comment {Branch ends, could not remove any alignment }
\ElsIf
\State $Q$.push($\hat{A}$)
\EndIf
\EndFor
\EndIf
\EndWhile
\State return $final$
\EndProcedure
\end{algorithmic}
\end{algorithm}
\end{document}
