Réaccentuation automatique de textes français Automatic Restoration of Accents in French Text

Michel Simard

Michel Simard

simard@citi.doc.ca

simard@citi.doc.ca

Industrie Canada Centre d'Innovation en Technologies de l'Information 1575 Chomedey Laval (Québec) CANADA H7V 2X2

Industry Canada Centre for Information Technology Innovation (CITI) 1575 Chomedey Blvd. Laval, Quebec Canada H7V 2X2

1 Introduction

1 Introduction

Les travaux présentés ici s'inscrivent dans le cadre du projet Robustesse, mené par l'équipe de traduction assistée par ordinateur (TAO) du CITI. Ce projet vise à élaborer des méthodes et des outils de traitement des langues naturelles robustes : plusieurs systèmes de TALN vont soit refuser de traiter des textes comportant des erreurs ou des phénomènes étrangers à leur propre ensemble de connaissances, soit afficher un comportement imprévisible dans ces circonstances. À l'opposé, un système robuste se comportera alors de façon prévisible et utile.

The research presented in this report is part of the Robustness Project conducted by the Computer- Aided Translation (CAT) team at CITI. This project is intended to develop methods and tools for the "robust" processing of natural languages: many natural-language processing (NLP) systems either refuse to process texts that contain errors or elements that are foreign to their particular knowledge base, or behave unpredictably under such circumstances. In contrast, a "robust" system will behave in a predictable and useful manner.

Les textes français sans accents (marques diacritiques) constituent un exemple typique et particulièrement répandu des problèmes auxquels font face les systèmes de TALN. C'est dans le contexte du courrier électronique (e-mail) qu'on rencontre le plus souvent ce phénomène, qui s'explique de deux façons. Premièrement, le monde de l'informatique a longtemps souffert de l'absence d'une norme suffisamment répandue pour l'encodage des caractères accentués, ce qui a entraîné toute une panoplie de problèmes de transfert et de traitement des texte français. Il n'est d'ailleurs pas rare qu'un des maillons logiciels dans la chaîne de distribution du courrier électronique "désaccentue" délibérément les caractères accentués, afin de prévenir d'éventuels problèmes. Deuxièmement, la saisie au clavier des caractères accentués demeure, encore à ce jour, un exercice ardu, voire acrobatique dans certains cas : ici, il s'agit à la fois d'une question de norme et d'une question d'ergonomie. Le résultat concret, c'est qu'un très grand nombre d'utilisateurs francophones évite systématiquement d'utiliser les caractères accentués, tout du moins pour le courrier électronique.

Unaccented French texts (i.e., texts without diacritics) are a typical and particularly common example of problems faced by NLP systems. Such problems are most often encountered in an E-mail context. Two factors account for this: First, the computer field has long suffered from a lack of sufficiently widespread standards for encoding accented characters, which has resulted in a plethora of problems in the electronic transfer and processing of French texts. Moreover, it is not uncommon for one of the software links in an E-mail distribution chain to deliberately remove accents in order to avoid subsequent problems. Secondly, keying in accented characters is still a cumbersome activity, at times requiring manual acrobatics. This is a matter of both standards and ergonomics. As a result, a large number of French-speaking users systematically avoid using accented characters, at least when writing E-mail.

Si cette situation demeure tolérable en pratique, c'est parce qu'il est extrêmement rare que la disparition des accents rende un texte français incompréhensible pour un humain. D'un point de vue linguistique, l'absence d'accents en français ne fait qu'augmenter le degré relatif d'ambiguïté inhérent à la langue. À la limite, elle ralentit la lecture et suscite un certain inconfort, comme peut le faire, par exemple, la lecture d'un texte rédigé entièrement en majuscules.

If this situation remains tolerable in practice, it is essentially because it is extremely rare that the absence of accents renders a French text incomprehensible to the human reader. From a linguistic point of view, the lack of accents in French simply increases the relative degree of ambiguity inherent in the language. At worst, it slows down reading and proves awkward, much as a text written entirely in capital letters might do.

Il n'en demeure pas moins que si le français sans accent est acceptable dans certaines circonstances, il ne l'est pas dans l'usage courant, notamment dans le cas des documents imprimés. Par ailleurs, l'absence des accents pose de sérieux problèmes pour le traitement automatique des textes. Qu'il s'agisse de recherche documentaire, de correction orthographique, grammaticale, stylistique, de traduction automatique, d'interface en langue en naturelle ou de quelqu'autre forme de traitement de la langue, on s'attendra en général à ce que les textes français comportent des accents. D'où l'intérêt pour des méthodes de récupération automatique des accents, ou de réaccentuation automatique.

