US 7,346,487 B2Grant

Method and apparatus for identifying translations

Issue Date:2008-03-18

•33 Claims

•7 Drawing Sheets

Abstract

A method for identifying a translation transforms a representation of context words in a source language into a transformed representation of context in a target language based on multiple different translations for at least one context word. Candidate representations of context words in a target language are determined for at least two candidate translations. The transformed representation is used to score each candidate representation and the scores are used to select a candidate translation. In another aspect of the invention, a method and apparatus are provided for updating a translation dictionary by receiving votes from multiple clients as to which translation is correct.

Metadata

Assignee

Microsoft Corporation

Inventor

Hang Li

Application Information

Application Number:US 10/626,455

Filing Date:2003-07-23

Priority Date:2003-07-23

Art Unit:2626

Classifications

IPC:

G06F17/28G06F17/21G10L11/00

Patent Drawings (7 sheets)

Description

Background of the Invention

[0001] The present invention relates to automatic translation systems. In particular, the present invention relates to translation identification using non-parallel corpora.

[0002] In translation systems, a string of characters in one language is converted into a string of characters in another language. One challenge to such translation systems is that it is difficult to construct a dictionary that can provide a translation for every word in the source and target languages. One reason for this is the number of words in the languages, which makes it labor intensive to create such a dictionary. Another reason is that new words are constantly being added to the languages, requiring a large amount of work to keep the dictionary current. The lack of available translations is particularly a problem for multi-word phrases such as the noun phrases “information age” or “information asymmetry” since there are a large number of such phrases and because new phrase are continually being created.

[0003] To overcome the work involved in building and updating translation dictionaries, several systems have been created that automatically generate a translation dictionary. Under one set of systems, the translation dictionary is formed using parallel bilingual corpora. In such systems, the same information is written in two different languages. The text in one of the languages is aligned with the text in the other language, typically on a sentence-by-sentence basis. After this alignment is complete, comparisons between the aligned texts are made to identify words that are likely translations of each other.

[0004] Although using parallel corpora is an effective technique, obtaining such corpora is difficult in practice. To deal with this difficulty, some systems have proposed using non-parallel corpora. Under such systems, a set of candidate translations are assumed to be given or can be easily collected. The goal of the systems is to select the best candidate from the set of candidates.

[0005] To do this, the systems rely on a linguistic phenomenon in which the contexts of a translation for a word in the target language are the same as the contexts of the word in the source language. Thus, these systems identify the best candidate by translating the contexts in the source language into the target language and selecting the candidate translation that has a target language context that best matches the translated context. In one system, the contexts are represented by vectors where each element in the vector represents a word in the context.

[0006] One problem with such systems is that they are dependent on an accurate translation of the contexts. In many systems, it is assumed that there is a one-to-one mapping between context words in the source language and context words in the target language and as such, an accurate translation can be achieved by consulting a translation dictionary. However, in reality, there is a many-to-many relationship between words in a source language and words in a target language. As a result, each word in the source context can have multiple translations in the target language. In addition, words in the target context can have several different translations in the source language.

[0007] Thus, a system is needed that provides for accurate translations of the contexts while taking into account the many-to-many relationship between words in the source and target languages.

[0008] In addition, since all automatic translation dictionary systems are prone to error, it is desirable to develop a system that limits the number of incorrect translations that are entered into the dictionary.

Summary of the Invention

[0009] A method for identifying a translation transforms a representation of context words in a source language into a transformed representation of context in a target language based on multiple different translations for at least one context word. Candidate representations of context words in a target language are determined for at least two candidate translations. The transformed representation is used to score each candidate representation and the scores are used to select a candidate translation.

[0010] In another aspect of the invention, a method and apparatus are provided for updating a translation dictionary. Under this aspect of the invention, two possible translations of a source word are provided to at least two clients. Each client provides an indication as to which translation is believed to be correct. The indications are used to select one of the translations for entry in the dictionary.

Brief Description of the Drawings

[0011] FIG. 1 is a block diagram of a general computing environment in which the present invention may be practiced.

[0012] FIG. 2 is a flow diagram of a method of identifying translations using non-parallel corpora under the present invention.

[0013] FIG. 3 is a block diagram of a system for identifying translations using non-parallel corpora under the present invention.

