Sentence Alignment - Revision history

Tamchyna at 14:23, 10 March 2015

2015-03-10T14:23:28Z

← Older revision		Revision as of 14:23, 10 March 2015
Line 37:		Line 37:

	<math>		<math>
	\delta = (l_2 - l_1 c) \sqrt{l_1 s^2}		\delta = (l_2 - l_1 c) / \sqrt{l_1 s^2}
	</math>		</math>

Tamchyna at 14:21, 10 March 2015

2015-03-10T14:21:08Z

← Older revision		Revision as of 14:21, 10 March 2015
Line 78:		Line 78:
	</math>		</math>

	Again, similarly to string edit distance, the minimum total distance can be read off the table cell <math>(I,J)<math> and backtracking can be used to find the actual alignment.		Again, similarly to string edit distance, the minimum total distance can be read off the table cell <math>(I,J)</math> and backtracking can be used to find the actual alignment.

	== Other Algorithms & Tools ==		== Other Algorithms & Tools ==

Tamchyna: /* Algorithm Formulation */

2015-03-10T14:20:54Z

Algorithm Formulation

← Older revision		Revision as of 14:20, 10 March 2015
Line 77:		Line 77:
	D(i - 2, j - 2) + d(x_i, y_j, x_{i-1}, y_{j-1}) \end{cases}		D(i - 2, j - 2) + d(x_i, y_j, x_{i-1}, y_{j-1}) \end{cases}
	</math>		</math>

			Again, similarly to string edit distance, the minimum total distance can be read off the table cell <math>(I,J)<math> and backtracking can be used to find the actual alignment.

	== Other Algorithms & Tools ==		== Other Algorithms & Tools ==

Tamchyna: /* Distance Function */

2015-03-10T14:19:24Z

Distance Function

@@ Line 44: / Line 44: @@
 <math>P(\text{match} | \delta) \propto P(\delta | \text{match}) \cdot P(\text{match})</math>
-We use <math>-log P(\text{match} | \delta)</math> so that we can lower cost is better and that we can sum the values and still have a probability distribution (instead of multiplying them).
+We use <math>-\log P(\text{match} | \delta)</math> so that lower cost is better and that we can sum the values in the algorithm and still have a probability distribution (instead of multiplying them).
 Let us define some notation (identical to the original paper):

Tamchyna at 14:05, 10 March 2015

2015-03-10T14:05:17Z

← Older revision		Revision as of 14:05, 10 March 2015
Line 34:		Line 34:
	== Distance Function ==		== Distance Function ==

	A distance measure (or a cost function) is required so that we can look for a minimal solution. Gale & Church observe that length differences (measured in characters) between matching sentences tend to be normally distributed. Let <math>c</math> be the average ratio between sentence lengths (for 0 mean, <math>c</math> would be 1), <math>s^2</math> be the observed variance, and <math>l_1, l_2</math> lengths of the source and target sentence, respectively. Then we define:		A distance measure (or a cost function) is required so that we can look for a minimal solution. Gale & Church observe that length differences (measured in characters) between matching sentences tend to be normally distributed. Let <math>c</math> be the average ratio between sentence lengths (for zero mean, <math>c</math> would be 1), <math>s^2</math> be the observed variance, and <math>l_1, l_2</math> lengths of the source and target sentence, respectively. Then we define:

	<math>		<math>
Line 40:		Line 40:
	</math>		</math>

			<math>\delta</math> is a zero-mean, unit-variance, normally distributed random variable. We can use it to define our ''distance measure'' as the inverse of the conditional probability of a match given a difference <math>\delta</math>. Following the Bayes' rule and dropping the (constant) denominator, we obtain:
	~~Gale & Church formulate this~~ as the conditional probability of a match given a difference <math>\delta</math>. Following the Bayes' rule and dropping the (constant) denominator, we obtain:

	<math>P(\text{match} \| \delta) \propto P(\delta \| \text{match}) \cdot P(\text{match})</math>		<math>P(\text{match} \| \delta) \propto P(\delta \| \text{match}) \cdot P(\text{match})</math>

	~~Gale & Church~~ use ~~a probabilistic view~~ so that the ~~costs can be combined in~~ a ~~principled way~~ (~~by summing log-probabilities, i.e. by~~ multiplying ~~probabilities~~). ~~We therefore look for:~~		We use <math>-log P(\text{match} \| \delta)</math> so that we can lower cost is better and that we can sum the values and still have a probability distribution (instead of multiplying them).



	~~Where~~

	~~First, let~~ us define some notation (identical to the original paper):		Let us define some notation (identical to the original paper):

	: <math>d(x_1, y_1, 0, 0)</math> -- the cost of ''substituting'' <math>x_1</math> with <math>y_1</math>		: <math>d(x_1, y_1, 0, 0)</math> -- the cost of ''substituting'' <math>x_1</math> with <math>y_1</math>

Tamchyna at 13:57, 10 March 2015

2015-03-10T13:57:35Z