The fact remains, however, that while unaccented French text may be tolerated under certain circumstances, it is not acceptable in common usage, especially in the case of printed documents. Furthermore, unaccented texts pose serious problems for automatic processing. Whether for purposes of documentary research, spelling, grammar or style checkers, machine translation, natural-language interface, or any other form of language processing, accents are generally required in French texts-hence the interest in methods of automatic accent restoration.

En examinant le problème, on constate que la grande majorité des mots d'un texte français s'écrivent naturellement sans accents (envrion 85%), et que pour plus de la moitié des mots qui restent, la forme accentuée correcte peut être déduite de façon déterministe à partir de la forme sans accent. Il en découle que la simple utilisation d'un bon dictionnaire permet de réaccentuer automatiquement un texte sans accent avec un taux de succès de près de 95% (c'est-à-dire qu'on commettra une erreur d'accent à peu près à tous les vingt mots).

An examination of the problem reveals that the vast majority (approximately 85%) of the words in French texts take no accents, and that the correct form of more than half of the remaining words can be deduced deterministically on the basis of the unaccented form. Consequently, with the use of a good dictionary, accents can be restored to an unaccented text with a success rate of nearly 95% (i.e., an error in accentuation will occur in approximately every 20 words).

Tout porte à croire qu'on peut atteindre des résultats de beaucoup supérieurs grâce à l'utilisation de modèles de langue plus ou moins sophistiqués, qui seront en mesure de lever les ambiguïtés résultant de l'absence d'accents, en se basant sur des considérations d'ordre linguistique. En particulier, il semble que les modèles de langue dits probabilistes soient particulièrement bien adaptés pour ce genre de tâche, parce qu'ils fournissent un critère de désambiguïsation quantitatif : lorsqu'on rencontre une forme sans accent à laquelle peuvent correspondre plusieurs formes valides (portant ou non des accents), on choisit la plus probable, en se basant sur le contexte immédiat et sur un ensemble d'évènements observés antérieurement (le "corpus d'entraînement").

All evidence suggests that much higher results can be attained through the use of moderately sophisticated language models, which will be able to deal with ambiguities resulting from missing accents, on the basis of linguistic considerations. More specifically, it would seem that language models termed probabilistic are particularly well adapted to this sort of task, as they provide a quantitative criterion for resolving ambiguity. When the system encounters an unaccented form that could correspond to various valid word forms (that may or may not take accents), it chooses the most probable one on the basis of the immediate context and a set of events observed previously (the training corpus).

Notons que cette idée n'est pas entièrement originale : El-Bèze et al. exposent dans [3] une technique de réaccentuation qui s'inspire des mêmes concepts, alors que Yarowsky obtient des résultats comparables dans [6], en combinant différents critères de désambiguïsation statistiques dans un cadre unificateur (les listes de décision).

Note, however, that this idea is not entirely original. El-Bèze et al. [3] describe an accent-restoration technique that draws upon the same concepts, while Yarowsky has obtained comparable results [6] by combining different criteria for statistical disambiguation within a unifying framework (decision lists).

2 Réaccentuation automatique

2 Automatic Accent Restoration

Nous avons mis au point un programme de réaccentuation automatique, que nous appelons Reacc, basé sur un modèle de langue stochastique. Reacc accepte en entrée une chaîne de caractères représentant un texte français sans accent. Si la chaîne d'entrée contient des accents, on peut bien sûr la désaccentuer : comme à tout caractère accentué ne correspond qu'un seul caractère sans accent, ce processus est entièrement déterministe. Une autre possibilité est de conserver les accents, en prenant pour acquis qu'ils sont corrects. Dans un cas comme dans l'autre, la sortie attendue de Reacc est une chaîne de caractères qui ne diffère de la chaîne d'entrée que par les accents : on s'attend à recevoir en sortie le même texte français, mais correctement accentué.

We have developed an automatic accent restoration program called Reacc. It is based on a stochastic language model. Reacc will accept as input a string of characters that represents unaccented French text. If the input string contains accents, the accents can, of course, be stripped away. Since each accented character can correspond to only one unaccented character, this process is entirely deterministic. Another option is to retain the accents, on the assumption that they are correct. In either case, the output expected from Reacc is a string of characters that differs from the input string solely in terms of accents. The expected output is therefore the same French text, the only difference being that the words are properly accented.

Reacc procède donc en trois étapes successives : segmentation, génération d'hypothèses et désambiguïsation.

Reacc performs three successive operations: segmentation, hypothesis generation and disambiguation.