[0014] FIG. 4 is a flow diagram of a method of allowing multiple users to vote on a translation before updating a translation dictionary.

[0015] FIG. 5 is a block diagram of one embodiment of a system that allows multiple users to vote on a translation before updating a translation dictionary.

[0016] FIG. 6 is an example of a web page under one embodiment of the present invention that allows users to vote for candidate translations.

Detailed Description of Illustrative Embodiments

[0017] FIG. 1 illustrates an example of a suitable computing system environment 100 on which the invention may be implemented. The computing system environment 100 is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Neither should the computing environment 100 be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment 100.

[0018] The invention is operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well-known computing systems, environments, and/or configurations that may be suitable for use with the invention include, but are not limited to, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, telephony systems, distributed computing environments that include any of the above systems or devices, and the like.

[0019] The invention may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The invention is designed to be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules are located in both local and remote computer storage media including memory storage devices.

[0020] With reference to FIG. 1, an exemplary system for implementing the invention includes a general-purpose computing device in the form of a computer 110. Components of computer 110 may include, but are not limited to, a processing unit 120, a system memory 130, and a system bus 121 that couples various system components including the system memory to the processing unit 120. The system bus 121 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus.

[0021] Computer 110 typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by computer 110 and includes both volatile and nonvolatile media, removable and non-removable media. By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computer 110. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of any of the above should also be included within the scope of computer readable media.

[0022] The system memory 130 includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) 131 and random access memory (RAM) 132. A basic input/output system 133 (BIOS), containing the basic routines that help to transfer information between elements within computer 110, such as during start-up, is typically stored in ROM 131. RAM 132 typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit 120. By way of example, and not limitation, FIG. 1 illustrates operating system 134, application programs 135, other program modules 136, and program data 137.

[0023] The computer 110 may also include other removable/non-removable volatile/nonvolatile computer storage media. By way of example only, FIG. 1 illustrates a hard disk drive 141 that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive 151 that reads from or writes to a removable, nonvolatile magnetic disk 152, and an optical disk drive 155 that reads from or writes to a removable, nonvolatile optical disk 156 such as a CD ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive 141 is typically connected to the system bus 121 through a non-removable memory interface such as interface 140, and magnetic disk drive 151 and optical disk drive 155 are typically connected to the system bus 121 by a removable memory interface, such as interface 150.

[0024] The drives and their associated computer storage media discussed above and illustrated in FIG. 1, provide storage of computer readable instructions, data structures, program modules and other data for the computer 110. In FIG. 1, for example, hard disk drive 141 is illustrated as storing operating system 144, application programs 145, other program modules 146, and program data 147. Note that these components can either be the same as or different from operating system 134, application programs 135, other program modules 136, and program data 137. Operating system 144, application programs 145, other program modules 146, and program data 147 are given different numbers here to illustrate that, at a minimum, they are different copies.

[0025] A user may enter commands and information into the computer 110 through input devices such as a keyboard 162, a microphone 163, and a pointing device 161, such as a mouse, trackball or touch pad. Other input devices (not shown) may include a joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit 120 through a user input interface 160 that is coupled to the system bus, but may be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). A monitor 191 or other type of display device is also connected to the system bus 121 via an interface, such as a video interface 190. In addition to the monitor, computers may also include other peripheral output devices such as speakers 197 and printer 196, which may be, connected through an output peripheral interface 195.

[0026] The computer 110 is operated in a networked environment using logical connections to one or more remote computers, such as a remote computer 180. The remote computer 180 may be a personal computer, a hand-held device, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer 110. The logical connections depicted in FIG. 1 include a local area network (LAN) 171 and a wide area network (WAN) 173, but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

[0027] When used in a LAN networking environment, the computer 110 is connected to the LAN 171 through a network interface or adapter 170. When used in a WAN networking environment, the computer 110 typically includes a modem 172 or other means for establishing communications over the WAN 173, such as the Internet. The modem 172, which may be internal or external, may be connected to the system bus 121 via the user input interface 160, or other appropriate mechanism. In a networked environment, program modules depicted relative to the computer 110, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation, FIG. 1 illustrates remote application programs 185 as residing on remote computer 180. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

