3
$\begingroup$

Suppose that you have a large dictionary with spellings and pronounciations of foreign words, and you want to find a set of pronunciation rules. They should have the simplest form: a sequence of letters to a sequence of sounds.

For example, in French, c [k], i [i] and ci [si].

  1. The rules may be long: tion [sjɔ̃] (instead of [tjɔ̃]).

  2. They may be rare: à [a] is used only in a dozen of words.

  3. They may be both: aill [aj] (as a-ill, instead of ai-ll [ɛl]).

Fortunately, such rules are rare enough: for the most part, the letters are pronounced by itself, even most of them in complicated rules. For examples, cercle [sɛʀkl] instead of [kɛʀklɛ]: the algorithm should notice the corresponding sounds in the middle of the word.

Maybe, there is a standard algorithm to extract candidates for such rules? I would like to have an explicit list of rules, rather than a method predicting pronunciation.

$\endgroup$
  • $\begingroup$ In fact, in French orthography, c has the sound [s] before both e and i, and in most case final e is elided. So your example of cercle is completely regular. On the other hand, you seem to be ignoring vowel quality and nasality. $\endgroup$ – Yuval Filmus Mar 21 '16 at 16:08
  • $\begingroup$ @Yuval Filmus, yes, I consider ce [s e] and e$ [] exactly as the rules to find. $\endgroup$ – se0808 Mar 21 '16 at 16:18
  • 1
    $\begingroup$ What algorithms from the fields of NLP and machine learning have you tried? Where did you get stuck? This is a very broad quesiton, and I feel like you could have done more to narrow things down. $\endgroup$ – Raphael Mar 22 '16 at 8:26
2
$\begingroup$

Broadly, I can see two possible approaches: machine learning, or data mining

Machine learning

You could look into using machine learning to learn a transducer that transforms the input sequence (the letters in the word) to the output sequence (the pronunciation). This approach doesn't try to find an explicit set of rules; it just tries to find a method that is effective in practice at producing the right pronunciation.

You could try training a recurrent neural network (RNN), and/or a LSTM network. LSTM's have been effective at related tasks, and since you have a large training set, they might possibly be effective here. Bi-directional RNN's/LSTM's might be worth exploring.

Data mining

Alternatively, you could use data mining techniques to try to find an explicit set of rules that seem to have good support among your dictionary.

This problem fits into the general area of sequence mining (also known as sequential pattern mining) and association rule learning. I think it might be fruitful to try applying one of the algorithms from that field, to your problem.

In your case, you could consider each possible substring of the word or pronunciation to be a possible item, and your goal is to find rules of the form $x \Rightarrow y$, where $x$ is a substring of the word and $y$ is a substring of the pronunciation. This is a special case of itemset mining, where your itemsets are restricted to have size 1. You could then adapt any standard itemset algorithm (e.g., Apriori, FP-growth) to this problem.

For instance, here is an adaptation of Apriori. You consider all possible rules of the form $x \Rightarrow y$, where $x$ and $y$ are length 1. For each, you compute their support or some probabilistic measure of the strength of the association (e.g., out of all words that contain $x$, what fraction contain $y$?). Discard all candidate rules for which this metric is below some threshold. Then, try all extensions of this rule by extending either $x$ or $y$ by one character to the left or right side of it; this gives you a bunch more candidates. For each such candidate, compute the metric and discard those that are below the threshold. Keep expanding your set of candidates until no new candidates can be identified. This is basically a form of "breadth-first search". Finally, at the end, prune your rules by eliminating rules with a containment relationship (e.g., if you have a rule $x \Rightarrow y$, then you might want to remove all other rules of the form $x' \Rightarrow y'$ where $x'$ is a substring of $x$ and $y'$ is a substring of $y$).

You could also consider similar tweaks to FP-growth.

However, it's not clear to me how well a data mining-based approach will work: while it does consider order to some extent, it doesn't take into account the position within the word, and it doesn't consider whether a set of rules fully covers all of the characters in the word, and it doesn't take into account rule overlap (e.g., $x_1 \Rightarrow y_1$ and $x_2 \Rightarrow y_2$ where $x_1,x_2$ overlap partially).

$\endgroup$
  • $\begingroup$ thank you! Your answer, particularly about Apriori, is wonderful. $\endgroup$ – se0808 Mar 22 '16 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.