L'unité sur laquelle opère Reacc est le mot. L'exercice de segmentation consiste donc à prendre la chaîne d'entrée et à y localiser les frontières entre les mots, incluant les signes de ponctuation, de même que les nombres et autres expressions combinant chiffres et lettres. La segmentation repose sur un ensemble de règles décrivant des connaissances générales sur la structure des textes électroniques. Très peu de ces connaissances sont spécifiques au français. On retrouve quand même une liste d'abréviations et acronymes courants, qui sert à déterminer si un point accolé à une suite de caractères alphabétiques appartient à ce mot, ou agit comme point final. On utilise aussi une liste des constructions les plus fréquentes impliquant le tiret et l'apostrophe en français, afin de déterminer s'ils agissent ou non comme frontière de mots : l'école versus aujourd'hui, passe- montagne versus pensez-vous.

The unit on which the program operates is the word. Therefore, the segmentation process consists in taking the input string and locating word boundaries, including punctuation marks, numbers and number/letter combinations. Segmentation relies almost exclusively on language-independant data, i.e. a set of rules encoding general knowledge about the structure of electronic texts. One exception to this is a list of French abbreviations and current acronyms, which is used to determine whether a period following a string of alphabetic characters (i.e., a word) belongs to the string itself or serves to end a sentence. Also, a list of the most prevalent constructions involving the hyphen and apostrophe in French is needed to determine whether or not these symbols act as word boundaries-for instance, compare l'école (in which case the apostrophe replaces an elided vowel in the article la and serves to link it with the noun that follows) with aujourd'hui (a single word with a compound origin), and passe-montagne (a compound noun) with pensez-vous (an interrogative inversion of pronoun and verb).

L'étape suivante, la génération d'hypothèses, consiste à produire, pour chaque mot identifié lors de la segmentation, la liste de toutes les possibilités d'accentuation. Par exemple, si on a isolé l'unité cote, on veut générer les formes cote, coté, côte, côté. En fait, rien n'empêche qu'on génère aussi les formes côtè, cötê, etc. En pratique, toutefois, il importe de limiter autant que possible le nombre d'hypothèses, de façon à réduire le potentiel d'explosions combinatoires. On a donc recours à une liste de toutes les formes françaises valides, formes fléchies incluses, indexées sur leurs versions désaccentuées. En théorie, une telle liste peut contenir plusieurs centaines de milliers de formes distinctes. En pratique, on peut couper ce nombre de moitié, en excluant les formes qui ne portent pas d'accents et pour lesquelles il n'existe pas de variante accentuée valide. On peut réaliser des économies supplémentaires en excluant les formes les moins fréquentes, mais dans ce cas, il faut s'attendre à une baisse de la performance.

The next step, hypothesis generation, consists in producing a list of all accentuation possibilities for each word identified in the segmentation process. For example, if the unit cote has been isolated, the system would have to generate cote, coté, côte, and côté. Note that nothing precludes the generation of nonexistent words such as côtè and cötê. In practice, though, it is important to limit the number of hypotheses as much as possible so as to reduce the possibility of an undue number of combinations. The system thus draws upon a list of all valid French forms, including inflections, indexed according to their unaccented counterparts. In theory, such a list could contain several hundreds of thousands of distinct word forms. In practice, though, the number can be reduced by half, by excluding the forms that take no accents and for which there are no valid accented variants. The number can be further reduced by excluding the lower-frequency forms; however, this will eventually result in a decline in performance.