[0028] The present invention provides a method and apparatus for identifying translations for words and phrases using two non-parallel corpora. In on aspect of the invention, the present invention uses the Expectation-Maximization algorithm to train translations of context vectors. The translations of context vectors are compared to context vectors in the target language to select a translation for a source word from a set of candidates in the target language. The method of one embodiment of this aspect of the invention is shown in the flow diagram of FIG. 2 and an embodiment of the apparatus is shown in the block diagram of FIG. 3.

[0029] A second aspect of the present invention receives user feedback before updating a translation dictionary. In particular, this aspect of the invention receives feedback from multiple users relative to a set of candidate translations. Candidate translations that receive more than a threshold amount of votes are entered into the translation dictionary. A method for practicing this aspect of the invention is shown in the flow diagram of FIG. 4 and a system for performing this aspect of the invention is shown in the block diagram of FIG. 5.

[0030] Returning to FIGS. 2 and 3 and the method of selecting a translation using the Expectation-Maximization algorithm, the process of FIG. 2 begins at step 200 where a phrase or word that needs to be translated is identified. Under one embodiment, this is done by a user, but in other embodiments it can be done by an automatic translation system that is unable to find a translation for a phrase or word. For simplicity, the word or phrase that needs to be translated is referred to as the source phrase below.

[0031] At step 202, a search is performed by a context identifier 300 to find examples of the source phrase in a corpus. Under one embodiment, the corpus consists of web pages 302 written in the source language that are available through a network connection such as Internet 304. In other embodiments, the corpus can consist of documents located on an intranet or within a single computer.

[0032] Based on the occurrences of the source phrase found by context identifier 300, one or more source frequency vectors 306 are constructed from the context words surrounding the source phrase. Under one embodiment, a single context vector is generated with each element in the vector representing a single context word and providing the number of times the word was found as a context word for the source phrase. For example, if the source phrase is “car wash” and the word “wax” is found twenty times as a context word for the phrase “car wash”, one element of the source frequency vector will be a value of twenty for the word “wax”.

[0033] A word is considered a context word for the source phrase if it is found within a window of words around the source phrase. The number of words in the window, known as the context length, is a matter of design choice.

[0034] In other embodiments, a separate source frequency vector is generated for each of a plurality of context lengths. For example, if one context length is ten words and another context length is fifteen words, one source frequency vector will be produced for the ten-word context and one source frequency vector will be produced for the fifteen-word context.

[0035] At step 204, a set of target candidate translations representing possible translations for the source phrase is identified by a target candidate identifier 308. Under one embodiment, where the source phrase consists of multiple words, the target candidates are identified by identifying all of the possible translations for each of the words in the source phrase using translation dictionary 310. For example, if the source phrase is “information age” and “information” has a single translation A, and “age” has three, translations B(how old someone is), C(historical era) and D(legal adulthood), “A” would be returned for “information” and “B”, “C”, and “D” would be returned for “age”. The individual translations are then combined to form each possible combination. Using the example above, this results in compositionally created translation candidates “AB”, “AC”, and “AD”.

[0036] A search is then performed on a target language corpus, such as target language web pages 312 available through Internet 304, to determine the number of times each compositionally created translation appears in the target corpus. All of the compositionally created candidates that appear at least once in the corpus are kept as translation candidates and the rest are discarded.

[0037] In another embodiment, candidate translations for the source phrase are identified by searching a target language corpus, such as target language web pages 312, for the source phrase itself. In many target language documents, source language phrases may appear in brackets or parenthesis after the target language translation of the source phrase. Thus, if a source phrase is found in a target language document, target translation candidates can be formed by grouping the words or characters that precede the source phrase into candidate translations. For example, if a sequence of five Chinese characters “ABCDE” preceded a source phrase in a Chinese text, target translation candidates of “E”, “DE”, “CDE”, “BCDE”, and “ABCDE” would be formed. As above, a search for each of these possible target translation candidates can be performed on the target language corpus so that candidates that do not occur frequently can be discarded.

[0038] Once the candidate translations have been identified at step 204, the contexts in which each of the candidate translations are found in the target language corpus are used to construct a separate target language frequency vector 314 for each candidate at step 206. As with the source language frequency vectors, each element in a target language frequency vector represents the number of times a single word was found as a context word. The contexts for the candidates can be retrieved when determining if a candidate translation occurs frequently enough to remain under consideration at step 204.

