FR2842923A1 - GENERATOR OF A DOMAIN-SPECIFIC CORPUS - Google Patents

Abstract

The product / program and the method according to the invention make it possible to generate a corpus of texts specific to a field of application from a general corpus and a grammar of the field. Thus a specific corpus can be created automatically without interaction with the user.

Description

i

  Generator of a corpus specific to a domain.

  The present invention belongs to the field of automatic processing of natural language. More specifically, it addresses the problem of generating a specific set of texts for a domain

  application or specific corpus.

  Specific corpora are needed, especially in computer speech recognition systems to achieve a recognition rate acceptable to the user. This is particularly necessary for large vocabulary systems (typically 20,000 words). The generation of a specific corpus is a treatment that still requires in the state of the art long progressive learning operations based on a selection of the texts of a corpus of a domain

  given from the sentences entered by the user.

  A selection method based on a probabilistic model has been

  disclosed in particular in US Patent 5,444,617.

  This method has the disadvantage of requiring

  long and expensive user interactions.

  The present invention overcomes this disadvantage by allowing the user to formulate a specification of the specific corpus in the form of a grammar, or set of syntax rules, specific to the application domain, the generation of the specific corpus of the domain being then automatic. The invention thus significantly reduces the time required

  to the collection of the specific corpus.

  For this purpose, the invention proposes a product / program and a method for collecting a set of texts specific to a field of application from a set of non-specific texts, characterized in that it comprises a command module by a grammar of the

application domain.

  The invention will be better understood on examining the following figures

  whose content is explained in the body of the description:

  Figure 1: Diagram showing the modules of the product / program