Une fois les hypothèses générées, il faut choisir les plus vraisemblables : c'est ce qu'on appelle la désambiguïsation. Nous utilisons pour ce faire un modèle de langue stochastique, appelé modèle de Markov caché (l'implantation que nous utilisons est le package lm de Foster [4]). Dans ce modèle, un texte est vu comme le résutat de deux processus stochastiques distincts. Le premier processus génère une suite de symboles qui, dans notre modèle, correspondent à des étiquettes morpho-syntaxiques (par exemple : NomCommun-masculin-singulier, Verbe-Indicatif-présent- 3ième-personne-pluriel). Dans un modèle markovien d'ordre N, la production d'un symbole dépend uniquement des N-1 symboles précédents. La séquence d'étiquettes produite constitue le phénomène caché d'où le modèle tire son nom. Le deuxième processus génère alors, pour chaque étiquette de la séquence, un autre symbole qui, cette fois-ci, correspond à une forme (un mot) du langage. Cette deuxième séquence est le résultat observable.

Once all the hypotheses have been generated, the most probable ones must be selected. This step is called disambiguation. A stochastic language model, called a hidden Markov model (HMM) is used (by means of Foster's Im package [4]) to carry out the disambiguation process, According to this model, a text is seen as the result of two distinct stochastic processes. The first generates a series of symbols which, in our model, correspond to morpho-syntactic tags (e.g., CommonNoun- masculine-singular; Verb-indicative-present-3rdPerson-plural). In an N-class HMM, the production of a symbol depends exclusively on the preceding N-1 symbols. The sequence of tags produced constitutes a hidden phenomenon (from which the name of the model is derived). Then for each tag in the sequence, the second process generates another symbol-in this instance, one that corresponds to a word that exists in the language. This second sequence is the observable result.

Les paramètres de notre modèle sont donc :

The parameters of our model are as follows:

· P(ti | hi-1) : La probabilité d'observer une étiquette ti, étant données les N-1 étiquettes précé- dentes (hi-1 désigne la suite d'étiquettes de longueur N-1 se terminant à la position i-1).

· P(ti | hi-1): The probability of observing tag ti, given the preceding N-1 tags (hi-1 designates the series of N-1 tags ending at position i-1).

· P(fi | ti) : La probabilité d'observer une forme fi, étant donnée l'étiquette sous-jacente ti.

· P(fi | ti): The probability of observing form fi, given the underlying tag ti.

Bien entendu, la valeur exacte de ces paramètres est inconnue, mais en pratique, on peut en faire l'estimation à partir de fréquences observées dans un corpus d'entraînement. Ce corpus consiste en un ensemble de phrases, à chaque mot duquel est acollée l'étiquette appropriée (en d'autres mots : un corpus dans lequel la nature du phénomène caché nous est "révélée"). La taille du corpus doit être suffisante pour assurer une estimation fiable de la valeur de chaque paramètre. À défaut d'un tel corpus étiquetté, on peut effectuer l'entraînement à partir d''un texte non-étiquetté, pour ensuite raffiner la valeur des paramètres par réestimation. On peut aussi combiner ces deux méthodes, c'est-à-dire obtenir une première estimation des paramètres à partir d'un petit corpus étiquetté, pour ensuite en faire la réestimation sur la base d'un corpus non-étiquetté de plus grande taille.

The exact value of these parameters is, of course, unknown, but in practice, an estimate can be made on the basis of frequencies observed in a training corpus. The corpus consists of a series of sentences, each word of which is assigned an appropriate tag (i.e., a corpus within which the nature of the "hidden" phenomenon is "revealed"). The corpus must be large enough to ensure a reliable estimate of the value of each parameter. If no such tagged corpus is available, the training operation can be carried out on an untagged text, and the parameters subsequently refined by reestimation. Another option is to combine the two methods-i.e., to obtain an initial estimate of the parameters on the basis of a small tagged corpus and then proceed with a reestimation on the basis of a larger, untagged corpus.

Étant donnés ces paramètres, on peut évaluer la probabilité globale d'une suite de mots s = s1s2...sn. Soit T, l'ensemble de toutes les séquences d'étiquettes de longueur n possibles : Bien que le calcul direct de cette équation requière un nombre d'opérations exponentiel en n, il existe un algorithme qui produit le même résultat en temps polynomial (voir [5]).

Given these parameters, the overall probability of a sequence of words s = s1s2...sn can be evaluated. If T is the set of all possible n-length tagged sequences, then: Although the direct calculation of this equation requires a number of operations exponential in n, there is an algorithm that will produce the same results in polynomial time (see [5]).

Notre stratégie de désambiguïsation consiste à choisir la suite d'hypothèses qui produit la version du texte dont la probabilité globale est maximale. En d'autres mots, si on représente le texte et ses hypothèses d'accentuation comme un graphe acyclique dirigé (DAG), le problème peut se formuler comme la recherche du chemin, allant du début à la fin du texte, dont la probabilité est maximale (figure 1).

Our disambiguation strategy consists in choosing a series of hypotheses that produce the version of the text with the highest overall probability. In other words, if a given text segment and its accentuation hypotheses are represented as a directed acyclic graph (DAG), the problem can be expressed as the search, from the beginning to the end of the text segment, for the pathway with the highest probability (figure 1).

Figure 1: Représentation d'un texte et des hypothèses d'accentuation sous forme de graphe acyclique dirigé

Figure 1: Representation of a text segment and possible accentuation hypotheses in the form of a directed acyclic graph