← Older revision		Revision as of 13:57, 10 March 2015
Line 34:		Line 34:
	== Distance Function ==		== Distance Function ==

	A distance measure (or a cost function) is required so that we can look for a minimal solution. Gale & Church formulate this as the conditional probability of a match given a difference <math>\delta</math>. Following the Bayes' rule and dropping the (constant) denominator, we obtain:		A distance measure (or a cost function) is required so that we can look for a minimal solution. Gale & Church observe that length differences (measured in characters) between matching sentences tend to be normally distributed. Let <math>c</math> be the average ratio between sentence lengths (for 0 mean, <math>c</math> would be 1), <math>s^2</math> be the observed variance, and <math>l_1, l_2</math> lengths of the source and target sentence, respectively. Then we define:

			<math>
			\delta = (l_2 - l_1 c) \sqrt{l_1 s^2}
			</math>


			Gale & Church formulate this as the conditional probability of a match given a difference <math>\delta</math>. Following the Bayes' rule and dropping the (constant) denominator, we obtain:

	<math>P(\text{match} \| \delta) \propto P(\delta \| \text{match}) \cdot P(\text{match})</math>		<math>P(\text{match} \| \delta) \propto P(\delta \| \text{match}) \cdot P(\text{match})</math>

Tamchyna at 13:50, 10 March 2015

2015-03-10T13:50:01Z

← Older revision		Revision as of 13:50, 10 March 2015
Line 34:		Line 34:
	== Distance Function ==		== Distance Function ==

	A distance measure (or a cost function) is required so that we can look for a minimal solution. Gale & Church formulate this as the conditional probability of a match given a difference <math>\delta</math>:		A distance measure (or a cost function) is required so that we can look for a minimal solution. Gale & Church formulate this as the conditional probability of a match given a difference <math>\delta</math>. Following the Bayes' rule and dropping the (constant) denominator, we obtain:

	<math>P(\text{match} \| \delta) \propto P(\delta \| \text{match}) \cdot P(\text{match})</math>		<math>P(\text{match} \| \delta) \propto P(\delta \| \text{match}) \cdot P(\text{match})</math>

Tamchyna: /* Distance Function */

2015-03-10T13:49:09Z

Distance Function

← Older revision		Revision as of 13:49, 10 March 2015
Line 34:		Line 34:
	== Distance Function ==		== Distance Function ==

	A distance measure (or a cost function) is required so that we can look for a minimal solution. Gale & Church use a probabilistic view so that the costs can be combined in a principled way (by summing log-probabilities, i.e. by multiplying probabilities). We therefore look for:		A distance measure (or a cost function) is required so that we can look for a minimal solution. Gale & Church formulate this as the conditional probability of a match given a difference <math>\delta</math>:

			<math>P(\text{match} \| \delta) \propto P(\delta \| \text{match}) \cdot P(\text{match})</math>

			Gale & Church use a probabilistic view so that the costs can be combined in a principled way (by summing log-probabilities, i.e. by multiplying probabilities). We therefore look for:


	~~<math>P(match \| \delta)</math>~~

	Where		Where

Tamchyna at 13:23, 10 March 2015

2015-03-10T13:23:36Z

← Older revision		Revision as of 13:23, 10 March 2015
Line 16:		Line 16:
	Gale & Church algorithm<ref name="galechurch">William Gale, Kenneth Church. ''[http://www.aclweb.org/anthology/J93-1004.pdf A Program for Aligning Sentences in Bilingual Corpora]''</ref> is an algorithm for sentence alignment. It assumes that documents are already aligned on the level of paragraphs. For each paragraph, it finds which sentences correspond to each other.		Gale & Church algorithm<ref name="galechurch">William Gale, Kenneth Church. ''[http://www.aclweb.org/anthology/J93-1004.pdf A Program for Aligning Sentences in Bilingual Corpora]''</ref> is an algorithm for sentence alignment. It assumes that documents are already aligned on the level of paragraphs. For each paragraph, it finds which sentences correspond to each other.

	It is formulated as a [http://en.wikipedia.org/wiki/Dynamic_programming dynamic programming] algorithm, quite analogous to [~~Levenshtein distance~~ http://en.wikipedia.org/wiki/Levenshtein_distance].		It is formulated as a [http://en.wikipedia.org/wiki/Dynamic_programming dynamic programming] algorithm, quite analogous to [http://en.wikipedia.org/wiki/Levenshtein_distance Levenshtein distance].

	== Possible Operations ==		== Possible Operations ==

Tamchyna at 13:22, 10 March 2015

2015-03-10T13:22:54Z

← Older revision		Revision as of 13:22, 10 March 2015
Line 10:		Line 10:
	{{#ev:youtube\|https://www.youtube.com/watch?v=_4lnyoC3mtQ\|800\|center}}		{{#ev:youtube\|https://www.youtube.com/watch?v=_4lnyoC3mtQ\|800\|center}}

	Sentence alignment is an essential step in building a translation system. Often, we have some parallel data (texts in the source and target language which are translations of each other) but we don't know exactly, which sentences correspond to each other. The task here is to find this correspondence (alignment).		Sentence alignment is an essential step in building a translation system. Often, we have some parallel data (texts in the source and target language which are translations of each other) but we don't know exactly which sentences correspond to each other. The task here is to find this correspondence (alignment).

	Once sentence alignment is available, we can proceed further by finding word or phrase correspondences within the aligned sentences, but that's a topic for another lecture.		Once sentence alignment is available, we can proceed further by finding word or phrase correspondences within the aligned sentences, but that's a topic for another lecture.