[0039] At step 208, an Expectation-Maximization (EM) algorithm is used by an EM trainer 316 to identify a translation frequency vector 318. Translation frequency vector 318 is a transform of the source language frequency vector into a vector in the target language. In terms of an equation:

[0040]

\begin{matrix} f_{E} (c) = P (c) \sum_{e \in E} f (e) & Eq . 1 \end{matrix}

where f(e) is one element in the source language frequency vector that indicates the frequency with which word e of the source language appears as a context word for the source phrase, E is the set of all words in the source language, c is a word in the target language, P(c) is the prior probability of the word c in the target language, and f_E(c) is one element in the translation frequency vector.

[0041] Equation 1 is performed for each word c in the set of all possible target language words C to provide the complete translation frequency vector.

[0042] To determine the prior probability, P(c), the present invention utilizes an EM algorithm. Under embodiments of the present invention, the EM algorithm is based on the assumption that each instance of a context word is independently generated according to a distribution defined as:

[0043]

\begin{matrix} P (e) = \sum_{c \in C} P (c) P (e | c) & Eq . 2 \end{matrix}

where P(e) is the probability of a word e in the source language, P(c) is the prior probability of a word c in the target language, and P(e|c) is the conditional probability of source language word e given target language word c.

[0044] Using the assumption of Equation 2, the E-step is defined as:

[0045]

\begin{matrix} P (c | e) \leftarrow \frac{P (c) P (e | c)}{\sum_{c \in C} P (c) P (e | c)} & Eq . 3 \end{matrix}

and the M-Step is defined as:

[0046]

\begin{matrix} P (c) \leftarrow \sum_{e \in E} f (e) P (c | e) & Eq . 4 \\ P (e | c) \leftarrow \frac{f (e) P (c | e)}{\sum_{e \in E} f (e) P (c | e)} & Eq . 5 \end{matrix}

where f(e) is a source frequency vector element for the source phrase and P(c|e) is the conditional probability of a word c in the target language given a word e in the source language. Before beginning the EM algorithm, the values used in the E-step are initialized for all words c in the source language C, c∈C as:

[0047]