Le calcul de ce chemin pose bien entendu des problèmes de complexité de calcul, puisque le nombre de chemins à explorer croît en général de façon exponentielle avec la longueur du texte. En pratique, toutefois, il est possible de segmenter le graphe en îlots indépendants, c'est-à-dire en sections pour lesquelles le chemin optimal est indépendant du reste du graphe. Typiquement, on considère que les phrases sont indépendantes les unes des autres. On peut donc segmenter le texte en phrases et calculer le chemin optimal pour chaque phrase. Si le nombre de possibilités à l'intérieur d'une phrase demeure problématique, il existe des moyens de resegmenter celle-ci, au prix d'une légère dégradation de la précision. Dans notre implantation, chaque phrase est découpée en segments tels que le nombre de chemins à explorer à l'intérieur d'un segment n'excède pas un certain seuil (que nous appelons le paramètre S). Les points de coupe sont choisis au moyen d'une heuristique simple qui tend à minimiser la dépendance entre les segments : dans la mesure du possible, chaque segment doit se terminer par une suite de mots non-ambigus, c'est- à-dire pour lesquels il n'existe à la fois qu'une seule hypothèse d'accentuation et une seule analyse lexicale. On traite alors successivement les segments de gauche à droite, et on préfixe chaque segment avec les derniers mots du chemin optimal du segment précédent.

There are, of course, computational complexity problems involved in the calculation of this pathway, as the number of pathways to be explored generally increases exponentially with the length of the text segment. In practice, however, it is possible to segment the graph into independent islets-i.e., into sections for which the optimal pathway is independent from the rest of the graph. Typically, sentences are considered to be independent of one another. The text can thus be segmented into sentences and the optimal pathway for each can be calculated. If the number of possibilities within a given sentence remains problematic, there are ways of resegmenting the sentence, at the expense of a slight loss in accuracy. In our way of proceeding, each sentence is segmented such that the number of pathways to be explored within a given segment does not exceed a certain threshold (referred to as parameter S). The segmentation points are chosen by means of a simple heuristic that tends to minimize segment interdependence. As much as possible, each segment must end with a series of non-ambiguous words-i.e., words for which there is only one accentuation hypothesis and one lexical analysis. The segments are processed successively from left to right, and each is prefixed with the last words of the optimal pathway of the preceding segment.

Une fois la désambiguïsation effectuée, il reste à produire un résultat. Cette opération est en réalité très simple, mais quand même digne d'intérêt. En effet, un de nos principaux soucis est de préserver dans la sortie l'apparence du texte d'entrée. Il faut donc partir de chaque forme apparaissant sur le chemin optimal du graphe, retrouver la forme correspondante dans la chaîne d'entrée, et transposer l'accentuation de la nouvelle forme sur la forme originale, sans autrement en modifier l'apparence.

Once the disambiguation process has been completed, the results must be produced. Though this operation does merit attention, it is actually very simple. One of our primary concerns is to preserve the appearance of the input text once it reaches the output stage. Therefore, we must start with each word form that appears on the optimal pathway represented on the graph, find the corresponding ocurrence in the input string, and transpose the accentuation of the new form onto the original form without modifying its appearance in any other way.

3 Évaluation

3 Assessment

Pour évaluer la performance d'une méthode de réaccentuation, il suffit de choisir un texte ou un ensemble de textes français correctement accentués, de les désaccentuer automatiquement, de soumettre le tout au programme de réaccentuation, et de comparer les résultats obtenus au texte original.

In order to assess the performance of an accent-restoration method, one simply has to select a French text or set of texts that are correctly accented, automatically strip them of accents, feed them into the accent-restoration program, and then compare the results with the original text.

Une des propriétés de Reacc que nous souhaitions évaluer était sa capacité à fonctionner avec des textes de nature variée. Pour ce faire, l'idéal aurait été de soumettre à notre programme un corpus "balancé", du même genre que le Brown Corpus. Comme nous ne disposions pas d'une telle ressource pour le français, nous avons dû confectionner notre propre corpus, à partir de documents qui nous étaient disponibles.

One of the properties of Reacc that we wanted to evaluate was its ability to operate on various types of texts. In order to do so, the ideal would have been to run the program on a "balanced" corpus, along the lines of the Brown corpus. However, since no such resource was available in French, we had to construct our own corpus from the documents at our disposal.

