Computer Science Assignment - Research Paper

70 C o m m u n i C at i o n s o f t h E a C m | j u ly 2 0 1 3 | v o l . 5 6 | n o . 7

contributed articles

V o i c e i n p u t i s a major requirement for practical question answering (QA) systems designed for smartphones. Speech-recognition technologies are not fully practical, however, due to fundamental problems (such as a noisy environment, speaker diversity, and errors in speech). Here, we define the information distance between a speech-recognition result and a meaningful query from which we can reconstruct the intended query, implementing this framework in our RSVP system.

In 12 test cases covering male, female, child, adult, native, and non-native English speakers, each with 57 to 300 questions from an independent test set of

300 questions, RSVP on average re- duced the number of errors by 16% for native speakers and by 30% for non- native speakers over the best-known speech-recognition software. The idea was then extended to translation in the QA domain.

In our project, which is supported by Canada’s International Develop- ment Research Centre (http://www. idrc.ca/), we built a voice-enabled cross-language QA search engine for cellphone users in the developing world. Using voice input, a QA system would be a convenient tool for people who do not write, for people with im- paired vision, and for children who might wish their Talking Tom or R2- D2 really could talk.

The quality of today’s speech-rec- ognition technologies, exemplified by systems from Google, Microsoft, and Nuance does not fully meet such needs for several reasons:

˲ Noisy environments in common audio situations;1

˲ Speech variations, as in, say, adults vs. children, native speakers vs. non-native speakers, and female vs. male, especially when individual voice-input training is not possible, as in our case; and

˲ Incorrect and incomplete sen- tences; even customized speech-rec- ognition systems would fail due to coughing, breaks, corrections, and the inability to distinguish between, say, “sailfish” and “sale fish.”

Speech-recognition systems can be trained for a “fixed command set” of up to 10,000 items, a paradigm that

information Distance Between What i said and What it heard

D o i : 1 0 . 1 1 4 5 / 2 4 8 3 8 5 2 . 2 4 8 3 8 6 9

The RSVP voice-recognition search engine improves speech recognition and translation accuracy in question answering.

BY YanG tanG, Di WanG, JinG Bai, XiaoYan Zhu, anD minG Li

key insights focusing on an infinite but highly

structured domain (such as Qa), we significantly improve general-purpose speech recognition results and general-purpose translation results.

assembling a large amount of internet data is key to helping us achieve these goals; in the highly structured Qa domain, we collected millions of human-asked questions covering 99% of question types.

RsVP development is guided by a theory involving information distance.

j u ly 2 0 1 3 | v o l . 5 6 | n o . 7 | C o m m u n i C at i o n s o f t h E a C m 71

does not work for general speech rec- ognition. We consider a new paradigm: speech recognition limited to the QA domain covering an unlimited number of questions; hence it cannot be trained as a fixed command set domain. How- ever, our QA domain is highly struc- tured and reflects clear patterns.

We use information on the Inter- net in the QA domain to find all pos- sible question patterns, then use it to correct the queries that are partially recognized by speech-recognition software. We collected more than 35 million questions from the Internet, aiming to use them to infer templates or patterns to reconstruct the original intended question from the speech- recognition input. Despite this, we must still address several questions:

˲ How do we know if an input ques- tion from the speech-recognition system is indeed the original user’s question?;

˲ How do we know if a question in

our database is the user’s intended question?;

˲ Should we trust the input or the database?; and

˲ Often, neither the database nor the input is always exactly right, so can we reconstruct the original question?

We provide a mathematical frame- work to address these questions and implement the related RSVP system. Our experiments show RSVP signifi- cantly improves current speech-recog- nition systems in the QA domain.

Related Work Speech recognition1 has made signifi- cant progress over the past 30 years since the introduction of statistical methods and hidden Markov mod- els. Many effective algorithms have been developed, including the EM al- gorithm, the Baum-Welch algorithm, Viterbi N-best search, and N-gram language models trained on large data corpora. However, as explored by Bak-

er et al.,1 automatic speech recogni- tion is still an unsolved problem.

Unlike traditional speech-recog- nition research, we propose a differ- ent paradigm in the QA domain. In it, we are able to collect a very large pure text corpus (no voice) that dif- fers from the fixed command set do- main where it is possible to train up to, say, 10,000 commands. The QA do- main is unbounded, and the number of existing questions on QA websites involves more than 100 million ques- tions, yet with very low coverage of all possible questions. These texts can be “clustered” into patterns. Here, we demonstrate that these patterns have 99% coverage of all possible question types, suggesting we can use them to improve speech-recognition software in this domain.

Previous research suggested that context information,21 the knowledge- base,16,20 and conceptual relation- ships15 all can help address this.

“Who is the mayor?”

72 C o m m u n i C at i o n s o f t h E a C m | j u ly 2 0 1 3 | v o l . 5 6 | n o . 7

contributed articles

Dmax is “universal” in the sense that it always minorizes any other reason- able computable distance metric.

This concept, and its normalized versions, were applied to whole-ge- nome phylogeny,12 chain-letter-evolu- tion history,3 plagiarism detection,4 other phylogeny studies,13 music classification,5 and parameter-free data mining,10 and has been followed by many other applications (for top- ics mentioned here that do not have references, see Li and Vitányi14) in- cluding protein-structure compari- son, heart-rhythm data analysis, QA systems, clustering, multiword ex- pression linguistic analysis, software evolution and engineering, software metrics and obfuscation, webpage authorship, topic, and domain identi- fication, phylogenetic reconstruction, SVM kernel for string classification, ortholog detection,19 analyzing worms and network traffic, image similarity, Internet knowledge discovery,6 multi- document summarization, network structure, and dynamic behavior,17 and gene expression dynamics in macrophase.18

Despite its useful properties and applications, the max distance Dmax(x,y) involves several problems when only partial matches are con- sidered8,22 where the triangle inequal- ity fails to hold and irrelevant infor- mation must be removed. Thus, Li et al.11 introduced a complementary in- formation-distance metric to resolve these problems. In Equation 1 we de- termine the smallest number of bits that must be used to reversibly convert between x and y. To remove the irrel- evant information from x or y, we thus define, with respect to a universal Tur- ing machine U, the cost of conversion between x and y as

Emin(x,y) = min{|p| : U(x, p, r) = y, U(y,p,q) = x, |p| + |q| + |r| ≤ E(x,y)}, (2)

This definition separates r from x and q from y. Modulo an O(log(|x| + |y|)) additive term, the following theorem was proved in Li11:

Theorem 2. Dmin(x,y) = min{K(x|y), K(y|x)}. We can thus define Dmin(x,y) = Emin(x,y) as a complementary information-dis- tance metric that disregards irrelevant information. Dmin is obviously sym-

information Distance Here, we develop the mathematical framework on which we designed our system. To define Kolmogorov com- plexity (invented in the 1960s), we start by fixing a universal Turing ma- chine U. The Kolmogorov complexity of a binary string x, given another bi- nary string y, KU(x|y), is the length of the shortest (prefix-free) program for U that outputs x with input y. Since it can be shown that for a different uni- versal Turing machine U′, the metric differs by only a constant, we write K(x|y) instead of KU(x|y). We write K(x|ε), where ε is the empty string, as K(x). We call a string x random if K(x) ≥ |x|. See Li and Vitányi14 for more on Kolmogorov complexity and its rich applications.

Note K(x) defines the amount of information in x. What would be a good departure point for defining an “information distance” between two objects? In the 1990s, Bennett et al.2 studied the energy cost of con- version between two strings, x and y. John von Neumann hypothesized that performing 1 bit of information pro- cessing costs 1KT of energy, where K is Boltzmann’s constant and T is the room temperature. In the 1960s, ob- serving that reversible computations could be done at no cost, Rolf Landau- er revised von Neumann’s proposal to hold only for irreversible compu- tations. Starting from this von Neu- mann-Landauer principle, Bennett et al.2 proposed using the minimum number of bits needed to convert x to y and vice versa to define their distance. Formally, with respect to a universal Turing machine U, the cost of conver- sion between x and y is defined as

E(x,y) = min{|p| : U (x, p) = y, U (y, p) = x} (1)

It is clear that E(x,y) ≤ K(x|y) + K(y|x). Bennett et al.2 obtained the following optimal result, modulo log(|x| + |y|):

Theorem 1. E (x, y) = max {K(x|y),K(y|x)}.

Thus, we define information distance between two sequences, x and y, as Dmax(x,y) = max{K(x|y),K(y|x)}.

This distance Dmax was shown to sat- isfy the basic distance requirements (such as positivity, symmetricity, and triangle inequality). Furthermore,

We use information on the internet in the Qa domain to find all possible question patterns, then use it to correct the queries that are partially recognized by speech-recognition software.

contributed articles

j u ly 2 0 1 3 | v o l . 5 6 | n o . 7 | C o m m u n i C at i o n s o f t h E a C m 73

metric but does not satisfy triangle inequality. Note that Dmin was used in the QUANTA QA system to deal with concepts that are more popular than others.23,24

min-max Distance Now we formulate our problem in the frame of information distance, given a question database Q and k input questions from a speech-recognition system, as in I = {q1,….,qk} (k ≤ 3 for the Google speech-recognition server in our experiments and k = 1 in our translation application. The goal is to compute the user’s intended question q. It could be one of the qis; it could be a combination of all k of them; and it could also be one of the questions in Q that is close to some parts of the qis.

We wish to find the most plau- sible question q, such that q fits one of the question patterns in Q, and q is “close” to I. We assume Q contains almost all question patterns; later, we provide an experimental justification for this claim.

We can thus formulate our prob- lem as: Given Q and I, find q such that it minimizes the sum of “distances” from Q to q and q to I, as in

I ←→ q ←→ Q

Here, Q is a huge database of 35 mil- lion questions asked by users. We as- sume q is “similar” to one of them; for example, a QA user might ask “Who is the mayor of Waterloo, Ontario?,” but Q might include such questions as “Who is the mayor of Toronto, Ontario?” and “Who is the mayor of Washington, D.C.?” I sometimes contains questions like “Hole is the mayor?” and “Who mayor off Wa- terloo” from the speech-recognition software. Since Q is so large, the Dmax measure does not make sense here, as most of the information in Q is ir- relevant. It is natural to use Dmin(q,Q) here. For the distance between q and I, we use dmax(q, I) to measure it. Given I, Q, we wish to find q that minimizes the function

δ Dmin(q,Q) + Dmax(I,q), (3)

where Dmin measures information dis- tance between q and Q with irrelevant information removed; Dmax is the in-

formation distance between q and I. We know

Dmin (x,y) = min{K(x|y), K(y|x)}, Dmax (x,y) = max{K(x|y), K(y|x)}.

Thus, Dmin (q,Q) = K(q|Q), because Q is very large and q is a single question. Note that d is a coefficient that deter- mines how much weight we wish to give to a correct template or pattern in Q.

Equation 3 thus becomes

δ K(q|Q) + max {K(q|I),K(I,q)}. (4)

Obervations: We need δ >1, so q = I does not minimize Equation 4. If δ is too large, then q = ε might minimize Equa- tion 4. There is a trade-off: Sometimes a less-popular pattern (taking more bits in the Dmin term) might fit I better (taking fewer bits in the Dmax item), and a more popular pattern (taking fewer bits in the Dmin item) might miss one or two key words in I, taking more bits to encode in the Dmax item. Note that δ is optimized for the trade-off.

Encoding issues To minimize Equation 4, we solve three problems:

˲ Encode q using Q in the first term. It is a problem to encode an item with respect to a big set;

˲ Encode q using I or encode I using q, and take whichever is larger in the second term; and

˲ Find all possible candidates q and a q0 that minimizes Equation 4.

We see that Q is very large and con- tains different “types” of questions. For each such type, we extract one or more question templates. In this way, Q can be viewed as a set of templates, with each template, denoted as p, cov- ering a subset of questions from Q. When encoding q, we need not encode q from Q directly. Instead, we encode q with respect to the patterns or tem- plates of Q; for example, if a pattern p in Q appears N times in Q, then we use log2(|Q|=N) bits to encode the in- dex for this pattern. Given pattern p, we encode q with p by encoding their word mismatches. There is a trade- off between the encoding of p and the encoding of q, given p. A common pat- tern may be encoded with a few bits but also may require more bits to en- code a specific question using the pat-

tern; for example, the template “who is the mayor of City Name” requires more bits to encode than the template “who is the mayor of Noun” because the former is a smaller class than the latter. However, the first template re- quires fewer bits to generate the ques- tion “who is the mayor of Waterloo” since it requires fewer bits to encode Waterloo from the class “City Name” than from the class “Noun.”

The patterns could be extracted by pre-processing or dynamically accord- ing to the input. In practice, we extract patterns only from questions relevant to I, denoted as Q′. We organize Q′ hierarchically. Similar questions are mapped to a cluster, and similar clus- ters are mapped to a bigger cluster. We extract one pattern from each cluster using a multiple alignment algorithm. This pattern should be as specific as possible while at the same time cover all questions in the cluster. Note that the higher the cluster in the hierar- chical structure, the more general the pattern. Our hierarchical clustering algorithm thus assures we can extract all possible patterns from relevant questions. We make use of numerous semantic and syntactic information sources during the process, including POS tagger, Name Entity Recognition, WordNet, and Wikipedia. For exam- ple, given a cluster of three questions:

˲ Who is the mayor of Toronto?; ˲ Who is the president of the United

States?; and ˲ Who is a senator from New York?

We could extract one pattern (such as Who is the Leader of Location? “Mayor,” “president,” and “senator”) are all mapped to the Leader class, while “Toronto,” “United States,” and “New York” all belong to the Lo- cation class.

If we treat pattern p as a sentence, the problem of item-to-set encoding becomes item-to-item encoding, as in the computation of K(q|I) and K(I|q). To convert a sentence from another sentence, we need encode only the word mismatches and the missing words. The best alignment between two sentences is found through a standard dynamic programming algo- rithm. We encode a missing word by the negative logarithm of their prob- abilities to appear at the given loca- tions and encode the mismatches by

74 C o m m u n i C at i o n s o f t h E a C m | j u ly 2 0 1 3 | v o l . 5 6 | n o . 7

contributed articles

mapped together; for example, given three questions—whole is the mayor of Waterloo, hole is the mayor of Wa- ter, and whole was the mayor of Wa- ter—the best word alignment would look like this:

Whole is the mayor of Waterloo hole is the mayor of Water Whole was the mayor of Water

Step 2. Improve input questions: ˲ Build a question based on the

word-alignment results from Step 1; for each aligned word block, we choose one word to appear in the result;

˲ We assume that a good format question should contain a “wh”-word,

including what, who, which, whose, whom, when, where, why, how, or what, or an auxiliary verb, including be, have, do, shall, will (would), shall (should), may (might), must, need, dare, or ought. If the inputs do not contain any such word, we add proper words into the question candidates; and

˲ Since some correct words may not appear in the input, we further expand the question candidates with hom- onym dictionaries and metaphone dictionaries.

Step 3. Analyze relevant database patterns:

˲ Find relevant database questions, sorting them based on their seman- tic and syntactic similarity to the im- proved input questions from Step 2;

˲ If a question is almost the same as one of the input questions, we return that input question directly, and no further steps are done in this case;

˲ The database questions involve many forms and patterns. We group similar questions together through a hierarchical clustering algorithm. The distance between two clusters is cal-

calculating their semantic and mor- phology similarities. It requires fewer bits to encode between synonyms than antonyms.

Equation 4 must select the candi- date question q, for which we use two strategies:

Offline. We cluster questions in Q and generate patterns offline, finding the most likely pattern, then generate q that is close to the input and to one of the patterns; and

Online. We consider only the ques- tion candidates relevant to the input and that could be matched by at least one of our templates generated from a few questions and that share some keywords with the input in Q.

Finally, we choose the best q that minimizes Equation 4. Furthermore, we apply a bigram language model to filter questions with low trustworthi- ness. The language model is trained in our background question set Q. The value δ is trained as a part of our ex- periments. In our system the δ value is a function of the lengths of the input questions.

We have thus implemented RSVP, which, given speech recognition input {q1, q2, q3}, finds q such that Equation 4 is minimized.

implementation Details The following are some RSVP imple- mentation details:

Step 1. Analyze input: ˲ Split the questions into words by

Stanford Pos Tagger; at the same time, name entities are extracted from the input questions using Stanford NER, Linepipe NER, and YAGO; and

˲ Find the best alignments among the input questions through dynamic programming. Words or name enti- ties with similar pronunciations are

culated based on the syntactic similar- ity between questions. The algorithm stops when the minimum distance between clusters reach a predefined threshold;

˲ When the relevant questions are grouped into clusters, we are able to extract patterns from each cluster. Following the algorithm outlined in Step 1, we align questions in each group, using their semantic simi- larities to encode the word distance. Then a group of questions is con- verted into a single list with multiple word blocks, with each block contain- ing several alternative words from dif- ferent questions; for example, given questions “Who is the mayor of New York,” “Who is the president of Unit- ed States,” and “Which person is the leader of Toronto,” we obtain a list of word blocks after alignment:

{who, who, which person}, {is}, {the}, { mayor, leader, president } of { New York, United States, Toronto}; and

˲ For each aligned word block, we further extract tags that would best de- scribe the slot; here, YAGO9 is used to describe the meaning of each word or phrase. We extract several most-com- mon facts as the description of each word block. We then obtain one or several semantic patterns composed of words and facts from YAGO.

Step 4. Generate the candidate ques- tions:

˲ Map the original input questions into the patterns we extracted from the database and replace the words in the patterns with the words from the input. Many candidate questions could be generated by considering the various combinations of word replace- ments; and

˲ To reduce complexity, we train a bigram language model from our question set, removing candidate questions with low probability.

Step 5. Rank candidate questions us- ing information distance:

˲ Calculate the distance between the candidate questions and the input questions K(q|I) and K(I|q). We align the candidate and input questions and encode the word mismatches and missing words, encoding a miss- ing word through minus logarithm of their probability to appear at the said

contributed articles

j u ly 2 0 1 3 | v o l . 5 6 | n o . 7 | C o m m u n i C at i o n s o f t h E a C m 75

locations and calculating word mis- matches through their semantic, mor- phology, and metaphone similarities;

˲ Calculate the distance between the candidate questions and the pat- terns K(q|p). A method similar to the previous step is used to calculate the distances between questions and pat- terns; and

˲ RSVP Ranks all the candidates us- ing Equation 4.

Step 6. Return the candidate with minimum information distance score as the final result: In order to improve speed, the last three items of step 3 may be performed offline on the com- plete database Q.

Completeness of the Database Q We tested the hypothesis that Q con- tains almost all common question types. The test set T contained 300 questions, selected (with the crite- ria of no more than 11 words or 65 letters, one question in a sentence, and no non-English letters) from an independent Microsoft QA set at http://research.microsoft.com/en-us/ downloads/88c0021c-328a-4148-a158- a42d7331c6cf. We found that all but three have corresponding patterns in Q. Only three questions lacked strictly similar patterns in Q: Why is some sand white, some brown, and some black? Do flying squirrels fly or do they just glide? And was there ever a movement to abolish the electoral college? We will provide the data set T upon request.

Experiments Our experiments aimed to test RSVP’s ability to correct speech-recognition errors in the QA domain, focusing on non-native speakers, as there are three non-native English speakers for each native English speaker in the world. Here, we further test and justify our proposed methodology by extend- ing it to translation in the QA domain.

Experiment setup. We initially (in 2011) used the Nuance speech-rec- ognition server and later switched to Google speech recognition (http:// google.com), because the Google serv- er has no daily quota and responds quicker. The RSVP system is imple- mented in a client-server architecture. The experiments were performed at a computer terminal with a micro-

phone. The experimenter would read a question, and Google speech recogni- tion would return three options. RSVP uses the three questions as input and computes the most likely question.

Dataset. We use the set T described in the previous section. T contains 300 questions. T was chosen indepen- dently, and T ∩ Q = Φ. Not all questions in T were used by each speaker in the experiments; non-native speakers and children skipped sentences that con- tain difficult-to-pronounce words, and less-proficient English speakers tend to skip more questions.

Time complexity. On a server with four cores, 2.8GHz per core, and 4G memory, RSVP typically uses approxi- mately 500ms to correct one question; that is, the speaker reads a question into a microphone, Google voice rec- ognition returns three questions, and RSVP uses the questions as input, tak- ing approximately half a second to output one final question.

Human speaker volunteers. Such experiments are complex and time consuming. We tried our best to re- move the individual speaker variance by having different people perform the experiments independently. We recruited 14 human volunteers, in- cluding native and non-native Eng- lish speakers, adults and children, fe- males and males (see Table 1) during

the period 2011 to 2012. We performed 12 sets of experi-

ments involving 14 different speak- ers, all using the same test set T or a subset of T. Due to children’s natu- rally short attention spans, the three native English-speaking children (two males, one female) completed one set of experiment (experiment 7), each responsible for 100 questions. A non- native-speaking female child, age 12, performed the test (experiment 10) independently but was able to finish only 57 questions.

In the following paragraphs, “CC” signifies that the speech-recognition software (from Google) returned the correct answer as the first option and RSVP agrees with it; “WC” signifies that the speech-recognition software returned the wrong answer as the first option and RSVP returned the correct answer; “CW” signifies that the speech-recognition software re- turned the correct answer as the first option and RSVP returned the wrong answer; and “WW” signifies that the speech-recognition software returned the wrong answer as the first option and RSVP also returned the wrong an- swer. All experiments were performed in quiet environments; in each, the speaker tried again if neither the speech recognition nor RSVP was cor- rect (see Table 2).

table 1. individuals used in our experiments.

native speaker non-native speaker

Adult Child Adult Child

Female 0 1 4 1

Male 3 2 3 0

table 2. Experimental results for speech correction.

Experiment # questions CC WC CW WW Base translator accuracy

RsVP accuracy

Google as base translator

428 112 211 6 99 27.5% 75.6%

Microsoft as base translator

428 116 207 11 94 29.6% 75.6%

Google as base translator

52 21 15 0 16 40% 69%

Google as base translator

114 44 49 1 20 38% 81.6%

76 C o m m u n i C at i o n s o f t h E a C m | j u ly 2 0 1 3 | v o l . 5 6 | n o . 7

contributed articles

bomb work? Original question: How holidays

are celebrated around the world? Google speech-recognition output: call holidays are celebrated around in the wall? call holidays are celebrated around in the world? how all holidays are celebrated around in the wall? RSVP output: how holidays are cel- ebrated around in the world?

Original question: Are there any known aliens? Google speech-recog- nition output: are there any loans de- viance? are there any loans aliens? are there any known deviance? RSVP out- put: Are there any known aliens?

Original question: What does a frog eat? Google speech-recognition output: what is front seat? what is the frogs eat? what does the front seat? RSVP output: What does frogs eat?

Experiment 2. Native speaker, male;

Experiment 1. Non-native speaker, male. Here, the speaker chose only easy-to-read questions from the 300-question Microsoft test set; the following are examples where RSVP corrected Google’s errors:

Original question: How many types of birds are found in North America? Google speech-recognition output: How many pints of birds are formed in North America? How many pints of birds are found in North America? How many pints of birds performed in North America? RSVP output: How many types of birds are found in North America?

Original question: How does the atom bomb work? Google speech- recognition output: call does the atom bomb work? All does the atom bomb work? aha does the atom bomb work? RSVP output: How does the atom

Experiment 3. Native speaker, male; Experiment 4. Non-native speaker,

male; Experiment 5. Non-native speaker,

female; Experiment 6. Non-native speaker,

female. Experiment 7. Three native English-

speaking children, 100 questions each. They are eight years old, female; nine years old, male; and 11 years old, male. In principle, we prefer inde- pendent tests with one individual re- sponsible for the complete set of 300 questions. However, we were only able to get each of the children to do 100 questions, skipping the difficult ones. The result is similar to that of adult native English speakers;

Experiment 8. Native English speak- er, male;

Experiment 9. Non-native English speaker, male;

Experiment 10. Non-native English speaker, female, 11 years old, in Can- ada to attend summer camp to learn English; her English was rudimentary and consequently was able to read only 57 questions out of 300;

Experiment 11. Non-native English speaker, female; and

Experiment 12. Non-native English speaker, female.

In our experiments, Table 2, the non-native speakers and the children selected relatively easy-to-read ques- tions (without, say, difficult-to-pro- nounce names) from T to do the tests. The ratio of improvements was better for the non-native speakers, reducing the number of errors (WW column) by 30% on average for experiments 1, 4, 5, 6, 9, 10, 11, and 12. For native speakers, RSVP also delivered a clear advantage, reducing the number of er- rors (WW column) by 16% on average for experiments 2, 3, 7, and 8. Such an advantage would be amplified in a noisy real-life environment. Allow- ing the speaker to repeat the question would increase the success rate, as in the following example (with Google): RSVP generated “How many toes does Mary Monroe have?” for the first query and “How many titles does Marilyn Monroe have?” for the second query. Combining the two questions, RSVP generated the correct intended ques- tion “How many toes does Marilyn Monroe have?”

translation examples.

Translation Examples

从多伦多到北京坐飞机多长时间

Google translation: Fly from Toronto to Beijing long?

Our translation: How long does it take to fly from Toronto to Beijing?

人身上有多少块骨头？

Google translation: People who have a few bones?

Our translation: How many bones do people have?

台湾的人口多少？

Google translation: Taiwan’s population size?

Our translation: What is the population size of Taiwan?

恐龙上什么时候灭绝的？

Google translation: When did the dinosaurs extinct?

Our translation: When did the dinosaurs become extinct?

table 3. Experimental results for speech correction

Experiment total no. of questions CC WC CW WW

1 164 105 39 5 15

2 300 219 25 6 50

3 300 222 15 5 58

4 257 141 41 7 68

5 181 100 26 4 51

6 214 125 29 10 50

7 206 145 19 8 34

8 298 180 12 4 102

9 131 77 14 0 40

10 57 28 4 1 24

11 63 35 9 1 18

12 107 62 9 2 34

contributed articles

j u ly 2 0 1 3 | v o l . 5 6 | n o . 7 | C o m m u n i C at i o n s o f t h E a C m 77

translation To further justify the methodology proposed here, we extend the ap- proach to translation in the QA do- main for cross-language search. Here, we use Chinese-English cross-lan- guage search as an example, though the methodology works for other lan- guages, too.

A Chinese-speaking person can perform a cross-language search of the English Internet in two ways:

Translate it all. Translate the whole English Internet, including all QA pairs in the English QA community and English (Wikipidea) databases, into Chinese; or

Translate a question. Translate a Chinese question into English, find- ing the answer in English, then trans- late the answer back to Chinese.

General-purpose translators today perform so poorly that the first option is out of the question. The RSVP meth- odology enables the second option, which involves two translations: the Chinese question to English, then the English answer back to Chinese. Since the QA answers are usually simple and read by humans, and the database re- lations can be manually translated, a general-purpose translator is suffi- cient and sometimes not even needed. The key to this approach is translating Chinese questions into English. We implemented the translation system and cross-language (Chinese-English) search as part of the RSVP QA system through the following steps:

˲ Translate a Chinese question into English through a general-purpose translator;

˲ Apply the (modified) correction procedure described here;

˲ Perform English QA search; and ˲ Translate the result back into Chi-

nese through a general-purpose trans- lator.

Table 3 outlines experiments with our translation system, using the no- tation outlined earlier: CC, WC, CW, and WW. The first three used data collected as we developed RSVP; the fourth used an independent dataset of 114 questions on a range of topics (see the figure here).

Conclusion This work would be more effective if it were integrated into speech-recogni-

tion software so more voice informa- tion could be used. However, it targets dynamic special domains that are so numerous that training them sepa- rately would be prohibitive.

In addition to special-domain translation, the RSVP methodology can be used to correct the grammati- cal errors and spelling mistakes in a normal QA text search, as well as to create an automatic writing assistant for a highly structured domain.

Moreover, “tuning” improves all systems; for example, if we ask “What is the distance between Toronto and Waterloo bla,” then we know the extra “bla” should be removed, as inferred from system knowledge, requiring zero bits to encode such a deletion. The theory allows us to add “inferra- ble rules” at no additional cost.

acknowledgments We thank Li Deng of Microsoft for his advice on speech-recognition software and Leonid Levin of Boston University for discussions and suggestions on al- ternative formulations. We are grateful to the volunteers who participated in our experiments. We thank the refer- ees and Nicole Keshav for helping us improve the article. We also thank Alan Baklor of Answer.com for his help. This work has been partially supported by Canada’s IDRC Research Chair in Infor- mation Technology program, NSERC Discovery Grant OGP0046506, the Canada Research Chair program, a CFI Infrastructure grant, an NSERC Collab- orative grant, Ontario’s Premier’s Dis- covery Award, and the Killam Prize.

References 1. baker, J.M., Deng, l., glass, J., Khudanpur, s., lee, c.h.,

Morgan, n., and o’shaughnessy, D. Developments and directions in speech recognition and understanding, Part 1. IEEE Signal Processing Magazine 26, 3 (May 2009), 75–80.

2. bennett, c.h., gács, P., li, M., Vitányi, P., and Zurek, W. information distance. IEEE Transactions on Information Theory 44, 4 (July, 1998), 1407–1423.

3. bennett, c.h., li, M., and Ma, b. chain letters and evolutionary histories. Scientific American 288, 6 (June 2003), 76–81.

4. chen, X., francia, b., li, M., McKinnon, b., and seker, a. shared information and program plagiarism detection. IEEE Transactions on Information Theory 50, 7 (July 2004), 1545–1550.

5. cilibrasi, r., Vitányi, P., and de Wolf, r. algorithmic clustering of music based on string compression. Computer Music Journal 28, 4 (Winter 2004), 49–67.

6. cilibrasi, r. and Vitányi, P. the google similarity distance. IEEE Transactions on Knowledge and Data Engineering 19, 3 (Mar. 2007), 370–383.

7. cuturi, M. and Vert, J.P. the context-tree kernel for strings. Neural Networks 18, 4 (oct. 2005), 1111–1123.

8. fagin, r. and stockmeyer, l. relaxing the triangle inequality in pattern matching. International Journal of Computer Vision 28, 3 (1998), 219–231.

9. hoffart, J., suchanek, f.M., berberich, K., and Weikum, g. yago2: a spatially and temporally enhanced knowledgebase from Wikipedia. Artificial Intelligence 194 (Jan. 2013), 28–61.

10. Keogh, e., lonardi, s., and ratanamahatana, c.a. towards parameter-free data mining. in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. acM Press, new york, 2004, 206–215.

11. li, M. information distance and its applications. International Journal on the Foundations of Computer Science 18, 4 (aug. 2007), 669–681.

12. li, M., badger, J., chen, X., Kwong, s., Kearney, P., and Zhang, h. an information-based sequence distance and its application to whole mitochondrial genome phylogeny. Bioinformatics 17, 2 (feb. 2001), 149–154.

13. li, M., chen, X., li, X., Ma, b., and Vitányi, P. the similarity metric. IEEE Transactions on Information Theory 50, 12 (Dec. 2004), 3250–3264.

14. li, M. and Vitányi, P. An Introduction to Kolmogorov Complexity and Its Applications, Third Edition. springer-Verlag, new york, 2008.

15. lieberman, h., faaborg, a., Daher, W., and espinosa, J. how to wreck a nice beach you sing calm incense. in Proceedings of the 10th International Conference on Intelligent User Interfaces (2005), 278–280.

16. lopes, l.r. a software agent for detecting and correcting speech recognition errors using a knowledge base. satnac, 2008.

17. nykter, M., Price, n.D., larjo, a., aho, t., Kauffman, s.a., yli-harja, o., and shmulevich, i. critical networks exhibit maximal information diversity in structure- dynamics relationships. Physical Review Letters 100, 5 (feb. 2008), 058702-706.

18. nykter, M., Price, n.D., aldana, M., ramsey, s.a., Kauffman, s.a., hood, l.e., yli-harja, o., and shmulevich, i. gene expression dynamics in the macrophage exhibit criticality. Proceedings of the National Academy of Sciences 105, 6 (feb. 2008), 1897–1900.

19. Pao, h.K. and case, J. computing entropy for ortholog detection. in Proceedings of the International Conference on Computational Intelligence (istanbul, turkey, Dec. 17–19, 2004).

20. rosenfeld, r. two decades of statistical language modeling: Where do we go from here? Proceedings of the IEEE 88, 8 (aug. 2000), 1270–1278.

21. sarma, a. and Palmer, D.D. context-based speech recognition error detection and correction. in Proceedings of the Human Language Technology Conference (boston, May 2–7). association of computational linguistics, stroudsburg, Pa, 2004, 85–88.

22. Veltkamp, r.c. shape matching: similarity measures and algorithms. in Proceedings of the International Conference on Shape Modeling Applications (genoa, italy, 2001), 188–197.

23. Zhang, X., hao, y., Zhu, X.y., and li, M. new information measure and its application in question-answering system. Journal of Computer Science and Technology 23, 4 (July 2008), 557–572.

24. Zhang, X., hao, y., Zhu, X., and li, M. information distance from a question to an answer. in Proceedings of the 13th ACM SIGKDD Conference on Knowledge Discovery in Data Mining (san Jose, ca, aug. 12–15). acM Press, new york, 2007, 874–883.

Yang Tang ([email protected]) is a research associate in the David r. cheriton school of computer science at the university of Waterloo, Waterloo, ontario.

Di Wang ([email protected]) is a graduate student in the David r. cheriton school of computer science at the university of Waterloo, Waterloo, ontario.

Jing Bai ([email protected]) is a researcher in Microsoft corporation, silicon Valley campus, sunnyvale, ca.

Xiaoyan Zhu ([email protected]) is a professor in the tsinghua national laboratory for information science and technology and Department of computer science and technology and director of state Key laboratory of intelligent technology and systems at tsinghua university, beijing.

Ming Li ([email protected]) is canada research chair in bioinformatics and a university Professor in the David r. cheriton school of computer science at the university of Waterloo, Waterloo, ontario.

© 2013 acM 0001-0782/13/07