\begin{matrix} P (c) = \frac{1}{\langle C \rangle} & Eq . 6 \\ P (e | c) = {\begin{matrix} \frac{1}{\langle Γ_{c} \rangle}, if e \in Γ_{c} \\ 0, if e \notin Γ_{c} \end{matrix} & Eq . 7 \end{matrix}

where |C| is the number of words in the source language, Γ_cis the set of source language translations for target language word c, and |Γ_c| is the number of source language translations for target language word c. The set of source language translations is determined from translation dictionary 310. Since each target language word may have multiple source language words, the EM algorithm is based on multiple possible translations for context words.

[0048] After initialization, the E-step and the M-step are iterated until the parameters converge. The prior probability and the source frequency vector 306 are then used in Equation 1 to generate translation frequency vector 318.

[0049] At step 210, translation frequency vector 318 and target frequency vectors 314 are used by a translation selection module 320 to select one candidate translation as the translation 322 for the source phrase.

[0050] Under one embodiment, the selection is made using a Naïve Bayesian Classifier to select a candidate translation {tilde over (c)} with the largest posterior probability, P({tilde over (c)}|D), where D is the translation frequency vector D=(f_E(c₁),f_E(c₂), . . . , f_E(c_n)). Based on Bayes' rule and the assumption that the data in D are independently generated from P(c|{tilde over (c)}),c ∈C, finding the maximum posterior probability comprises finding the translation that maximizes the following function:

[0051]

\begin{matrix} \log P (\tilde{c}) + \sum_{c \in C} f_{E} (c) \log P (c | \tilde{c}) & Eq . 8 \end{matrix}

or equivalently, finding the translation that minimizes:

[0052]

\begin{matrix} - α \log P (\tilde{c}) - \sum_{c \in C} f_{E} (c) \log P (c | \tilde{c}) & Eq . 9 \end{matrix}

where α is an additional parameter used to emphasize prior information, which under one embodiment is set to 5, f_E(c) is an element of the translation frequency vector 318, the prior probability, P({tilde over (c)}), is estimated by using the document frequencies of the translation candidates in the target language corpus, and the conditional probability is defined as:

[0053]

\begin{matrix} P (c | \tilde{c}) = \frac{f_{\tilde{c}} (c)}{\sum_{c \in C} f_{\tilde{c}} (c)} & Eq . 10 \end{matrix}

where f_{{tilde over (c)}}(c) is an element of the target frequency vector for target word c and translation candidate {tilde over (c)}.

[0054] Thus, using the translation frequency vector determined through the EM algorithm and Equation 9, the present invention is able to identify a most likely translation for the source phrase.

[0055] In further embodiments of the present invention, an ensemble of the Naïve Bayesian Classifier is used. Specifically, the ensemble is defined as:

[0056]

\begin{matrix} P (\tilde{c} | D) = \frac{1}{s} \sum_{i = 1}^{s} P (\tilde{c} | D_{i}) & Eq . 11 \end{matrix}

where each D_irepresents a frequency vector for a different context with a different window size. Thus, one D_imay be for a context of four words and one D_imay be for a context of six words. Under the ensemble embodiment, selecting a candidate translation under equation 9 involves finding the candidate translation that minimizes:

[0057]

\begin{matrix} \frac{1}{s} \sum_{i = 1}^{s} (- α \log P (\tilde{c}) - \sum_{c \in C} f_{Ei} (c) \log P (c | \tilde{c})) & Eq . 12 \end{matrix}

where a separate translation frequency vector f_Ei(c) is provided for each context length by repeating the EM training for each context length separately.

[0058] In other embodiments, the best candidate translation is selected at step 210 by creating TF-IDF vectors (Term Frequency/Inverse Document Frequency Vectors) based on the translation frequency vector and the target frequency vectors and comparing the TF-IDF vectors to find the TF-IDF target frequency vector that best matches the TF-IDF translation frequency vector.

[0059] Under such an embodiment, selection module 320 constructs the TF-IDF vectors by first determining an inverse document frequency value (idf(c)) for each word in the target language using:
idf(c)=−log(df(c)/F) Eq. 13
where df(c) is the document frequency of target word c and F is the total document frequency.

[0060] Using the inverse document frequency values, the translation frequency vector becomes:
A=(f_E(c₁)idf(c₁),f_E(c₂)idf(c₂), . . . ,f_E(c_n)idf(c_n)) Eq. 14
and the target frequency vector for candidate {tilde over (c)} becomes:
B=(f(c₁)idf(c₁),f(c₂)idf(c₂), . . . , f(c_n)idf(c_n)) Eq. 15

[0061] where terms such as f(c₁)idf(c₁) indicate the product of f(c₁) and idf(c₁).

[0062] With the TF-IDF vectors defined, the candidate translation is selected by selecting the candidate translation that maximizes the cosine of the angle between the two vectors. In other words, the candidate is selected by selecting the candidate with the maximum value for tfidf({tilde over (c)}), defined as:

[0063]

\begin{matrix} tfidf (c) = \cos (A, B) where & Eq . 16 \\ \cos (A, B) = \frac{a_{1} b_{1} + a_{2} b_{2} + \dots + a_{n} b_{n}}{\sqrt{a_{1}^{2} + a_{2}^{2} \dots + a_{n}^{2}} \cdot \sqrt{b_{1}^{2} + b_{2}^{2} \dots + b_{n}^{2}}} & Eq . 17 \end{matrix}

[0064] In a further embodiment of the present invention, the EM algorithm forms part of a back-off technique. Under this embodiment, the target corpus is searched to find the source phrase. If the source phrase is found, the target words preceding the source phrase are used as the translation of the source phrase. If the source phrase cannot be found in the target corpus, candidate translation are formed using the compositional technique described above, and the EM algorithm is invoked to select a most likely candidate translation as the translation for the source phrase.

[0065] Note that although the techniques described above are used to find a translation for a source phrase, in other embodiments these techniques are used to find strings of text in a target corpus that match a string of text in a source language. In particular, the techniques described above can be used to locate pages that contain text in the target language that is relevant to a search string in the source language. This is done by converting the search string into a context vector, using the EM algorithm to form a translation context vector, and comparing the translation context vector to target context vectors that are formed from strings in the target corpus.

[0066] A second aspect of the present invention updates a translation dictionary based on feedback from multiple users. A method and system for performing this system are shown in the flow diagram of FIG. 4 and the block diagram of FIG. 5, respectively.

[0067] At step 400 of FIG. 4, one of a plurality of clients such as clients 500, 502, 504, and 506 requests a translation from an extraction server 508 through a network connection such as Internet 510. Extraction server 508 looks for the translation of the source phrase in a translation dictionary 518. If the dictionary does not have a translation for the source phrase, extraction server 508 extracts possible translations from pages connected to the Internet, such as source language pages 512 and target language pages 514, at step 402.

[0068] One technique for extracting the translation includes returning a page identified through a compositional technique as discussed above without performing the EM algorithm to determine if the translation is a best candidate. Alternatively, the translation can be extracted by finding the source language phrase in a target language page as discussed above without performing the EM algorithm to determine if the translation is a best candidate. A further alternative is to perform one of the EM-based algorithms discussed above to identify a most likely translation candidate.

[0069] As part of step 402, the extracted translation candidate and the page that it appears on are returned to the client that requested the translation. Under one embodiment, this information is returned as a web page such as the web page of FIG. 6. In FIG. 6, the word to be translated is input in an input box 600 by a user who has found the word in a Web Page 600 and wants its translation. A list of translations has been returned to the user. This list includes candidate translations 604, 606, and 608. The candidate translations are accompanied by links 610, 612, and 614, respectively, which provide links to web pages where the translation was found. This allows the user to view the candidate translation in a context so that they can make a more informed decision when selecting one of the candidate translations.

[0070] At step 404, the user at the client reviews the translations and the pages that the translations are found on and votes as to whether the translation is correct. To vote for a candidate translation, the user marks one of the check boxes 616, 618, or 620, next to the correct translation. The client sends this user vote back to a dictionary update server 516 at step 406. Optionally, the client also updates a local translation dictionary stored on the client based on the user's selection.

[0071] Note that although dictionary update server 516 is shown as a separate server from extraction server 508 in FIG. 5, the functions of these two servers may be combined in a single server under some embodiments of the present invention.

[0072] Dictionary update server 516 stores the vote at step 408 and at step 410 determines if the candidate translation has received enough votes to qualify for placement in translation dictionary 518. If dictionary update server 516 has not received enough votes at step 410, it returns to step 400 and waits for another client request for a translation of the source phrase.

[0073] After dictionary update server 516 has received enough votes at step 410, it places the candidate translation in translation dictionary 518 at step 412.

[0074] Thus, the invention of FIGS. 4 and 5 use feedback from multiple users to select between candidate translations that are extracted from pages on a network such as the Internet. This automates the incremental updating of the translation dictionary without requiring a single user to be responsible for making decisions between candidate translations. This is thought to provide more robust translation selection and better dictionary updates. Note that in some embodiments, users are prevented from entering multiple votes for a translation. This is done to help prevent malicious attacks on the translation dictionary.

[0075] Although the present invention has been described with reference to particular embodiments, workers skilled in the art will recognize that changes may be made in form and detail without departing from the spirit and scope of the invention.

Claims

What is claimed is:

1. A method of identifying a translation in a target language for at least one source word in a source language, the method comprising:

transforming a representation of context words in the source language into a transformed representation of context words in the target language based in part on multiple different translations for at least one context word in the target language;

determining candidate representations of context words for at least two candidate translations in the target language;

using the transformed representation to score each candidate representation; and

selecting a candidate translation based on the scores for the candidate representations.

2. The method of claim 1 wherein the representation of context words in the source language comprises a frequency vector wherein each element in the frequency vector comprises a count of the number of times a respective word in the source language appears as a context word for the at least one source word.

3. The method of claim 2 wherein transforming the representation of context words in the source language comprises using a probability of a word in the target language.

4. The method of claim 3 wherein the probability of the word in the target language is trained using an iterative algorithm.

5. The method of claim 4 wherein the iterative algorithm utilizes a probability that is based in part on entries in a translation dictionary.

6. The method of claim 4 wherein the iterative algorithm comprises an expectation-maximization algorithm.

7. The method of claim 3 wherein transforming the representation of context words in the source language comprises forming a frequency vector as the transformed representation.

8. The method of claim 3 wherein transforming the representation of context words in the source language comprises forming a term frequency-inverse document frequency vector.

9. The method of claim 8 wherein each candidate representation comprises a term frequency-inverse document frequency vector.

10. The method of claim 1 wherein the transformed representation comprises a vector and each candidate representation comprises a vector and using the transformed representation to score each candidate representation comprises determining the cosine of the angle between the transformed representation vector and each candidate representation vector.

11. The method of claim 1 wherein using the transformed representation to score each candidate representation comprises determining a score using a function that is based on the transformed representation and the candidate representation.

12. The method of claim 11 wherein the candidate representation comprises a probability of a context word in the target language given a candidate translation.

13. A computer-readable storage medium having computer-executable instructions for performing steps comprising:

receiving a string of words in a source language wherein receiving a string of words comprises identifying multiple strings of words, each string representing a context for a word in the source language;

transforming the string of words into a transformed representation using an iterative algorithm;

using the transformed representation to score strings of words in the target language.

14. The computer-readable storage medium of claim 13 further comprising selecting a string of words in the target language based on the score.

15. The computer-readable storage medium of claim 14 further comprising identifying pages containing the selected string of words in the target language as relevant to the string of words in the source language.

16. The computer-readable storage medium of claim 13 wherein transforming the string of words comprises forming a frequency vector from the strings of words and transforming the frequency vector into a transformed frequency vector.

17. The computer-readable storage medium of claim 16 wherein using the transformed representation to score a string of words in the target language comprises determining a probability for each word in the string of words in the target language and using the probabilities for the words and the transformed frequency vector to score the string of words in the target language.

18. The computer-readable storage medium of claim 16 wherein using the transformed representation to score a string of words in the target language comprises forming a target frequency vector based on the string of words and using the target frequency vector and the transformed frequency vector to score the string of words.

19. The computer-readable storage medium of claim 18 wherein using the transformed representation to score a string of words in the target language comprises forming a single score for multiple strings of words in the target language.

20. The computer-readable storage medium of claim 16 wherein transforming the string of words further comprises forming a transformed term frequency-inverse document frequency vector based in part on the frequency vector.

21. The computer-readable storage medium of claim 20 wherein using the transformed representation to score a string of words in the target language comprises forming a target term frequency-inverse document frequency vector based in part on the string of words and using the transformed term frequency-inverse document frequency vector and the target term frequency-inverse document frequency vector to score the string of words.

22. The computer-readable storage medium of claim 13 wherein the iterative algorithm is an expectation-maximization algorithm.

23. A method of updating a translation dictionary, the method comprising:

providing two possible translations for a word to at least two clients;

receiving an indication from each of the clients as to which translation was deemed correct;

using the indications from the clients to select one of the translations for entry in a translation dictionary.

24. The method of claim 23 wherein providing a possible translation comprises examining a page on a network to find a possible translation for a word.

25. The method of claim 24 further comprising providing a link to a page containing the possible translation along with the possible translation.

26. The method of claim 23 wherein providing the at least two possible translations to a client further comprises receiving a request from the client for a translation of a word before providing the at least two possible translations.

27. The method of claim 23 wherein using an indication from the client to select at least one translation comprises determining if a translation was deemed correct more than a threshold number of times.

28. The method of claim 23 further comprising not using an indication from a client to select a translation if the client has provided more than a threshold number of indications for a translation.

29. A computer-readable storage medium having computer-executable instructions for performing steps comprising:

serving a page to a client to solicit a source phrase from the client;

receiving the source phrase from the client;

accessing pages though a network to identify translations for the source phrase;

returning a page comprising a plurality of candidate translations for the source phrase and for each candidate translation, a page identifier that identifies the page that contains the translation to the client;

receiving an indication that one of the plurality of candidate translations has been selected on the client as a proper translation of the source phrase; and

using the indication to determine whether to add the selected translation to a translation dictionary accessed by a server.

30. The computer-readable storage medium of claim 29 further comprising updating a translation dictionary used by the client based on the selected translation.

31. The computer-readable storage medium of claim 29 wherein accessing pages through a network comprises accessing web pages through the Internet.

32. The computer-readable storage medium of claim 31 wherein the page identifier is a link to a web page that contains the translations.

33. The computer-readable storage medium of claim 29 further comprising receiving the source phrase form multiple clients, returning at least two candidate translations to each client, receiving an indication as to whether the client accepts a candidate translation as a proper translation from multiple clients, and using the multiple indications to determine whether to add a translation to a translation dictionary.

Patent Citations (10)

Patent	Date	Inventor	Cited By
US6119078(A)	2000-09-01	Kobayakawa et al.	Examiner
US6598015(B1)	2003-07-01	Peterson et al.	Examiner
US6857022(B1)	2005-02-01	Scanlan	Examiner
US6885985(B2)	2005-04-01	Hull	Examiner
US7103531(B2)	2006-09-01	Moore	Examiner
US7107204(B1)	2006-09-01	Liu et al.	Examiner
US2001/0029455(A1)	2001-10-01	Chin et al.	Examiner
US2002/0138250(A1)	2002-09-01	Okura et al.	Examiner
US2002/0161569(A1)	2002-10-01	Itoh et al.	Examiner
US2003/0009320(A1)	2003-01-01	Furuta	Examiner

Non-Patent Literature (18)

Cao et al., “Base Noun Phrase translation using web data and the EM algorithm”, Proceedings of the 19th international conference on Computational linguistics, vol. 1, pp. 1-7, 2002.Examiner
Brill E., Lin J., Banko M., Dumais S. and Ng A. (2001) Data-Intensive Questions Answering. In Proc. of TREC '2001.Applicant
Brown P.F., Della Pietra, S.A., Della Pietra V.J., and Mercer, R.L. (1993) The mathematics of Statistical Machine Translation: parameter Estimation. Computational Linguistics 19(2), pp. 263-311.Applicant
Diab M. Finch S. (2000) A Statistical word-level translation model for comparable corpora. In Proc. of RIAO.Applicant
Fujii A. and Ishikawa T. (2000). Utilizing the World Wide Web as an Encyclopedia: Extracting Term Descriptions from Semi-Structured Texts. In Proc. of ACL '2000, pp. 488-495.Applicant
Fung P. and Yee L.Y. (1998) An IR approach for translation new words from nonparallel, comparable texts. In Proc. of COLING-ACL '1998, pp. 414-420.Applicant
Gao J.F., Nie J.Y., Xun E.D., Zhang J., Zhou M. and Huang C.N. (2001) Improving Query Translation for Cross-Language Information Retrieval Using Statistical Models. In Proc. of SIGIR '2001.Applicant
Koehn P. and Knight K. (2000) Estimating word translation probabilities from unrelated monolingual corpra using the EM algorithm. In Proc. of AAAI '2000.Applicant
Nagata M., Saito T., and Suzuki K. (2001) Using the Web as a bilingual dictionary. In Proc. of ACL '2001 DD-MT Workshop.Applicant
Nakagawa H. (2001) Disambiguation of single noun translations extracted from bilingual comparable corpora. In Terminology 7:1.Applicant
Nie J.Y., Simard M., Isabelle P. and Durand R. (1999) Cross-Language Information Retrieval based on Parallel Texts and Automatic Mining of Parallel Texts in the Web. In Proc. of SIGIR '1999.Applicant
Rapp R. (1999) Automatic identification of word translations from unrelated English and German corpora. IN Proc of ACL '1999.Applicant
Resnik P. (1999) Mining the Web for Bilingual Text. In Proc. of ACL '1999.Applicant
Sumita E. (2000) Lexical transfer using a vector-space model. In Proc of ACL '2000.Applicant
Tanaka K. and Iwasaki H. (1996) Extraction of Lexical Translation from non-aligned corpra. In Proc. of COLING '1996.Applicant
Wang, Y. and Waibel, A. (1998) Modeling with Structures in Statistical Machine Translation. In Proc. of COLING-ACL '1998.Applicant
Xun E.D., Huang C.N. and Zhou M. (2000) A Unified Statistical Model for the Identification of English BaseNP. In Proc. of ACL '2000.Applicant
Xu, J. and R. Weischedel, Cross-lingual Information Retrieval using Hidden Markov Models, In the Proc. of the Joint SIGDAT conference on EMNLP/VLC-2000, 2000.Applicant