according to the invention.

  Figure 2: Diagram showing an example of generation of ngrams of a specific grammar of an application domain.

  Figure 3: Diagram explaining an algorithm for calculating

  distances between words according to the invention.

  Figure 4: Example of calculating the distances between words according to the invention.

  Figure 5: Example of semantic calculation.

  Figure 6: Graph showing the distribution of n-grams in

  distance function to grammar vocabulary words.

  Figure 1 shows the sequence of modules and treatments according to the invention. The definitions of the figure are as follows: The general corpus 10 is a set of texts, commercially available, nonspecific domain, which may include several million texts. n-gram [VcORpusj 13 is a set of sequences of ordered words extracted from the general corpus or n-tuples, said words being present in the vocabulary. The manner in which these n-grams are formed is described below. The vocabulary of this corpus VCORPUS 11 is the set of words most frequently encountered in this corpus or set of unigrams. The vocabulary is generally limited to 20,000 words. The AEF generator 20 is a module that makes it possible to generate the n-grams of a domain A grammar from said grammar, in a manner

  also explained in the following description. A set ngram [VcFG (A)] 33 is generated from the CFG (A) grammar of a

  explained in the following description. The specific corpus of A,

  CORPUS (A) 40 is initialized with n-grams VCFG (A) 33. CORPUS (A) 40 is recurrently added to the n-grams of VCORPUS 13 which satisfy the condition:

  3 n-gram [VcFG (A)]: D (n-gram [VcoRpus], n-gram [VCFG (A)]) <6.

  Several distance functions D can be used as explained in the rest of the description. 6 is the distance threshold that must be set

  in order to optimize the constitution of CORPUS (A) 40 for domain A specific recognition applications. Typically, the n-grams of VCORPUS13 will be bi grams or trigrams. A bigram is a set of two words that belong to the vocabulary VcoRpusl 1 with which their probabilities of occurrence are associated in the general corpus 10. The trigrams are sets of three words in the order in which they occur in the corpus general 10 to which are

  associated their probabilities of occurrence in the general corpus 10.

  To generate n-gram [VcoRpus] one can use tools of the trade generally denominated under the generic name of tools of generation of statistical model of language. One can for example use the one developed by Carnegie Mellon University described by Philippe Clarkson and Ronald Rosenfeld in a publication of Rosenfeld University [Rosenfeld 95], The CMU Statistical Language Modeling Toolkit and its use,

  ARPA Spoken Language Technology Workshop, Austin Texas (USA) pp. 4550, 1995. This article is incorporated by reference into this specification. The

  most statistical language models, and in particular the one described in the article under reference, correct the probabilities of the lowest occurrences so as to eliminate the bias that is conventional in this type of statistical analysis. The least observed n-grams have indeed a probability of occurrence biased downwards and most observed a

  probability of occurrence biased upwards.

  The CFG grammar (A) 30 is a context-independent grammar, which means that variations of the context do not alter the grammar itself. This grammar is, in the state of the art, constituted manually. N-gram [VcFG (A)] 33 will typically be tri grams or quad grams. They are created by the AEF generator 20, an example of which is described in FIG. 2. The generation of the n-grams of CFG (A) follows as follows: - creation of the corresponding deterministic automaton (we do not take into account the probabilities). (Summit = state, Transition = terminal symbol); - we select all the consecutive n-arcs belonging to this automaton, ie the following CFG: GRAMMAR = unit (alpha OR bravo) (join OR (go to) the unit (alpha OR bravo) The vocabulary is thus VCFG = (unit , alpha, bravo, join,

go to, the unit).

We notice that | I = 6

  We obtain the deterministic finite automaton represented in FIG.

The unigrams are:

  unity, alpha, bravo, join, go to, the unit (we fall on VCFG).

  The bigrams are: alpha unit, bravo unit, alpha join, alpha go to, bravo join, bravo go to, join the unit, go to the unit, the alpha unit, the unit bravo. There are 10, that is, much less than I VCGF 12 = 36 The trigrams are: unit alpha join, unit alpha go to, unit bravo join, unit bravo go to, alpha join the unit, alpha go to the unit, bravo join the unit, bravo go to the unit, join the alpha unit, join

  bravo unit, go to the alpha unit, go to the bravo unit.

  There are 12, that is, much less than IVCGF 3 = 216 Although in theory, the number of n-grams can reach

  IVCGF n, it is actually much smaller than that (a few thousand grams for a grammar whose vocabulary reaches 200 words).

  The vocabulary VCFG (A) 31 is the set of uni grams.

  FIG. 3 illustrates the operation of the algorithm for calculating the distance between two words of a dictionary. In the application we use the

  three dictionaries 10, 12 and 32 of FIG.

  The dictionary dico-VcoRpus 12 and dico-VCFG (A) 32 are dictionaries extracted from a general dictionary 1 Oa which is a component that

it is found in commerce.

  This general dictionary provides information to inflected forms of words, such as pronunciation, the root word. We can also add semantic information that can be represented under

  form of graphs or conceptual vectors.

  This algorithm consists of three steps: - letter-to-letter distance calculation, which uses the edit distance algorithm and the ins-del-sub parameters; - The calculation of distance between any two words, which will weight according to the length of the transformed word; - The calculation of distance between two words of the dictionary that will

  take into account the type and meaning of words.

  The notation is as follows: ## EQU1 ## The number of letters of a C empty word Div full division operator One of the methods for calculating the distances between two words is described in the works accessible to a person skilled in the art under the name of distance. edition (or of Levenstein or Wagner-Fisher) [Wagner & Fisher, 1974] Wagner, RA & Fisher, MJ (1974). The string-to-string correction problem. Journal of the Association for Computing Machinery, 21 (1), 168-173. [Amengual & Vidai, 1998] Amengual, J.-C. & Vidal, E. Efficient error-correcting viterbi parsing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20 (10), 1109-1116, 1998. These Articles

  are incorporated by reference in the present application.

  Given two words a and b, the edit distance returns the minimum number of editing operations needed to transform the word a into a word b. These editing operations are usually the insertion of a letter, the deletion of a letter and the substitution of a letter. We can assign a weight to each of these operations. In this case, the editing distance

  will return the minimum total weight that transforms the word a into a word b.

  Let DL (a, b) be the function that returns the editing distance (Levenstein) that transforms a to b. DL admits for parameters the integers Pins, Pdel, Psub (unit distances for each insertion / deletion / substitution). The choices of these parameters are arbitrary at first, it is according to the results that we will be able to refine them, but for example we can take: Pdel = 2, Pins = 3 and Psub = 4. For our application, the distance DQ between any two words must highlight the denaturation of the original word: the importance of the transformation performed can be measured in relation to the size of the original word. Given a word of length n, if k editing operations were performed, then the denaturation of the original word can be estimated at k / n. In the particular case oa is empty (a = E) the computation is carried out as if the length of the empty word was 1. The vocabulary VCFG and VCORPUS being finished, the length of the longest word is given by the formula: DQ ( a, b) = (K * DL (a, b)) div lai sia! E 0 and Do (a, b) = DL (F, b) sia! = 0 o K = max ({al / aa VCFG}, {l bl / b Y VCORPUS}) It is now desirable to calculate the distance D between two words of the dictionary to correct the editing distance of a factor taking into account of their etymological and semantic distance. In order not to degrade the speed of execution of the treatment, a simplified indicator of this proximity is advantageously chosen, as described below. Let D max be the maximum distance between any two words. Let E be VCFG (A) and b E VcoRpus the two words which one wants

measure the distance.

  D (a, b) = C + DQ (a, b) If a and b have the same root, DO = 0 If a and b have the same meaning, Do = DOmax If a and b belong to the CFG vocabulary, Do = 2 * DQmax Otherwise, Do = 3 * DQmax Any distance calculation function between a and b can be used. It is however preferable that the function D be continuous with

  pieces and growing according to DQ.

  An example of execution of the algorithm of

calculating the distance between words.

  Take Pins = Pdel = Psub = 1 Let VCFG be defined by: VCFG = {g, "unit", "display"} Let Vcorpus be defined by VCORPUS = {ú, "show", <"horse>" K = 8 length of the word longest: "display" So the expression of the distance between two words of the dictionary becomes Do (a, b) = 8 * DL (a, b) div I to I 8 * DL (E, b) if a! = 0 otherwise DQmax = 8 * 1 = 8 D (ú, e) = OD (ú ,, <show, ") = Do = 24 Do (z ,, unit,) = 7 D (ú," unit ") = 24 + 7 = 31 D (ú <, "horse") =

DO = 24

  DQ (F, "horse") = 6 D (ú, "horse") = 24 + 6 = 30 D ("unit", ú) = Do = 24 Do ("<unit>", F) = (5 * 8) div 5 = 8 D ("unit", E) = 24 + 8 = 32 D ("unit", <"show") = Do = 3 * Domax = 24 DQ ("<unit", "show" ) = (6 * 8) div 5 = 9 because ("unit" -> <"munity - >> <" monity "->" shown "-> <" shows "-," <show "= 6) D ( "c unit", "<show") = 24 + 9 = 33 "<mounted" -> D "<unit", <c horse ") = Do = 3 * DQmax = 24 DQ (<c unit", " horse ") = (6 * 8) div 5 = 9 because (" <unit "->" cnity "- >>" chité "->" cheté "-," chevé "- *" cheva "-> < c horse "= 6) D (" unit>, <"horse,) = 24 + 9 = 33 D (" display ",) =

DO = 24

  DQ ("display>",) = (8 * 8) div 8 = 8 D ("display", g) = 24 + 8 = 32 D ("display", "show") = Do = Damax = 8 DQ ( ", show", "show") = (6 * 8) div 8 = 6 Car (", display" -> "display> -> <moficher>, -> <" monicher "- '<" mount "- > "<show, -" -> show> = 6) D ("show ,," show ") = 8 + 6 = 14 D (" show "," horse ") = DO = 3 * DQmax = 24 DQ ( "display", "horse") = (7 * 8) div 8 = 7 car ("<display" -> "ffile" >> "file" -> "icher" -> "expensive" - @ "chev "->" cheva "- *" horse "= 7) D (" <display ,, "horse") = 24 + 7 = 31 The table of unit distances resulting from calculations is given

figure 4.

  Note that the lowest distance (except for empty words) is that for the couple (display, show). It is indeed easier to insert than to delete: the deletion leads to the loss of information, while

  that the insertion adds noise in the information.

  In an alternative embodiment, it is possible to have a finer division in the sense by considering several levels of different semantics (through a classification). For example: color, red, and green are neighbors, but red and green are closer

between them only with color.

  Semantic computation is done from semantic dictionaries.

  There are several forms of semantic discourse, two of which

  particular: those based on graphs, and those based on vectors.

  On the example of the colors, if the semantic dictionary is a graph, one can obtain the diagram of figure 5; To calculate the distance, we can use the following convention - two brothers have a distance of 1 a father and a son have a distance of 2 For example, the distance between colors and red is 2. That

between red and green is 1.

  However, the distance between red and dog is 5, as

illustrated figure 5b.

  When it comes to conceptual vectors, the distance comes down to a scalar product. As far as we are concerned, it is the very close distances between the words (from a certain distance, we are no longer interested in the value). Therefore, in the invention we will consider the semantic distance as being binary (two words are

  1 5 semantically close or not).

  The distances are integer values, which makes it easier to create analysis tables that will make it possible to choose

the threshold.

  Using this algorithm for calculating distances between words (or unit distances), it is possible to calculate D (a, b) for any word a and all

  word b respectively belonging to VCORPUS and VCFG (A).

  It is now necessary to deduce from this first matrix a second matrix of distances between the n-grams (x;) 'of VcoRpus and the mgrams (y,)' of VCFG (A). It is advantageous to use an algorithm known to those skilled in the art described in [Chodorowski, 2001] Chodorowski, J. Inference grammatical for the learning of syntax in speech recognition and oral dialogue. Thesis, University

  de Rennes 1, 2001, page 50 which is incorporated by reference in the present description. We seek to calculate the element M (n, m) of this second matrix which is the distance between the n-gram (x *); and the gram (yj) rn.

  The algorithm described in the above reference computes M (n, m) by a dynamic programming recursion defined as follows

M (0,0) = 0

  M (i, 0) = Y, '= D (xk, c) for 1 <i <m, where xk is the kth word of i-gram M (i, 0) = D, D (E, Yk) for 1 <j <n M (i - 1, j) + D (xi, e) M (i, j) = min M (ij, j - 1) + D (e, y1) M (i - 1, j) + D (xi, yj) The distance between two n-grams uses the Levenstein distance between two sequences, but this time at the sentence level. The work is exactly the same: the distance between any two words being known, we apply this measure of distance as if the words

were mere symbols.

Example:

  Distance between <alpha unit go to "and" alpha unit go ahead

towards ".

  1 5 M1 = unit M2 = alpha M3 = go M4 = to M5 = move forward The distance between these two sentences is equal to the distance between the sequences M1M2M3M4 and M1M2M3M5, given the matrix of

  unit distance D (Mi, Mj) calculated previously.

  The number of computations for each element M (n, m) is therefore of the order of nxm, ie of 12 in the case of a privileged mode of realization on = 3 and m = 4. It will be noted that the computations of rank lower in recurrence

  allow to fill other spaces of the matrix of the distances between ngram and m-grams.

  However, of course, other algorithms for calculating

  distances between n-grams and m-grams may be chosen.

  The threshold δ of distance below which the n-grams of the general corpus whose distance to m-grams of VCFG (A) are added to CORPUS

  (A), this being initialized initially by VCFG (A).

  The numerical analysis of the matrix of M (n, m) makes it possible to plot a graph of the frequencies of n-grams according to the

  distance to words and VCFG (A) (Figure 6).

  Some iterations will be useful to adjust 8.

  It is possible to implement the invention on a commercial computer of any type provided with conventional interfaces for inputting and restoring data (keyboard, mouse, screen, printer). Integration with a voice recognition system is possible on a common configuration. In this case, the computer system also has a microphone, loudspeakers, a specialized

  signal processing and specialized speech recognition software.

Claims (22)

  A product / program for collecting a set of texts (40) specific to a field of application (to) from a non-specific text set (10), characterized in that it comprises a module of command by a grammar (30) of the application domain (to). 2. Product / program according to claim 1, characterized in that the control module comprises a distance measuring module D between sentences of the set of non-specific texts and sentences of   the grammar of the application domain.   3. Product / program according to claim 2, characterized in that the control module comprises an adjustable value δ threshold of distance between sentences.   4. Product / program according to one of claims 2 or 3,   characterized in that the distance measuring module calculates the distance D between a sentence of n words and a sentence of m words recursively   from a measure of the distance between words.   5. Product / program according to claim 4, characterized in that for i and j 'respectively varying from 1 to n and 1 to m, an element of rank (i, j) in the recurrence is the minimum of the sum of l element of rank (i 1, j) and of the distance between the word of rank i of the first sentence and the word "space", of the sum of the element of rank (i, j - 1) and the distance between the word "space" and the word of rank j of the second sentence and the sum of the rank element (i - 1, j - 1) and the distance between the word of rank   i of the first sentence and the word of rank j of the second sentence.   6. Product / program according to claim 4, characterized in that, for i and j respectively varying from 1 to n and from 1 to m, elements of rank (i, o) or (o, j) in the recurrence are each the sum for k variant   from 1 to i distances between the word of rank k and the word "space".   Product / program according to claim 4, characterized in that   that, the element of rank (o, o) in the recurrence is equal to o.   8. Product / program according to one of claims 4 to 7,   characterized in that the distance between words is a decreasing function of their etymological and semantic and increasing proximity to a measure of the   letter-to-letter transformation of one of the two words in the other.   9. Product / program according to one of claims 1 to 8,   characterized in that the n-grams of the application domain-specific grammar (33) are generated by a module (20) where the parameter user   a deterministic finite state automaton.   10. Speech recognition system including a   product / program according to one of claims 1 to 9.   11. Information processing system comprising a module   according to one of claims 1 to 10.   12. A method of collecting a set of texts specific to an application domain A from a set of non-specific texts (10), characterized in that the collection is controlled by a grammar of the field of application D (30).   13. The method of claim 12, characterized in that the command comprises a measure of distance D between sentences of the non-specific text set and sentences of the grammar of the application domain.   14. The method according to claim 13, characterized in that the control comprises an adjustable value of the distance threshold between sentences.   15. Method according to one of claims 13 or 14, characterized   in that the measure of distance between a sentence of n words and a sentence of m words is calculated recurrently from a measurement of the distance between words.   16. Method according to claim 15, characterized in that for i and j 'respectively varying from 1 to n and 1 to m, an element of rank (i, j) in the recurrence is the minimum of the sum of the element of rank (i-1, j) and the distance between the word of rank i of the first sentence and the word "space", the sum of the rank element (i, j-1) and the distance between the word "space" and the word of rank j of the second sentence and the sum of the rank element (i - 1, j - 1) and the distance between the word of rank i of the   first sentence and the word of rank j of the second sentence.   17. Method according to claim 15, characterized in that, for i and j respectively varying from 1 to n and from 1 to m, elements of rank (i, o) or (o, j) in the recurrence are each the sum for k varying from 1 to i of   distances between the word of rank k and the word "space".   18. Process according to claim 15, characterized in that,   the element of rank (o, o) in the recurrence is equal to o.   19. Process according to one of Claims 15 to 18, characterized in   that the distance between words is a decreasing function of their etymological and semantic and increasing proximity to a measure of the cost of   letter-by-letter transformation of one of the two words into the other.   20. Method according to one of claims 12 to 19, characterized in   the n-grams of the specific grammar of the application domain (33) are generated by a module (20) where the user sets an automaton deterministic finite states.   21. Speech recognition method implementing a   process according to one of claims 12 to 20.   1 5 22. An information processing method implementing a   Method according to one of Claims 12 to 21.