Le corpus de test est donc constitué d'extraits de textes français accentués, provenant de sept sources différentes, représentées à peu près également : on y retrouve des textes du domaine militaire, des textes juridiques, des publications des Nations Unies, des textes littéraires, des revues de presse, des manuels informatiques et des extraits du Hansard canadien (journal des débats à la Chambre de Communes). L'ensemble totalise 57 966 mots (ce compte a été produit au moyen de l'utilitaire UNIX wc). Certaines modifications ont été apportées au texte, afin de corriger les quelques erreurs d'accentuation que nous avons pu déceler au fil des expériences.

The training corpus was therefore composed of excerpts from accented French texts drawn from seven different sources, represented in more or less equal proportions. The texts include military documents, legal texts, United Nations publications, literary texts, press reviews, computer manuals, and excerpts from Hansard (the official record of proceedings in Canada's House of Commons). The corpus totals 57,966 words (a figure produced by the UNIX wc utility). Certain adjustments were made to the texts in order to correct a few errors in accentuation that were found during testing.

Le générateur d'hypothèses de Reacc utilisait, pour nos tests, une liste de formes extraite du DMF, un dictionnaire morpho-syntaxique contenant près de 380 000 formes distinctes ([1]). En fait, ce nombre est probablement excessif. Nous avons d'ailleurs obtenu des résultats tout-à-fait satisfaisants lors d'expériences préliminaires, avec un dictionnaire ne reconnaissant que 50 000 formes environ.

For the purposes of our tests, the Reacc hypothesis generator used a list of word forms taken from the Dictionnaire micro-informatisé du français (DMF), a morpho-syntactic dictionary that contains nearly 380,000 distinct word forms [1]. Such a large number of terms is probably unnecessary. In fact, as fully satisfactory results were obtained during preliminary trials using a dictionary that recognized some 50,000 word forms only.

Pour le modèle de langue, après différentes expériences, nous avons opté pour une approche qui privilégie la qualité des données sur leur quantité. Nous avons utilisé un modèle de Markov caché d'ordre 2, basé sur un ensemble d'environ 350 étiquettes morpho-syntaxiques. Les paramètres du modèle ont d'abord été initialisés à l'aide du DMF, c'est-à-dire qu'on a restreint d'emblée les P(fi | ti) en fonction du contenu des valeurs sanctionnées par le dictionnaire. On a ensuite procédé à un entraînement du modèle sur un corpus de texte de 60 000 mots, extrait du Hansard canadien, étiqueté à la main ([2]). On a finalement utilisé un corpus de texte beaucoup plus volumineux (plus de 3 millions de mots), non-étiqueté, afin de réestimer les paramètres du modèle.

Where the language model was concerned, after various trials, we opted for an approach that placed a greater priority on the quality rather than the quantity of data. We used a bi-class HMM based on a set of approximately 350 morpho-syntactic tags. The parameters of the model were first initialized by means of the DMF-in other words, the P(fi | ti) were restricted according to the contents of the values sanctioned by the dictionary. We then went on to an initial training phase, using a 60,000-word manually tagged corpus taken from the Canadian Hansard [2]. Lastly, a much larger untagged corpus was used, consisting of over 3 million words, in order to reestimate the model's parameters.

Outre le générateur d'hypothèses et le modèle de langue utilisés, plusieurs paramètres affectent la performance de Reacc, tant sur le plan de la qualité des résultats obtenus que sur celui du temps- machine. Néanmoins, le facteur le plus important est le paramètre S, qui limite la taille des segments sur lesquels Reacc travaille. On retrouve dans la tableau 1 les résultats obtenus pour différentes valeurs de S (une augmentation exponentielle de ce facteur se traduit en général par une augmentation linéaire de la longueur des segments traités). Les tests ont été effectués sur une machine Sun SPARCstation 10.

Aside from the hypothesis generator and the language model used, a number of other parameters affect Reacc's performance on the level of both the quality of the results obtained and running time. Nevertheless, the most important factor is the S parameter, which limits the size of the segments that Reacc processes. Table 1 provides the results obtained for different S values (an exponential increase in this factor generally translates into a linear increase in the length of the segments processed). The tests were carried out on a Sun SPARCstation 10.

Nombre maximum d'hypothèses par segment (S)

Maximum no. of hypotheses per segment (S)

Temps-machine (secondes)

Running time (seconds)

Nombre total d'erreurs (mots)

Total number of errors (words)

Distance moyenne entre les erreurs (mots)

Average distance between errors (words)

Tableau 1: Résultats des réaccentuations

Table 1: Results of Accent-Restoration Trials

Un examen sommaire des résultats obtenus révèle qu'on a fort à gagner en permettant au système de travailler sur des segments plus longs. Toutefois, passée une certaine limite, la qualité des résultats tend à plafonner, alors que les temps d'exécution, eux, grimpent en flèche. Tout dépendant du genre d'application et des ressources disponibles, il semblerait qu'on puisse compter sur des résultats acceptables dès lors que S est fixé à l'entour de 16 ou 32.

A cursory look at the results reveals that there is much to be gained by allowing the system to work on longer segments. However, beyond a certain limit, the quality of the results tends to level off, while the running time increases radically. Depending on the type of application and the resources available, it would seem that acceptable results can be obtained when S is set at around 16 or 32.

Il est intéressant d'examiner où Reacc se trompe. On retrouve dans le tableau 2 une classification grossière des erreurs de réaccentuation que Reacc a commises sur notre corpus de test, lorsque S était fixé à 16. La catégorie qui arrive en tête regroupe assez libéralement les erreurs qui ont pour point en commun qu'elles résultent d'un mauvais choix sur la présence d'un accent aigu sur le e de la syllabe finale (par exemple : aime versus aimé). Viennent ensuite les erreurs qui découlent de "lacunes" du générateur d'hypothèses, c'est-à-dire de cas où celui-ci ne connaît tout simplement pas la forme correctement accentuée. Dans la majorité des cas, il s'agit de noms propres (près de la moitié, en fait), mais on rencontre aussi, surtout dans les textes de nature plus technique, beaucoup d'abréviations, de mots non-français et de "néologismes" (par exemple : réaménagement, séropositivité). La catégorie qui vient ensuite concerne une unique paire de mots : la préposition à et la forme a du verbe avoir.

It is interesting to look at where Reacc goes wrong. Table 2 provides a rough classification of accent-restoration errors made by Reacc on our training corpus when S was set at 16. The category in which the greatest number of accentuation errors were made includes a rather liberal grouping of errors that have a common feature: they are the result of an incorrect choice pertaining to an acute accent on an e in the final syllable of a word (e.g., aime as opposed to aimé). The next group of errors are those that stem from inadequacies in the hypothesis generator-i.e., cases in which the generator simply does not know the correct accented form. In most cases (nearly half), proper nouns are involved, but, especially in more technical texts, there are also many abbreviations, non- French words, and neologisms (e.g., réaménagement, séropositivité). The next category concerns a unique word pair: the preposition à, and a, the third person singular form of the verb avoir.

Type d'erreur

Type of error

Nombre

Number

Pourcentage

Percentage

Ambiguïtés -e / -é

Ambiguities: -e vs. -é

Formes inconnues

Unknown word forms

Ambiguïté a / à

Ambiguity: a vs. à

Autres

Other

Total

Total

Tableau 2: Classification des erreurs d'accentuation (S = 16)

Table 2: Classification of Accent Restoration Errors (S = 16)

4 Conclusions

4 Conclusions

Nous avons présenté une méthode de réaccentuation automatique des textes français, basée sur un modèle de langue markovien caché. Cette méthode a fait l'objet d'une implantation réelle : le programme Reacc. Nos expériences ont démontré que ce programme produisait des textes d'une qualité tout-à-fait acceptable, dans des temps plus que raisonnables : on peut atteindre une moyenne d'une erreur d'accentuation aux 130 mots, en traitant plus de 20 000 mots à la minute.

This report has presented a method of automatic accent restoration for French texts, based on a hidden Markov language model. This method was actually implemented by means of the Reacc software. Our experiments have demonstrated that this program produces texts that are altogether acceptable within a totally reasonable time frame: we can expect an error to occur every 130 words on average, and the processing of 20,000 words per minute.

Bien entendu, il y a toujours place à des améliorations. En particulier, il est certain que l'utilisation d'un modèle de langue plus fin (par exemple, un modèle d'ordre 3) ne pourrait qu'améliorer la qualité de la désambiguïsation. Compte tenu aussi de la forte proportion d'erreurs d'accentuation causées par des lacunes au dictionnaire, il serait intéressant d'examiner des façons de traiter ces "mots inconnus". À cet égard, nous avons déjà effectué certaines expériences préliminaires, qui ont produit des résultats particulièrement intéressant. En particulier, nous nous sommes intéressés à des façons de "deviner" l'accentuation d'un mot inconnu, à partir d'une modélisation stochastique de l'accentuation des mots connus. Il reste toutefois beaucoup de travail à faire de ce côté.

There is, of course, always room for improvement. In particular, the use of a more refined language model (e.g., a tri-class HMM) could only enhance the quality of the disambiguation process. Moreover, given the large proportion of accentuation errors caused by words not recognized by the dictionary, it would be interesting to examine means of dealing with such "unknown" words. In this regard, we have already carried out certain preliminary experiments which have produced especially interesting results. In particular, we have focused on ways of "guessing" the accentuation of an unknown word on the basis of a stochastic model of the accentuation of known words. There is nevertheless a great deal of work to be done in this area.

Par ailleurs, les méthodes que nous avons exposées ouvrent la porte à d'autres applications du même genre. Par exemple, on peut voir comment les méthodes de réaccentuation pourraient être généralisées, afin de traiter d'autres types de pertes d'information. On pense tout particulièrement aux textes dont tous les caractères accentués ont été remplacés par un caractère unique (typiquement, un point d'interrogation), ou aux textes dont le huitième bit de chaque caractère a été perdu. Dans de tels textes le é apparaît comme un i, le è comme un h, etc. Dans ces cas, au problème de l'ambiguïté lexicale s'ajoute celui du découpage, qui devient lui aussi ambigu.

The methods we described here open the door to other, similar applications. For example, we can see how generalizations could be drawn from accent-restoration methods in order to deal with other types of information loss-especially texts in which all accented characters have been replaced by a single character (most often a question mark), or texts in which the eighth bit of each character has been lost. For instance, in such texts, é comes out as an i and è as an h. In such cases, a problem of determining word boundaries compounds that of lexical ambiguity; word boundaries thus become a source of ambiguity as well.

Une autre possibilité intéressante est de greffer un programme du genre de Reacc à un logiciel de traitement de texte, d'une manière telle que l'utilisateur puisse taper un texte français sans se soucier des accents, qui sont alors insérés automatiquement à mesure que le texte est produit. De la réaccentuation, on passe ainisi à l'accentuation automatique. Un tel mécanisme pourrait faciliter sensiblement la saisie des textes français. (On sait combien les conventions de saisie des accents au clavier sont variées et pas toujours très ergonomiques.)

Another interesting possibility is that of grafting a program such as Reacc onto a word processing application so that the user can input a French text without worrying about accents, which would be inserted automatically as the text is being input. This would thus mark a shift from accent restoration to automatic accentuation. This type of feature could significantly facilitate the inputting of French texts, especially in light of the lack of uniformity and ergonomic soundness in the conventions for producing accents on computer keyboards.

Une application beaucoup plus ambitieuse, se basant sur des méthodes similaires, est la rédaction assistée par ordinateur. Dans ce cas, plutôt que de travailler sur le texte déjà tapé par l'utilisateur, l'ordinateur s'intéresse au texte à venir, et essaie de prévoir ce que l'utilisateur va taper, de façon à lui éviter la saisie de grandes portions de texte.

A much more ambitious application that could derive from similar methods is computer-assisted writing. Instead of processing a text already input by the user, the computer would be concerned with text yet to be formulated and would try to foresee what the user will type so as to avoid the need to manually input large portions of text.

Toutes ces applications font présentement l'objet de travaux de recherche au CITI.

All of these applications are currently being studied at CITI.

Références

References

[1] Bourbeau, Laurent et François Pinard, 1987, Dictionnaire Micro-informatisé du Français (DMF), Progiciels Bourbeau Pinard Inc., 1501 avenue Ducharme, Montréal, H2V 1G2.

[1] Bourbeau, Laurent, and François Pinard. 1987. Dictionnaire micro-informatisé du français (DMF). Montreal: Progiciels Bourbeau Pinard inc.

[2] Bourbeau, Laurent, 1994, Fabrication d'un corpus témoin bilingue étiqueté et annoté pour la mise au point de techniques de parsage automatique probabiliste, Rapport technique présenté par Progiciels Bourbeau Pinard, Centre d'innovation en technologies de l'information (CITI), Laval.

[2] Bourbeau, Laurent. 1994. Fabrication d'un corpus témoin bilingue étiqueté et annoté pour la mise au point de techniques de parsage automatique probabiliste. Technical report submitted by Progiciels Bourbeau Pinard to the Centre for Information Technology Innovation (CITI), Laval.

[3] El-Bèze, Marc, Bernard Mérialdo, Bénédicte Rozeron et Anne-Marie Derouault, 1994, "Accentuation automatique de textes par des méthodes probabilistes", dans Technique et sciences informatiques, Vol 13, no 6, pp. 797 - 815.

[3] El-Bèze, Marc, Bernard Mérialdo, Bénédicte Rozeron and Anne-Marie Derouault. 1994. "Accentuation automatique de textes par des méthodes probabilistes." In Technique et sciences informatiques, vol. 13, no. 6, pp. 797-815.

[4] Foster, George F., 1995, Communication personnelle.

[4] Foster, George F. 1995. Personal communication.

[5] Rabiner, L. R. et B. H. Juang, janvier 1986, "An Introduction to Hidden Markov Models", dans IEEE ASSP Magazine.

[5] Rabiner, L. R., and B. H. Juang. 1986. "An Introduction to Hidden Markov Models." In IEEE ASSP Magazine, January issue.

[6] Yarowsky, David, 1994, "Decision Lists for Lexical Ambiguity Resolution: Application to Accent Restoration in Spanish and French", dans Proceeding of the 32nd Annual Meeting of the Association for Computational Linguistics (ACL-94), pp. 88-95. [6] Yarowsky, David. 1994. "Decision Lists for Lexical Ambiguity Resolution: Application to Accent Restoration in Spanish and French." In Proceedings of the 32nd Annual Meeting of the Association for Computational Linguistics (ACL-94), pp. 88-95.