Jean-Luc Rouas

Automatic prosodic variations modelling for language and dialect discrimination

Keywords: Automatic language identification, prosody, read and spontaneous speech

This paper addresses the problem of modelling prosody for language identification. The aim is to create a system that can be used prior to any linguistic work to show if prosodic differences among languages or dialects can be automatically determined. In previous papers, we defined a prosodic unit, the pseudo-syllable. Rhythmic modelling has proven the relevance of the pseudo-syllable unit for automatic language identification. In this paper, we propose to model the prosodic variations, that is to say model sequences of prosodic units. This is achieved by the separation of phrase and accentual components of intonation. We propose an independent coding of those components on differentiated scales of duration. Short-term and long-term languagedependent sequences of labels are modelled by n-gram models. The performance of the system is demonstrated by experiments on read speech and evaluated by experiments on spontaneous speech. Finally, an experiment is described on the discrimination of Arabic dialects, for which there is a lack of linguistic studies, notably on prosodic comparisons. We show that our system is able to clearly identify the dialectal areas, leading to the hypothesis that those dialects have prosodic differences.

EDICS Category: SPE-MULT

I. INTRODUCTION

T HE standard approach to automatic language identifica- tion (ALI) considers a phonetic modelling as a front-end. The resulting sequences of phonetic units are then decoded according to language specific phonotactic grammars [START_REF] Zissman | Automatic language identification[END_REF].

Other information sources can be useful to identify a language however. Recent studies (see [START_REF] Barkat | From perceptual designs to linguistic typology and automatic language identification: Overview and perspectives[END_REF] for a review) reveal that humans use different levels of perception to identify a language. Three major kinds of features are employed: segmental features (acoustic properties of phonemes), suprasegmental features (phonotactics and prosody) and high level features (lexicon). Beside acoustics, phonetics and phonotactics, prosody is one of the most promising features to be considered for language identification, even if its extraction and modelling are not a straightforward issue.

In the NIST 2003 Language Verification campaign, most systems used acoustic modelling, using Gaussian Mixture Models adapted from Universal Background Models (a technique derived from speaker verification [START_REF] Reynolds | Robust text-independent speaker identification using gaussian mixtures speaker models[END_REF]), and/or phonotactic modelling (Parallel Phone Recognition followed by Language Modelling -PPRLM, see [START_REF] Zissman | Automatic language identification[END_REF], [START_REF] Hazen | Segment-based automatic language identification[END_REF]). While these techniques gave the best results, systems using prosodic cues have also been investigated, following research in speaker

The author is with L2F -INESC-ID, Rua Alves Redol, 9, 1000-029 Lisboa (email: rouas@l2f.inesc-id.pt, phone: +351213100314, fax: +351213145843).

I would like to thank François Pellegrino for providing helpful comments on this article and Mélissa Barkat for her help on the Arabic dialects experiments. recognition [START_REF] Reynolds | The supersid project: Exploiting high-level information for high-accuracy speaker recognition[END_REF], notably Adami's system [START_REF] Adami | Modeling prosodic dynamics for speaker recognition[END_REF]. More recently, systems using syllable-scale features have been under research, although their aim is to model acoustic/phonotactic properties of languages [START_REF] Zhu | Different Size Multilingual Phone Inventories and Context-Dependent Acoustic Models for Language Identification[END_REF] or also prosodic cues [START_REF] Matrin | A syllable-scale framework for language identification[END_REF].

Beside the use of prosody to improve the performances of ALI systems, we believe that there is a real linguistic interest in developing an automatic language identification system using prosody and not requiring any a priori knowledge (e.g. manual annotations). Hence, we will have the possibility of testing if prosodically unstudied languages can be automatically differentiated. The final aim of our studies is to automatically describe prosodic language typologies.

In this paper, we will describe our prosodic-based language identification system. In section II, we will recall the main linguistic theories about differences among languages. After reviewing the linguistic and perceptual elements that demonstrate the interest of prosody modelling for language identification, we will address the problem of modelling.

Indeed, modelling prosody is still an open problem, mostly because of the suprasegmental nature of the prosodic features. To address this problem, automatic extraction techniques of sub-phonemic segments are used (section III). After an activity detection and a vowel localisation, a prosodic syllable-like unit adapted to language identification is characterised. Results previously obtained by modelling prosodic features extracted on this unit are briefly described at the end of section III. We believe however that prosodic models should take into account temporal fluctuations, as prosody perception is mostly linked to variations (in duration, energy and pitch). That is why we propose a prosody coding which enables to consider the sequences of prosodic events in the same way as language models are used to model phone sequences in the PPRLM approach. The originality of our method lies in differentiating phrase accent from local accent, and modelling them separately. The method is described in section IV. The system is firstly tested on databases with languages that have known prosodic differences to assess the accuracy of the modelling. These experiments are carried out on both read (section V) and spontaneous (section VI) speech, using respectively the MULTEXT [START_REF] Campione | A multilingual prosodic database[END_REF] and OGI-MLTS [START_REF] Muthusamy | The ogi multilanguage telephone speech corpus[END_REF] corpora. Then, a final experiment is performed on Arabic dialects (section VII), for which we investigate if prosodic differences between those dialects can be automatically detected.

II. PROSODIC DIFFERENCES AMONG LANGUAGES

The system described in this paper aims at determining to what extent languages are prosodically different. In this section, we will describe what the rhythmic and intonational properties of languages are and how humans perceive them.

A. Rhythm

The rhythm of languages has been defined as an effect involving the isochronous (that is to say at regular intervals) recurrence of some type of speech unit [START_REF] Grabe | Durational variability in speech and the rhythm class hypothesis[END_REF]. Isochrony is defined as the property of speech to organise itself in pieces equal or equivalent in duration. Depending on the unit considered, the isochrony theory classifies languages in three main sets:

• stress-timed languages (as English and German),

• syllable-timed languages (as French and Spanish),

• mora-timed languages (as Japanese). Syllable-timed languages share the characteristic of having regular intervals between syllables, while stress-timed languages have regular intervals between stressed syllables, and for mora-timed languages, successive mora are quasi equivalent in terms of duration. This point of view was made popular by Pike [START_REF] Ladefoged | The intonation of American English[END_REF] and later by Abercrombie [START_REF] Abercrombie | Elements of General Phonetics[END_REF]. According to them, distinction between stress-timed and syllable-timed languages is strictly categorical, since languages cannot be more or less stress or syllable-timed. Despite its popularity among linguists, the rhythm class hypothesis is contradicted by several experiments (notably by Roach [START_REF] Roach | On the distinction between "stress-timed" and "syllabletimed" languages[END_REF] and Dauer [START_REF] Dauer | Stress-timing and syllable-timing reanalysed[END_REF]). This forced some researchers (Beckman [START_REF] Beckman | Evidence for speech rhythms across languages[END_REF] for example) to shift from "objective" to "subjective" isochrony. True isochrony is described as a constraint, and the production of isochronous units is perturbed by phonetic, phonologic and grammatical rules of the languages. Some other researchers have concluded that isochrony is mainly a perceptual phenomenon (for example Lehiste [START_REF] Lehiste | Isochrony reconsidered[END_REF]). Isochrony can then be seen as a concept relative to speech perception.

The lack of an empirical proof of isochrony led Dauer [START_REF] Dauer | Stress-timing and syllable-timing reanalysed[END_REF] to propose a new rhythmic classification system. From her point of view, speakers do not try to keep equal interstress or inter-syllabic intervals, but languages are more or less stress or syllable-timed. Nespor [START_REF] Nespor | On the rhythm parameter in phonology[END_REF] introduced the notion of rhythmically intermediate languages, which share properties associated with stress-timed languages and other associated with syllable-timed languages. As an example, she cites Polish -classed as stress-timed although it does not have vocalic reduction -and Catalan -syllable-timed but having vocalic reduction.

B. Intonation

Three main groups of languages can be characterised regarding their use of intonation:

• tone languages (as Mandarin Chinese),

• pitch-accent languages (as Japanese),

• stress-accent languages (as English and German). According to Cummins [START_REF] Cummins | Speech rhythm and rhythmic taxonomy[END_REF], distinguishing languages using fundamental frequency alone had a moderate success. The explanation is twofold:

• On the one hand, we can imagine a discrimination based on the use of lexical tone (Mandarin) or not (English), but intermediate cases exist (Korean dialects) which are usually considered as representing transitory states between languages of one class and those of another [START_REF] Hyman | Word-prosodic typology[END_REF].

• On the other hand, phenomena linked to accents and intonation are less easy to handle. There are multiple theories on utterance intonation that do not agree. The situation is made more complex by studies on the nonlinguistic uses of intonation, as for example to express emotions. Several studies agree on a classification by degrees rather than separate classes [START_REF] Ladd | The perception of intonation emphasis: continuous or categorical?[END_REF].

C. Perception

Over the last few decades, numerous experiments have shown the human capability for language identification [START_REF] Barkat | From perceptual designs to linguistic typology and automatic language identification: Overview and perspectives[END_REF]. Three major kinds of cues help humans to identify languages:

1) Segmental cues (acoustic properties of phonemes and their frequency of occurrence), 2) Supra-segmental cues (phonotactics, prosody), 3) High-level features (lexicon, morpho-syntax). About prosodic features, several perceptual experiments try to shed light on human abilities to distinguish languages keeping only rhythmic or intonation properties. The method is to degrade speech recordings by filtering or re-synthesis to remove all segmental cues to the subjects whose task is to identify the language. The subjects are either naive or trained adults, infants or newborns, or even non-human primates. For example, all the syllables are replaced by a unique syllable "/sa/" in Ramus' experiments [START_REF] Ramus | Correlates of linguistic rhythm in the speech signal[END_REF]. In other cases, processing of speech through a low-pass filter (cutoff frequency 400 Hz) is used to degrade the speech signal [START_REF] Frota | Language discrimination and rhythm classes: evidence from portuguese[END_REF]. Other authors [START_REF] Komatsu | Perceptual discrimination of prosodic types[END_REF] propose different methods to degrade the speech signal in order to keep only the desired information (intensity, intonation or rhythm). From a general point of view, all those experiments show the notable human capacity to identify to some extent foreign languages after a short period of exposure.

III. SEGMENTATION, VOWEL DETECTION AND PSEUDO-SYLLABLES

The starting point of recent work on rhythm is the rhythm description method proposed by Ramus in 1999 [START_REF] Ramus | Correlates of linguistic rhythm in the speech signal[END_REF]. Following him, others have proposed different and more complex rhythm modelling methods (for example [START_REF] Grabe | Durational variability in speech and the rhythm class hypothesis[END_REF] and [START_REF] Galves | Sonority as a basis for rhythmic class discrimination[END_REF]). The weak point in many of those approaches is that they have only been applied after a manual segmentation of the speech signal. Consequently, their performance has only been assessed on relatively small corpora.

To overcome this limitation and to model the prosody of languages automatically, we use automatic processing to extract prosodic information. Three baseline procedures lead to relevant consonant, vocalic and silence segment boundaries:

• Automatic speech segmentation leading to quasistationary segments: This segmentation results from the "Forward-Backward Divergence" (DFB) algorithm [START_REF] André-Obrecht | A new statistical approach for automatic speech segmentation[END_REF], which is based on a statistical study of the signal in the temporal framework. The segmentation achieves an sub-phonemic segmentation where segments correspond to steady or transient parts of phonemes.

• Vocal activity detection: The vocal activity detection is based on a first order statistical analysis of the temporal signal [START_REF] Pellegrino | Vocalic system modeling : A vq approach[END_REF]. The activity detection algorithm detects the less intense segments of the excerpt (in terms of energy)

and the other segments are classified as Silence or Activity according to an adaptive threshold.

• Vowel localisation: The vowel location algorithm is based on a spectral analysis (see [START_REF] Pellegrino | Vocalic system modeling : A vq approach[END_REF] for more details). The fact that neither labelled data nor supervised learning are necessary constitutes the main advantage of this algorithm. The fact that no learning phase is necessary allows the algorithm to be used on different languages, even if no hand-labelled data is available. However, the consequence is that the algorithm is not optimised for any language even if it behaves correctly when compared to other systems [START_REF] Pellegrino | Une approche phonétique en identification automatique des langues : la modélisation acoustique des systèmes vocaliques[END_REF]. This front-end processing results in a segmentation into vocalic, consonantal and silence segments. Labels "V", "C", or "#" are used to qualify each segments (Figure 1). The syllable is a privileged unit for rhythm modelling. However, automatic extraction of syllables (in particular, boundary detection) is a controversial operation that is still in debate among phonologists: the pronunciation quality and the speech rate are factors influencing directly the syllable segmentation [START_REF] Kopecek | Syllable based approach to automatic prosody detection; applications for dialogue systems[END_REF]. Furthermore, segmenting the speech signal in syllables is a language-specific task [START_REF] Pfitzinger | Syllable detection in read and spontaneous speech[END_REF]. No language-independent algorithm can be easily applied.

We therefore used the notion of pseudo-syllable [START_REF] Rouas | Rhythmic unit extraction and modelling for automatic language identification[END_REF]. The basic idea is to articulate the prosodic unit around primordial elements of the syllables -vowels -and to gather the neighbouring consonants around those nuclei. We have decided to gather only the preceding consonants. This choice is explained by the fact that syllable boundary detection is not an easy task in a multilingual framework, and that the most frequent syllables correspond to the consonant/vowel structure [START_REF] Dauer | Stress-timing and syllable-timing reanalysed[END_REF]. An example of this segmentation is shown in Figure 2.

We showed in previous papers [START_REF] Rouas | Rhythmic unit extraction and modelling for automatic language identification[END_REF] that the pseudo-syllable segmentation can be successfully used for language identification. Features characterising durations and fundamental frequency variations are extracted from each pseudo-syllable and are used to learn the parameters of Gaussian mixtures for each language of the database.

With the duration features, the correct identification rate is 67% for the seven languages of the MULTEXT corpus. This result is obtained using a mixture of 8 Gaussians. With the Fig. 2. Pseudo-syllable segmentation performed for the sentence "les choux avaient été entièrement dévorés par les limaces". Consecutive "C" segments are gathered until a "V" segment is found. intonation features, the correct identification rate is 50%, using a GMM with 8 components. A fusion of the results obtained with both duration and intonation features allows to reach 70% correct. The confusions occur mainly across languages belonging to the same groups evoked in linguistic theories.

Identifying stress-timed languages (English, German and hypothetically Mandarin) versus syllable-timed languages (French, Italian and Spanish) versus mora-timed languages (Japanese), accuracy is 91% correct using both duration and intonation models.

Nevertheless, the statistical models (Gaussian Mixture Models) we use to model pseudo-syllabic features are intrinsically static models. This does not fit with the perceptive reality of prosody which is continue, dynamic and supra-segmental. We must use different models to take the temporal variations into account.

IV. MODELLING PROSODIC VARIATIONS Following Adami's work [START_REF] Adami | Modeling prosodic dynamics for speaker recognition[END_REF], we used the features computed on each pseudo-syllable to label the fundamental frequency and energy trajectories. Two models are used to separate the long-term and short-term components of prosody. The long-term component characterises prosodic movements over several pseudo-syllables while the short-term component represents prosodic movements inside a pseudo-syllable. An overview of the system is displayed in Figure 3. Fundamental frequency and energy are extracted from the signal using the SNACK Sound toolkit [START_REF] Sjölander | The snack sound toolkit[END_REF].

A. Fundamental frequency coding

The fundamental frequency processing is divided into two phases, representing the phrase accentuation and the local accentuation, as in Fujisaki's work [START_REF] Fujisaki | Prosody, information and modeling -with emphasis on tonal features of speech[END_REF]:

1) Baseline computing & coding: The baseline extraction consists in finding all the local minima of the F 0 contour, and linking them. Then, the baseline is labelled in terms of U(p), D(own) and #(silence or unvoiced).

To find local minima, the sound file is automatically divided into "sentences," defined here as intervals between silent segments of duration over 250 ms. The linear regression of the F 0 curve is then computed on each sentence. Then each part of the curve under the linear regression is used to find a unique minima (Figure 4). Successive minima are linked by linear approximation. An example of a resulting baseline curve is displayed in Figure 5. The slope of the regression is used to label the baseline. We use one label per pseudo-syllable. Labels are 'U' for a positive slope and 'D' for a negative slope. Unvoiced pseudo-syllables (less than 70% voiced in duration) are labelled '#'. In this example, the label sequence corresponding to the sentence is:

U.U.U.U.D.D.D.D.D.D.# 2

) Residue approximation & coding:

The baseline is subtracted from the original contour. The resulting curve is called residue (Figure 6). This residue is then approximated for each segment by a linear regression. The slope of the linear regression is used to label the F 0 movement on the unit, according to three available labels (Up, Down and Silence).

B. Energy coding

The energy curve is approximated by linear regressions for each considered units (sub-phonemic segments or pseudo- syllables) (Figure 7). The process is the same as the one used for the residue coding. As there is no segment with no energy, only two labels are used: Up and Down. In this example, the sequence of labels is:

C. Duration coding

Duration labels are computed only for the sub-phonemic segment units. The labels are assigned considering the mean duration of each kind of segment (vocalic, consonantic or silence). If the segment to label is a vocalic segment with a duration above the mean vocalic segments duration computed on the learning part of the corpus, it is labelled "l" (long), If the current vocalic segment duration is below the mean, the "s" (short) label is then used. The duration labels generated on the example sentence are: s.l.s.s.s.s.s.s.s.s.l.s.l.s.s.l.s.s.s.s.l.s.l.s.s.s.s.l.s.s.s.s.s.s.s

D. Modelling

To model the prosodic variations, we use classical n-gram language modelling provided by the SRI language modelling toolkit [START_REF] Stolcke | Srilm -an extensible language modeling toolkit[END_REF]. For each system -long-and short-term -each language is modelled by a n-gram model during the learning procedure. During the test phase, the most likely language is picked according to the model which provides the maximum likelihood. For the long-term models, this modelling is applied at the pseudo-syllable level and n-grams are learnt using baseline labels, eventually combined with energy labels coded at the pseudo-syllable scale. The short-term models are learnt using the sub-phonemic segmentation, and using the residue labels, optionally combined with energy and duration labels. For each segment, the label is then composed of three symbols. For the example sentence, we have:

#Ds

Several lengths for the n-gram models have been tested (from 3-to 5-grams), but as the best results are obtained with 3-grams, only the results obtained using 3-grams models are displayed.

V. EXPERIMENTS ON READ SPEECH

The first experiments are made on the MULTEXT corpus [START_REF] Campione | A multilingual prosodic database[END_REF] (a subset of EUROM1), which contains 5 languages (English, French, German, Italian and Spanish), and 10 speakers per language, balanced between male and female. We have 10 20-second files per speaker. This baseline corpus has been extended with recordings of Japanese speakers [START_REF] Kitazawa | Periodicity of japanese accent in continuous speech[END_REF]. Mandarin Chinese recordings are also added to the original corpus, thanks to Komatsu [START_REF] Komatsu | Perceptual discrimination of prosodic types[END_REF].

The three theoretical rhythmic classes are represented in this corpus : English, German and Mandarin Chinese are stresstimed languages; French, Italian and Spanish are syllabletimed languages, and Japanese is a mora-timed language. Moreover, Mandarin Chinese is a tone language and Japanese is a pitch-accent language.

For the learning phase, we used 8 speakers (4 for Japanese), and 2 (one male and one female) were used for the tests. We have 80 learning files per language (≈ 26 minutes) and 20 test files per language (≈ 6 minutes) -except for French (19 files) -resulting in a total of 139 test files.

A. Long-term modelling

The sequences of labels computed on each pseudo-syllable are modelled by n-gram models. We investigated different combinations of labels to see which features are more useful (Table I). The best performance is obtained using only the baseline labels. With these labels, the correct identification rate is 50%. The confusion matrix is drawn in Table II with identified languages in columns and references in rows (confidence intervals are provided in the legend). Table II show that French, Spanish and German are clearly identified.

B. Short-term modelling

The sequences of labels computed on each sub-phonemic segment are also modelled by n-gram models. Contributions of different features are shown in Table III. The best results are obtained using the combination of residue, energy and duration labels. The identification rate is 80%. Detailed results using this configuration are displayed in Table IV. These results allow us to hypothesise that the most characteristic prosodic elements of languages are not pseudosyllable sequences but sequences of elements constituting them.

C. Merging long and short-term components

The merging of the two systems described previously is addressed. The merging technique is a simple addition of the log-likelihoods. The identification rate obtained with this method is 83%, which is considerably better than the 70% obtained with static modelling (section III). Despite the poor performance of the long-term model, merging the long and short term results allows to improve the identification rate. Results show that most languages are well identified.

The language classes evoked in section II have an influence on the correct identification rates: Mandarin (i.e. the only tone language of the corpus) is the most clearly identified language. Japanese, the only mora-timed language, and the only pitchaccent language in our corpus, is also well identified. The main confusions are between Italian and Spanish, both belonging to the syllable-timed and stress-accent groups. Considering rhythmic classes (represented in different strength of grey in the matrix), we can see that most confusions are within languages of the same rhythmic family.

Consequently, a rhythmic classes identification experiment was performed using the same data with the fusion of the short and long-term models. English, German and Mandarin are part of the stress-timed group; French, Italian and Spanish are in the syllable-timed group, and Japanese constitutes in itself the mora-timed group. The rhythmic classes identification rate is 94% (Table VI). On this data, our system manages well to classify languages according to their prosodic properties.

VI. EXPERIMENTS ON SPONTANEOUS SPEECH

The same experiments have been made on a spontaneous speech corpus, the OGI Multilingual Telephone Speech Corpus (OGI-MLTS) corpus [START_REF] Muthusamy | The ogi multilanguage telephone speech corpus[END_REF]. This corpus is composed of telephone speech recorded in ten languages: English, Farsi, French, German, Japanese, Korean, Mandarin, Spanish, Tamil and Vietnamese. Experiments are made on 6 languages (English, French, German, Japanese, Mandarin and Spanish) using spontaneous speech utterances of 45 seconds each, one file per speaker. The data organization is displayed in Table VII. The tests here are made using the same tuning as for the read speech experiments -same features used (baseline labels for the long-term model, and the combination of residue, energy and duration labels for the short-term model), same n-gram configuration (3-grams). Results are displayed in Tables VIII and IX for the long and short-term models respectively.

The long-term model only manages to reach performances slightly better than chance (on a six-way classification, the chance level is ≈ 16%).

The short-term model achieves a performance of 40% of correct identifications. The best recognised languages are English (55%) and Japanese (53%). We can observe that German is mainly confused with English.

The performances of the system for the rhythm classes identification task is given in Table X. The global identification rate is 69%. The identification rates for each class are respectively 85% for the stress-timed languages, 46% for the syllable-timed languages and 53% for the mora-timed language. As expected from language identification results, syllable-timed languages are the least recognised. The identification mistakes are made principally on the French language, responsible for 10 errors -that is to say 66% of the syllable-timed languages identification error. This may be explained by the different varieties of French (Canadian and European) encountered in the corpus.

It is however quite difficult to directly transpose our approach, designed on read speech, to spontaneous speech. The main reason may be the intrinsic variability of the spontaneous data. This variability can be linked to the great variations of speech rate observed within each language (see [START_REF] Pellegrino | Automatic Estimation of Speaking Rate in Multilingual Spontaneous Speech[END_REF] for a study of automatic speech rate estimation on read and spontaneous speech). Figure 8 displays the accumulated number of vowels per second for the English parts of the MULTEXT and OGI-MLTS corpus. Spontaneous speech leads to much more variation in terms of number of vowels per second than read speech. The Table XI shows the standard deviations of the speech rate approximation on spontaneous and read speech for different languages (45 s. spontaneous speech utterances of the OGI-MLTS corpus and 20 s. read utterances from the MULTEXT corpus). These standard deviation values show that there is a much greater dispersion of spontaneous speech rate within each language than for read speech. These intralanguage variations can explain why our models achieve a poor performance on the test part of the corpus. We believe nonetheless that our system can be applied, at least on groups of languages, to investigate if the groups considered can be automatically distinguished prosodically. We carried out experiments with different Arabic dialects to show how the features described in this paper help to classify them.

The corpus ARABER has been recorded at the Dynamique du Langage Laboratory in Lyon, France. It consists of semispontaneous recordings (comments on an image book) from 40 speakers from Maghreb, Middle-East and an intermediate area (Tunisia, Egypt). The mean duration for each speaker's recording is 5 minutes, in 40 files of 7.6 seconds. All the data have been used both for learning and testing, via a crossvalidation procedure.

The quality of the recordings made this corpus interesting because it is intermediate between the studio-recorded read speech corpus MULTEXT and the telephone spontaneous speech of the OGI corpus.

As research on the prosody of Arabic dialects is emerging, very few observations are available to hypothesise how much they differ. At this point, Arabic dialects are classified according to inter-comprehension between speakers, resulting in 3 main areas: Occidental (Moroccan, Algerian), Intermediate (Tunisian, Egyptian) and Oriental (Lebanese, Jordanian, Syrian). The aim of this study is to see, with an ALI system that does not require any kind of annotation, if it is possible to identify the hypothesised dialectal areas using only prosody.

The prosodic ALI system -using the combination of the long and short-term models -has been applied to this corpus without any tuning procedure: same features (baseline labels for the long term model and the combination of residue, energy and duration features for the short-term model), same n-gram configuration. Experiments are made according to a crossvalidation procedure applied on each speaker: learning is done using all speakers except one who is used for the test. This is repeated until all speakers have been used for the test. Results of the cross-validation tests are displayed in Table XII. The system performs very well on this data, which shows that prosodic differences may be important between the hypothesised dialectal areas of Arabic. Further studies are needed in order to identify the exact prosodic differences between dialectal areas, and if there are differences among dialects of a same area.

VIII. CONCLUSIONS AND PERSPECTIVES

Experiments on read speech show that our system is able to automatically identify languages using prosody alone. Differences between languages seem more characterised by microprosodic events (short term) than macro-prosodic ones. The experiments show that variations of fundamental frequency, energy and segment duration that occur within a syllable are more characteristic. The dynamic modelling allows to reach 83% of correct identification on a seven language discrimination task. Results tend to confirm the existence of automatically identifiable rhythmic classes (accuracies above 90% for rhythm class identification).

Considering spontaneous speech, accuracies are lower. This can be partly explained by the greater inter-speaker variability due to the number of different prosodic realizations allowed by spontaneous speech, especially in terms of changes in speech rate. The results remain however interesting for the language class identification experiment.

An applicative example has been shown with the experiments on Arabic dialects, where the speech quality is intermediate between read and spontaneous. This experiment has shown that there exist some automatically detectable prosodic differences between hypothesised dialectal areas of Arabic. A careful study with the help of linguists is needed in order to define precisely what are those differences and where they appear. The next experiment will be to test if the dialects can be automatically clustered using our system.

The main advantage of our prosodic ALI system lies in the fact it does not require any manual annotations (especially phonetic annotations which are very time-consuming). Hence, the system can be directly applied to unknown data, and be used to evaluate if the prosodic differences between languages or dialects can be automatically detected. Using this system can help linguists to verify that further investigation is needed, leading to new collaborations between the automatic processing and the linguistic communities.

Fig. 1 .

 1 Fig. 1. Result of the automatic segmentation, vowel location and vocal activity detection on a French recording of the MULTEXT database. The sentence is: "les choux avaient été entièrement devorés par les limaces". "#" labels are for non-activity segments, "V" are for vocalic segments, other segments are labelled "C". Word boundaries are displayed for illustration purpose.

Fig. 3 .

 3 Fig. 3. Description of the system.

Fig. 4 .

 4 Fig. 4.Finding local minima for the sentence "les choux avaient été entièrement dévorés par les limaces". Local minima under the linear regression are displayed as a big dot.

  The example sentence is labelled in the following way: D.D.#.#.#.#.#.D.D.U.D.D.D.D.U.U.D.-U.#.#.D.D.U.D.U.D.D.U.D.#.#.#.#.#.#

Fig. 5 .

 5 Fig. 5. Extraction of the baseline for the sentence "les choux avaient été entièrement dévorés par les limaces". Previously found local minima are linked with a straight line.

Fig. 6 .

 6 Fig.6. Approximation of the residue for the sentence "les choux avaient été entièrement dévorés par les limaces". The residue is approximated by a linear regression for each segment.

Fig. 7 .

 7 Fig. 7. Approximation of the energy for the sentence "les choux avaient été entièrement dévorés par les limaces". The energy is approximated by a linear regression for each segment.

  DUs.DDl.#Ds.#Us.#Us.#Us.#Ds.DUs.-DDs.UUs.DDl.DUs.DUl.DDs.UUs.UDl.-DDs.UDs.#Us.#Us.DUl.DDs.UDl.DUs.-UDs.DUs.DDs.UDl.DDs.#Us.#Us.#Ds.-#Ds.#Ds.

Fig. 8 .

 8 Fig. 8. (a) Number of detected vowels as a function of time on English read speech, (b) Number of detected vowels as a function of time on English spontaneous speech

TABLE VI RHYTHM

 VI CLASSES IDENTIFICATION TASK (CORRECT=93.5 ± 4.1% (130/139 FILES)). RESULTS ARE DISPLAYED AS PERCENTAGES.

	reference\ identified	Stress-timed	Syllable-timed	Mora-timed
	Stress-timed	90	10	-
	Syllable-timed	2	98	-
	Mora-timed	10	-	90

TABLE X RHYTHM

 X CLASSES IDENTIFICATION TASK (CORRECT=68.6 ± 9.1% (70/102 FILES)). RESULTS ARE DISPLAYED AS PERCENTAGES.

	reference\ identified	Stress-timed	Syllable-timed	Mora-timed
	Stress-timed	85	11	4
	Syllable-timed	50	46	4
	Mora-timed	16	31	53

TABLE XI STANDARD

 XI DEVIATIONS OF SPEECH RATE (ESTIMATION) FOR DIFFERENT

		LANGUAGES ON READ AND SPONTANEOUS SPEECH
	Lang.	Eng	Fre	Ger	Ita	Jap	Man	Spa	All
	Read	0.36	0.35	0.37	0.56	0.42	0.49	0.40	0.50
	Spont.	0.77	0.93	0.80	n.d.	0.98	0.77	0.81	0.85
		VII. EXPERIMENTS ON ARABIC DIALECTS

TABLE XII ARABIC

 XII DIALECTAL AREAS IDENTIFICATION (CORRECT= 98.0 ± 0.6% (1563/1592 FILES). RESULTS ARE DISPLAYED AS PERCENTAGES.

	identified\ reference	Occidental	Intermediate	Oriental
	Occidental	99.5	-	0.5
	Intermediate	1.8	96.0	2.2
	Oriental	1.0	0.3	98.7


Evelyne Hubert
email: evelyne.hubert@inria.fr

George Labahn
email: glabahn@uwaterloo.ca

Rational invariants of scalings from Hermite normal forms

Keywords: Matrix normal form, Group actions, Rational invariants, Symmetry reduction AMS Classification: 08-04 12-04 14L30 15-04

Scalings form a class of group actions on affine spaces that have both theoretical and practical importance. A scaling is accurately described by an integer matrix. Tools from linear algebra are exploited to compute a minimal generating set of rational invariants, trivial rewriting and rational sections for such a group action. The primary tools used are Hermite normal forms and their unimodular multipliers. With the same line of ideas, a complete solution to the scaling symmetry reduction of a polynomial system is also presented.

INTRODUCTION

Scalings form a simple class of group actions: they are diagonal actions of a torus on an affine space. For example, [(µ, ν), (z1, z2, z3, z4, z5)] → (µ 6 z1, ν 3 z2, ν µ 4 z3, µ ν 4 z4, µ 3 ν 3 z5)

describes the action of the group (R * ) 2 , with coordinates (µ, ν), on R 5 , with coordinates (z1, z2, z3, z4, z5). The action simply rescales each individual coordinate. One can check that the three rational functions

g1 = z1z 2 2 z 2 3 z 2 4 , g2 = z 3 2 z 2 4 z1z3 , g3 = z2z4z5 z 2 1 z 2 3
are left invariant by any of the above transformation determined by (µ, ν). They actually form a generating set of invariants of the scaling: they have the property that any other rational invariant f can be written as a rational function of them. In fact they have an even stronger property: the rewriting is given by a simple substitution. Indeed, if f (z) is a rational invariant then f (z1, z2, z3, z4, z5) = f g1 -1 , g2, g1, g2 -1 , g3 .

Providing a generating set of rational invariants along with an associated rewriting substitution for any given scaling is the first goal of the present article.

Though simple, scalings and their invariants have considerable practical importance. On the theoretical front scalings are known as torus actions and play a major role in algebraic geometry and combinatorics. Besides they underlie what is known as dimensional analysis with the invariants giving the dimensionless quantities needed to derive physical laws [START_REF] Birkhoff | Hydrodynamics: A study in logic, fact and similitude[END_REF][START_REF] Bridgman | Dimensional Analysis[END_REF][START_REF] Huntley | Dimensional Analysis[END_REF]. Dimensional analysis has been automated in the works [START_REF] Ishida | Formula processing on physical systems[END_REF] and [START_REF] Khanin | Dimensional Analysis in Computer Algebra[END_REF]. Central to this is the Buckingham-πtheorem. A reinterpretation of it states that a fundamental set of invariants is obtained from the basis of the nullspace of a matrix of exponents of the scaling [START_REF] Olver | Applications of Lie Groups to Differential Equations[END_REF]Section 3.4]. A second use of scalings is that they give mathematical sense to the rule of thumb used to reduce the number of parameters in biological models [START_REF] Murray | [END_REF][START_REF] Lin | Mathematics applied to deterministic problems in the natural sciences[END_REF]. This reduction by scaling symmetry of dynamical or polynomial systems was previously studied in [START_REF] Hubert | Polynomial Time Nondimensionalisation of Ordinary Differential Equations via their Lie Point Symmetries[END_REF][START_REF] Lemaire | A method for semi-rectifying algebraic and differential systems using scaling type Lie point symmetries with linear algebra[END_REF][START_REF] Sedoglavic | Reduction of algebraic parametric systems by rectification of their affine expanded lie symmetries[END_REF].

In this paper we go further in this direction than handled in the previous cited works. In particular we produce invariants which are rational functions, that is which do not involve any square roots or other fractional powers of the variables. In addition we provide trivial rewrite rules for our generating set of invariants. By this we mean that we give explicit substitution rules for rewriting any rational invariant (and actually any smooth invariant) in terms of the generating set. Again, this operation is performed without introducing any radicals.

Algorithmic tools for finding generating rational invariants and rewrite rules for the general class of rational actions of an algebraic group typically require Gröbner bases computations [START_REF] Müller-Quade | Calculating generators for invariant fields of linear algebraic groups[END_REF][START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF][START_REF] Kemper | The computation of invariant fields and a new proof of a theorem by Rosenlicht[END_REF]. A rewriting substitution can be achieved provided we allow algebraic functions [START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF].

In the case of scaling we show that a unimodular multiplier for the Hermite normal form of the integer matrix of exponents contains even further information. The unimodular multiplier provides a basis for the integer lattice of vectors in the kernel of the matrix of exponents. This basis actually describes rational invariant given as Laurent monomials (that is, monomials where we allow negative powers). We

show that these invariants form a generating set for the field of rational invariants. It is furthermore a minimal such set.

In fact we show more than the generation property. We also provide a simple method to rewrite any invariant in terms of these monomials via variable substitution. The substitution is read off from the inverse of the unimodular multiplier.

The triviality of the rewrite rules actually reflects the existence of a rational section to the orbits of the action. The equation of the section can be read off the unimodular multiplier, something of independent theoretical interest in the area of group actions. The unimodular multiplier for the Hermite form of the matrix of exponents is not unique. We give a construction for a canonical unimodular multipler which allows us to pinpoint the simplest rational sections.

In order to show a practical application of the new tools offered we address and solve a symmetry reduction problem. The knowledge of some symmetry of the solution set of a polynomial system brings hope that we can reduce the size of the problem by factoring out the symmetry. With a generating set and rewrite rules at hand we can indeed write the reduced system. The new variables are the generating invariants. We have here a minimal set of those and thus the number of variabes and the dimension of the solution set is exactly reduced by the dimension of the group. In the symmetry reduction business, a more subtle task is actually to retrieve the solution of the original system from the solution of the reduced system. In the case of scaling we show how to parameterize all the toric solutions of the original system from the solutions of the reduced system.

INTEGER MATRIX NORMAL FORMS

In this section we provide the basic information about the Hermite normal form of a matrix of integers and its unimodular multiplier. We propose a canonical unimodular multiplier that is relevant in providing a simple rational section to the orbits of a scaling. (ii) h k,j = 0 for k > ij;

Hermite Normal Forms

(iii) 0 ≤ h i j ,k < hi j ,j when j < k.

Thus a matrix is in column Hermite normal form if the submatrix formed by the pivot rows i1, • • • , ir and the first r columns is upper triangular and that all nonzero elements of the pivot rows are positive and less than the corresponding (positive) diagonal entry. The integer r is the rank of the matrix. By changing column to row and row to column indices in (ii) and (iii) one obtains the row Hermite Normal Form of a matrix of integers.

Every integer matrix can be transformed via integer column operations to obtain a unique column Hermite form. The column operations are encoded in unimodular matrices, that is, invertible integer matrices whose inverses are also integer matrices. Thus for each A there exists a unimodular matrix V such that A • V is in Hermite normal form. Similar statements also hold for the row Hermite normal form. We refer the reader to [START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF] for more information on such forms.

When A ∈ Z r×n , with r ≤ n, has full row rank r then there exists a unimodular matrix V such that

A • V = [H, 0] with H ∈ Z r×r of full rank. (1)
If W ∈ Z n×n is the inverse of V then we can partition V and W as

V = [V i , Vn] with V i ∈ Z n×r and Vn ∈ Z n×(n-r) (2)
and

W = Wu Wd with Wu ∈ Z r×n and Wd ∈ Z (n-r)×n . ( 3
)
We then have

In = W V = WuV i WuVn WdV i WdVn (4)
In = V W = V i Wu + VnWd . (5)
Note that the blocks of V provide the Hermite normalization of the blocks of W since from (4) we have

Wu[V i , Vn] = [Ir, 0] and Wd[Vn, V i ] = [In-r, 0].
We state a known properties of Hermite normal forms [START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF] in a way that is needed later in the paper.

Lemma 2.2 Let A ∈ Z r×n be a full row rank matrix and V ∈ Z n×n a unimodular matrix such that AV = [ H, 0] with H ∈ Z r×r . If V is partitioned as in (2), then the columns of Vn form a basis for the integer lattice defined by the kernel of A.

Normal unimodular multiplier

For the problem of interest in this paper the number of columns is larger than the rank. In this case the unimodular multiplier is not unique. Indeed, with the partition V = [V i , Vn] as in [START_REF] Birkhoff | Hydrodynamics: A study in logic, fact and similitude[END_REF], any column operation using the columns of Vn do not affect the Hermite form H for the initial matrix A and hence results in a different unimodular multiplier V . In this subsection we describe a normalization of the multiplier V which is both simple and unique. Previous work on determining unique unimodular multipliers includes that of [START_REF] Havas | Extended gcd and Hermite normal form algorithms via lattice basis reduction[END_REF] for integer matrices where the unimodular multiplier is reduced via lattice reduction. We favor the component Vnto be in Hermite normal form, as in [START_REF] Beckermann | Normal forms for general polynomial matrices[END_REF], which deals with polynomial matrices. We indeed prefer that the component Vn be in The triangular form obtained is useful for our application.

Theorem 2.3 Suppose A ∈ Z r×n has full row rank. Then there exists a unique unimodular matrix V such that

(a) A • V = [H, 0] with H ∈ Z r×n in column Hermite nor- mal form, (b) V = [V i , Vn] with Vn ∈ Z n×(n-r) in column Hermite normal form, (c) If i1 < i2 < • • • < in-r are the pivots rows for Vn then for each 1 ≤ j ≤ n -r : 0 ≤ [V i ] i j ,k < [Vn]i j ,j for all 1 ≤ k ≤ r.
That is, V i is reduced with respect to the pivots rows of Vn.

Proof. The existence of a unimodular matrix V satisfying (a) and (b) follows directly from the existence of column Hermite forms. The reduction (c) follows by doing the column operation

[V i ] i j ,k ← [V i ] i j ,k -q•[Vn]i j ,j with q = iquo([V i ] i j ,k , [Vn]i j ,j )
for each k as j varies from column nr to 1. Here iquo denotes integer quotient, a function which always results in a nonnegative remainder.

It remains to show that any V satisfying (a), (b) and (c) is unique. Thus we suppose the contrary and assume that we have

A • V = A • V * = [H, 0] with V = [V i , Vn] and V * = [V * i , V * n ]
both being unimodular and satisfying (a), (b) and (c). Since both Vn and V * n form a basis for the kernel (over Z) of A there exists an integer matrix U * such that Vn = V * n • U * . The uniqueness of column Hermite forms then implies that U * = I and so Vn = V * n .

Finally, in order to show

V i = V * i we first notice that V i -V * i is in the kernel of A.
Since the columns of Vn form a basis for this kernel, there exists an integer matrix U such that

V i -V * i = Vn • U .
Looking at the last pivot row of Vn (row in-r) and using condition (c) we have that for each 1 ≤ k ≤ r:

[V i ] i n-r ,k -[V * i ] i n-r ,k = [Vn]i n-r ,n-r • u n-r,k . From condition (c) we have that both [V i ] i n-r ,k and [V * i ] i n-r
,k are positive integers smaller than [Vn]i n-r ,n-r . Thus u n-r,k = 0 for all k and hence the last row of U is zero. Suppose now that rows n-r, . . . , ℓ+1 of U are all zero. Then for the pivot row i ℓ the triangular property of the Hermite form implies that for each k we have

[V i ] i ℓ ,k -[V * i ] i ℓ ,k = [Vn] i ℓ ,ℓ • u ℓ,k .
As before, the size condition (c) implies that u ℓ,k = 0 for all k and hence row ℓ of U is zero. By induction we see that while the normalized unimodular multiplier is

U = 0. Hence V i = V * i and so V = V * is unique. ✷ Example 2.4 Let A = 8
V =      -1 -2 -2 -2 -1 -3 -14 -7 -13 -7 1 1 2 1 0 0 2 0 3 0 0 1 0 0 2      .

SCALINGS

Scalings can be described through the matrix of exponents of the group parameters as they act on each component. Similar descriptions are used for toric ideals [START_REF] Sturmfels | Gröbner bases and convex polytopes[END_REF]. In this section we describe the matrix forms and properties that are useful when representing scalings and computing their invariants.

Matrix notations for monomial maps

If a = [a1, . . . , ar] T is a column vector of integers and λ = [λ1, . . . , λr] is a row vector with entries in K * , then λ a denotes the scalar

λ a = λ a 1 1 • • • λ ar r . If λ = [λ1, . . . ,
λr] is a row vector of r indeterminates, then λ a can be understood as a monomial in the Laurent polynomial ring K[λ, λ -1 ], a domain isomorphic to K[λ, µ]/(λ1µ1 -1, . . . , λrµr -1). We extend this notation to matrices: If A is an r × n matrix then λ A is the row vector

λ A = [λ A •,1 , • • • , λ A•,n ]
where A•,1, . . . , A•,n are the n columns of A.

A = [λ A i , λ An ], (b) λ AB = (λ A ) B , (c) (y ⋆ z) A = y A ⋆ z A . (d) λ A+B = λ A ⋆ λ B
Proof. Part (a) follows directly from the definition of λ A . For part (b) we have for each component j, 1 ≤ j ≤ t:

[(λ A ) B ]j = n i=1 [λ A ] b ij i = n i=1 ( r ℓ=1 λ a ℓi ℓ ) b ij = r ℓ=1 ( n i=1 λ a ℓi b ij ℓ ) = r ℓ=1 ( λ n i=1 a ℓi b ij ℓ ) = [λ AB ]j .
For part (c) one simply notices that for each j we have

[(y ⋆ z) A ]j = r i [y ⋆ z] a i,j i = r i y a i,j i • z a i,j i = [y A ]j[z A ]j = [y A ⋆ z A ]j.
The proof of (d) follows along the same lines. ✷

Scalings in matrix notation

We consider an algebraically closed field K of characteristic zero, the multiplicative group of which is K * . The rdimensional torus is the Abelian group (K * ) r . Its identity is 1r = (1, . . . , 1) and the group operation is componentwise multiplication, which we denoted ⋆.

Definition 3.2 Let A be a r × n integer matrix: A ∈ Z r×n . The associated scaling is the linear action of T = (K * ) r on the affine space K n given by

(K * ) r × K n → K n (λ , z) → λ A ⋆ z. (6)
With the notations introduced above we have that

λ A ⋆ z = [λ A •,1 z1, . . . , λ A•,n zn]
with A•,1, . . . , A•,n being the n columns of A. Thus for each j = 1, . . . , n the action scales the j th component zj by the power product λ

a 1,j 1 • • • λ a r,j r
. The axioms for a group action are satisfied thanks to Proposition 3.1:

1r ⋆ z = z and (λ ⋆ µ) A ⋆ z = λ A ⋆ (µ A ⋆ z).
There is no loss of generality in assuming that A has full row rank. Indeed, we can view the scaling defined by A as a diagonal representation of (K * ) r on the n dimensional space

K n : (K * ) r → Dn (λ1, . . . , λr) → diag(λ A )
where Dn is the group of invertible diagonal matrices. This in turn can be factored by the group morphism from (K * ) r to (K * ) n defined by A. This is given explicitly by:

ρ(A) : (K * ) r → (K * ) n (λ1, . . . , λr) → λ A Suppose now that U A = B 0 is a row Hermite form for
A with unimodular row multiplier U . Writing U = U1 U2 where U1A = B is of row dimension d we have that U2A = 0. Then

(K * ) d × (K * ) r-d U -→ (K * ) r A -→ (K * ) n µ2) → µ U 1 1 ⋆ µ U 2 2 → (µ U 1 1 ⋆ µ U 2 2 ) A = µ B 1 .
Since U is unimodular, ρ(U ) is an isomorphism of groups and the image of (K * ) r by ρ(A) is equal to the image of (K * ) d by ρ(B).

RATIONAL INVARIANTS

Consider a full row rank matrix A ∈ Z r×n which defines an action of the torus T = (K * ) r on K n . A rational invariant is an element f of K(z) such that f (λ A ⋆ z) = f (z). Rational invariants form the subfield K(z) T of K(z). In this section we show how a unimodular multiplier V , where A • V is the Hermite normal form, provides us with a complete description of the subfield of rational invariants. From V we shall extract

• nr generating rational invariants, which are actually Laurent monomials,

• a simple rewriting of any rational invariant in terms of this generating set,

• a rational section to the orbits of the scaling.

We thus go much further than the group action transcription of the Buckingham π-theorem of dimensional analysis [START_REF] Birkhoff | Hydrodynamics: A study in logic, fact and similitude[END_REF][START_REF] Olver | Applications of Lie Groups to Differential Equations[END_REF]. This latter takes any basis of the nullspace of the matrix A and provides a set of functionally generating invariants, some of which could involve fractional powers. In the present approach, only integer powers are involved. This spares us the determination of proper domains of definition. Furthermore, the Buckingham π-theorem gives no indication on how to rewrite an invariant in terms of the generators produced. The rewriting we propose is a simple substitution. This is reminiscent of the normalized invariants appearing in [START_REF] Fels | Moving coframes. ii. Regularization and theoretical foundations[END_REF][START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF][START_REF] Mansfield | A Practical Guide to the Invariant Calculus[END_REF] (or replacement invariants in [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF]). And indeed, using the terminology of those articles, we are in a position to exhibit a global cross-section (of degree one) to the orbits of the scaling. Note though, that the substitution is again rational: we do not introduce any algebraic functions.

Generating and replacement invariants

A Laurent monomial z v is a rational invariant if (λ A ⋆ z) v = z v
and therefore if and only if Av = 0. The following theorem shows that rational invariants of a scaling can be written as a rational function of Laurent monomials that are invariants.

Lemma 4.1 Suppose p q ∈ K(z) T , with p, q ∈ K[z] relatively prime. Then there exists u ∈ Z n such that

p(z) = v ∈ kerA ∩ Z n av z u+v and q(z) = v ∈ kerA ∩ Z n bv z u+v
where the families of coefficients, (av) v and (bv)v, have finite support. 1 Proof. We take advantage of the more general fact that rational invariants of a linear action on K n are quotients of semi-invariants (see for instance [START_REF] Popov | Invariant Theory[END_REF]Theorem 3.3]). Indeed, if p/q is a rational invariant, then we have

p(z) q(λ A ⋆ z) = p(λ A ⋆ z) q(z) in K(λ)[z].
As p and q are relatively prime, p(z) divides p(λ A ⋆ z) and, since these two polynomials have the same degree, there exists χ(λ) ∈ K(λ) such that p(λ A ⋆ z) = χ(λ) p(z). It then also follows that q(λ A ⋆ z) = χ(λ) q(z).

Let us now look at the specific case of a scaling. Then

p(z) = w ∈ Z n aw z w ⇒ p(λ A ⋆ z) = w ∈ Z n awλ Aw z w .
For p(λ A ⋆ z) to factor as χ(λ)p(z) we must have Aw = Au for any two vectors u, w ∈ Z n with av and au in the support of p. Let us fix u. Then wu ∈ ker A and χ(λ) = λ Au . From the previous paragraph we have w ∈ Z n bwλ Aw z w = q(λ A ⋆ z) = λ Au q(z) = λ Au w ∈ Z n bw z w . Thus Au = Aw 1 In particular av = 0 (respectively bv = 0) when u + v / ∈ N n .

and therefore there exists v ∈ ker A∩Z n such that w = u+v for all w with bw in the support of q. ✷

The set of rational functions on K n that are invariant under a group action form a subfield of K(z) and, as such, it is a finitely generated field. In the case of a scaling the generators of this field can be constructed making use only of linear algebra and the representations of rational invariants given in Lemma 4.1. Proof. Observe first that the components of g are invariants. Indeed the columns of Vn span kerA and so λ A ⋆ z Vn = λ AVn ⋆z Vn = z Vn . We shall prove that any rational invariant can be rewritten in terms of these components.

Since V and W are inverses of each other we have In = V i Wu+VnWd. Thus z = z V i Wu+VnW d , where z = [z1, . . . , zn] T , the vector of degree 1 monomials. More generally, for any

v ∈ Z n , z v = z (V i Wu+VnW d )v . If now v ∈ kerA ∩ Z n then z v = z VnW d v = g W d v since ker A ⊂ ker Wu.
The representation given in Lemma 4.1 implies that any p q ∈ K(z) T , with p, q ∈ K[z] relatively prime, has the form

p(z) = v ∈ kerA ∩ Z n av z u+v and q(z) = v ∈ kerA ∩ Z n bv z u+v
for some u ∈ Z n . As elements of K(z), we can rewrite these as

p(z) = z u v∈kerA ∩ Z n av z VnW d v q(z) = z u v ∈ kerA ∩ Z n bv z VnW d v and so p(z) q(z) = p z VnW d q (z VnW d ) = p g W d q (g W d ) .
✷ Both V and W are needed for computing invariants and rewrite rules. Since a V matrix is produced from a matrix of column operations which convert A to column Hermite form, the W matrix can be computed simultaneously with minimal cost by the inverse column operations. A unimodular multiplier for its Hermite normal form is

V = -1 3 1 -2 with inverse W = 2 3 1 1 .
It follows that g = x 3 y 2 is a generating invariant. Any other rational invariant can be written in terms of g with the substitution x → g, y → g. Example 4.4 In order to illustrate the simplicity of our method let us return to the example in the introduction.

Consider the 2 × 5 matrix A given by

A = 6 0 -4 1 3 0 3 1 -4 3
which defines the group action mentioned in the introduction. Thus if z = (z1, z2, z3, z4, , z5) and λ = (µ, ν) then the group action defined by A is given by

λ A ⋆ z = ( µ 6 z1, ν 3 z2, ν µ 4 z3, µ ν 4 z4, µ 3 ν 3 z5).
The column Hermite normal form for A is given by [H, 0] = 3 2 0 0 0 0 1 0 0 0 and the normal unimodular multiplier and its inverse are

V =      1 1 2 1 0 1 0 -1 2 0 1 1 3 2 1 1 0 0 2 1 0 0 0 0 1      , W=      2 -2 -2 3 -1 0 3 1 -4 3 0 -1 0 1 -1 -1 1 1 -1 0 0 0 0 0 1      .
Here the last 3 rows of Vn are the pivot rows. A generating set of invariants is given by the components

(g1, g2, g3) = z Vn = z 2 1 z 3 3 z2 , z1z

Rational section to the orbits

The fact we can rewrite any invariant in terms of the generating set by a simple substitution actually reflects the existence and intrinsic use of a rational section [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF][START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF]. And indeed, any unimodular multiplier for the Hermite normal form provides a rational section. The simplest rational sections are uncovered by the normal unimodular multipliers of Theorem 2.3.

An irreducible variety P ⊂ K n is a rational section for the rational action of an affine algebraic group if there exists a nonempty Zariski open subset Z ⊂ K n such that any orbit of the induced action on Z intersects P at exactly one point [21, Section 2.5].

Every vector a ∈ Z r can be uniquely written as a = a + -a - where a + and a -are nonnegative and have disjoint support. Their components are:

[a + ]i = ai if ai ≥ 0 0 otherwise and [a -]i = ai if ai ≤ 0 0 otherwise.
This can be extended to r × n matrices by

A + = [(A.,1) + , • • • , (A.,n) + ] and A -= [(A.,1) -, • • • , (A.,n) -].
Theorem 4.5 With the hypotheses of Theorem 4.2, the variety P of (z

V + i -z V - i ) :
z ∞ is a rational section for the scaling defined by A. The intersection of the orbit of a point z ∈ (K * ) n with this section is the point z VnW d .

Proof. The matrix Wd is full row rank and Wd •[Vn, V i ] = [In-r, 0]. By Lemma 2.2 the columns of V i span the lattice kernel of Wd. Thus the kernel of

K[z] → K[x, x -1 ] z → x W d .
is the prime (toric) ideal Assume z ∈ (K * ) n . For z = λ A ⋆ z to be on the variety P of P the components of zV i need to all be equal to 1.

P = z V + i -z V - i : (z1 . . . zn) ∞ of dimension r [
Thus

λ AV i = z -V i , that is, λ H = z -V i .
Because of the triangular structure of H we can always find λ ∈ (K * ) r satisfying this equation. For any such λ we then have z =

λ A ⋆ z V i Wu+VnW d since V i Wu + VnWd = In and so z = λ HWu ⋆ z V i Wu+VnW d = z -V i Wu ⋆ z V i Wu+VnW d = z VnW d by Proposition 3.1.
Thus the intersection of the orbit of z with the variety of P exists, is unique and equal to z VnW d . ✷

From this description we deduce that the invariants z VnW d are actually the normalized invariants as defined in [START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF]. As such the rewriting of Theorem 4.2 applies to the more general class of smooth invariants. Furthermore, if the Hermite form of A is Ir there is a global moving frame for the group action and z VnW d correspond to the normalized invariants as originally defined in [START_REF] Fels | Moving coframes. ii. Regularization and theoretical foundations[END_REF].

Example 4.6 Consider the scaling given by

(z1, z2, z3, z4, z5) → ( η ν 3 z1, η µ z2, ηz3, ν ηµ z4, ην µ z5)
an example used to illustrate dimensional analysis in [START_REF] Olver | Applications of Lie Groups to Differential Equations[END_REF].

In this case the matrix of exponents is

A =   -3 1 1 -1 1 0 -1 0 -1 -2 1 0 0 1 1   .
The normal unimodular multiplier and its inverse are

V =      0 0 1 -1 -1 0 -1 0 -1 -2 1 1 3 -1 -2 0 0 0 1 0 0 0 0 0 1      , W =      -3 1 1 -1 1 0 -1 0 -1 -2 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1      .
Thus the rewrite rules are simply z → g W d = (1, 1, 1, g1, g2). By Theorem 4.5 the associated rational section is the variety

(z3 -1, z3 -z2, z 3 3 -z1) : z ∞ .
Simple combinations of the ideal generators show that this ideal is equal to (z1 -1, z2 -1, z3 -1).

Example 4.3 illustrates a case where things are particularly simple. Namely, the simplest case for the normalization of the unimodular multiplier V occurs when the pivot rows of Vn are the rows of an (n-r)-identity matrix. Assuming that the pivot rows appear at the end, a situation that can be arranged by permuting the columns of A and therefore the order of the original variables, then the normal unimodular multiplier and its inverse are

V = V * i V * n 0 In-r and W = V * i -1 -V * i -1 V * n 0
In-r .

The rewrite rules are then: z → g W d = (1, . . . , 1, g1, . . . , gn-r) which indicates that the equations for the section can be made simpler than in Theorem 4.5.

Proposition 4.7 If the canonical unimodular multiplier V of A for its Hermite normal form is

V = V * i V * n 0 In-r (7)
then the variety of (z1 -1, . . . , zr -1) is a rational section to the scaling defined by A. There are then nr generating invariants g * r+1 , . . . , g * n s.t. any other rational invariants can be written in terms of those with the substitution (z1, . . . , zn) → (1, . . . , 1, g * r+1 , . . . , g * n ).

The proof proceeds by taking the power (V * i ) -1 of (z

V + i - z V - i ).
The components then belong to the ideal generated by the components of (z V + i -z V - i ) and factor as a product of (z-1n) with a monomial in z. Then (1, . . . , 1, g * r+1 , . . . , g

* n ) = z Vn•W d = (1r, z Vn ) = (1r, g).
Note that the form [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF] is the only possibility for the nr bottom rows of V i to be zero. Indeed, since this implies that the nr bottom rows of Vn form a unimodular matrix, and, since it is in Hermite form, it can only be the identity.

REDUCING POLYNOMIAL SYSTEMS

If the solution set of a polynomial system of equations is invariant under a group action, then there is an equivalent system given in terms of invariants of this group action [START_REF] Olver | Applications of Lie Groups to Differential Equations[END_REF]. The equivalent system written in terms of a generating set of invariants is the reduced system. However, for general symmetry reductions a further problem is to recover the solutions of the original system from the solutions of the reduced system.

In this section we show how to fully work out a symmetry reduction for a scaling symmetry. If the scaling symmetry is rdimensional, then the reduced system has r fewer variables. In addition, we show how to retrieve all toric solutions of the original system from the toric solutions of the reduced system. We shall indeed discount the solutions for which there is a zero component. This is a relevant case. For instance, in a chemical reaction or a population dynamics model we look for the equilibria where no species disappears.

We consider a set of equations p1(z) = 0, . . . , pm(z) = 0 where p1, . . . , pm are in K[z] = K[z1, . . . , zn] or even in the Laurent polynomial ring K[z, z -1 ] since we are concerned with solutions in (K * ) n . For convenience we introduce the map p = (p1, . . . , pm) and write the system of equations as p(z) = 0. Definition 5.1 The matrix A ∈ Z r×n defines a scaling symmetry for the polynomial system p(z) = 0 if, for a given z ∈ (K * ) n , we have

p(z) = 0 ⇒ p(λ A ⋆ z) = 0, ∀λ ∈ (K * ) r . (8)
In the following we suppose that A ∈ Z r×n defines a scaling symmetry for the polynomial system p(z) = 0. Appendix A provides a way of determining some of these symmetries. Then V is a unimodular multiplier such that A • V is the Hermite normal form of A, and W is the inverse of V . The invariantization of p ∈ K[z, z -1 ] associated to a choice of V is a Laurent polynomial q in nr variables (y1, . . . , yn-r) defined by q(y) = f y W d . From Theorem 4.2 we know that if p is invariant then p(z) = q(g) where g = z Vn . Yet we do not restrict invariantization to invariants as there is no need for the polynomials defining the symmetric system to be invariant.

Proposition 5.2 Let q1, . . . , qm in K[y, y -1 ] be defined as qi(y) = pi y W d . If y ∈ (K * ) n-r is a solution of q(y) = 0, then for all λ ∈ (K * ) r , λ A ⋆ y W d is a solution of p(z) = 0.

The Laurent polynomials q1, . . . , qm form the reduced system. This reduced system has r fewer variables than the original system. As described in the above proposition, any point on its solution set provides a parameterized rdimensional set of solutions for the original system. Proposition 5.2 is an immediate result of the symmetry condition [START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF]. The following result is a stronger assertion: any toric solution of the original system can be obtained that way.

Theorem 5.3 Assume that A ∈ Z r×n defines a scaling symmetry for the polynomial system p(z) = 0 and that q(y) = 0 is the reduced system. Then for any z ∈ (K * ) n satisfying p(z) = 0 there exists λ ∈ (K * ) r and y ∈ (K * ) n-r such that q(y) = 0 and z = λ A ⋆ y W d .

Proof. Assume z ∈ (K * ) n satisfies p(z) = 0. Since H is triangular and nonsingular, there exists λ ∈ (K * ) r such that λ

H = z -V i . Set y = z Vn . Since λ [H,0] = z -V i , 1n-r we have λ A ⋆ z [V i ,Vn] = λ [H,0] ⋆ (z V i , z Vn ) = (1r, y).
Taking both sides of the above equality to the power W gives

λ A ⋆ z = λ A ⋆ z V •W = (1r, y)   Wu Wd   = y W d .
By the symmetry hypothesis p y W d = p(λ A ⋆ z) = 0. Thus q(y) = 0. ✷ There is a geometric interpretation for the above approach that stems out of the work of [START_REF] Fels | Moving coframes. ii. Regularization and theoretical foundations[END_REF][START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF][START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF]. Namely, the solution set of the reduced system describes the projection, along the orbits, of the original solution set on the section z V i = 1.

From the above proof it is clear that the group element λ ∈ (K * ) r providing the link between the solution of the original system and the solution of the reduced system is unique if and only if the Hermite normal form is the identity.

APPENDIX A. FINDING SCALING SYMMETRY OF A POLYNOMIAL SYSTEM

Suppose we have m equations of the form

p k (z) ≡ c k,0 z α k,0 + c k,1 z α k,1 + • • • + c k,ℓ k z α k,ℓ k = 0
where z = (z1, . . . , zn). A sufficient condition for the solution set of this system to have a given group action as a symmetry is that the polynomials are semi-invariant for this group action. In the case of a scaling determined by a integer matrix A this condition is that p k (z) divides p k (λ A ⋆ z).

As we address only toric solutions, that is, solutions where no component is zero, we can work with Laurent polynomials and normalize all the equations by dividing out the first monomial. We get equations of the form

q k (z) ≡ c k,0 + c k,1 z β k,1 + • • • + c k,ℓ k z β k,ℓ k = 0 ( 9
)
where β k,j = α k,j -α k,0 for all k and all j > 0. The sufficient condition for the solution set to have a scaling symmetry is then that the Laurent polynomials q1, . . . , qm are invariants. Since

q k (λ A ⋆ z) = c k,0 + c k,1 λ Aβ k,1 z β k,1 + • • • + c k,ℓ k λ Aβ k,ℓ k z β k,ℓ k
The invariance condition q k (λ A ⋆z) = q k (z) results in λ Aβ In order to determine A let us assume that we have a matrix K and we are looking for a matrix A such that A • K = 0 with A of full row rank. That is, we look for a basis of the left nullspace of K, as a module over the integers.

If K has full column rank and we take transposes then we recognize the problem as one solved in Lemma 2.2. If K is not of full column rank then we can still reduce the problem via the technique described at the end of Subsection 3.2 (again taking transposes).

Thus one method to find left nullspace bases (after ensuring that K is of full column rank) is to use unimodular row operations U to determine

U • K = H 0 ( 10
)
with H of full row rank. If there are r rows of zeros on the right term in (10) then we can let A, the matrix of the scaling, be the last r rows of U . Note that, since U is unimodular, the resulting matrix A is also of full row rank.

Example A.1 Suppose K is given by

K =     -1 1 1 -1 0 1 2 0    
the kernel which comes from the polynomial system of equations in Example 5.4. Then a unimodular matrix which re-veals the rank of this matrix is given by

    0 -1 -1 0 -1 -1 -1 0 1 1 0 0 0 2 2 -1         -1 1 1 -1 0 1 2 0     =     -1 0 0 -1 0 0 0 0     .
A scaling matrix is thus

A = 1 1 0 0 0 2 2 -1 .
The alternate scaling used in [START_REF] Lemaire | A method for semi-rectifying algebraic and differential systems using scaling type Lie point symmetries with linear algebra[END_REF] when treating Example 5.4 is

A ′ = -2 0 2 -1 0 -2 -2 1 .
In this case A ′ = U • A where

U = -2 1 0 -1
and, since U is not unimodular, the action of the scaling described by A ′ has nontrivial isotropy.

When using a Hermite reduction, the rows of A form a basis for the integer lattice of the left kernel of K. Any other integer matrix A ′ whose rows are in the left kernel of K are of the form A ′ = U • A. The rows of A ′ then forms a basis for the left kernel of K if and only if U is unimodular.

Definition 2 . 1

 21 An m × n integer matrix H = [hij] is in column Hermite Normal Form if there exists an integer r and a strictly increasing sequence i1 < i2 < • • • < ir of pivot rows such that (i) The first r columns are nonzero;

2 15 9 11 6 0 6 2 3

 3 which has Hermite normal form [I2, 0]. The reduction performed by Maple results in the unimodular multiplier

  If x = [x1, . . . , xn] and y = [y1, . . . , yn] are two row vectors, we write x ⋆ y for the row vector obtained by component wise multiplication: x ⋆ y = [x1y1, . . . , xnyn] Proposition 3.1 Suppose A and B are matrices of size r × n and n × n, respectively, and that λ is a row vector with r components. Then (a) If A = [A i , An] is a partition of the columns of A, then λ

Theorem 4 . 2

 42 Let V = [ V i , Vn ] and W = Wu Wd be unimodular matrices of integers such that AV = [ H, 0 ] is in column Hermite normal form and W is the inverse of V . Then the scaling defined by A has the following properties: (a) The nr components of g = [z1, . . . , zn] Vn form a generating set of rational invariants; (b) Any rational invariant can be written in terms of the components of g by substituting z = [z1, . . . , zn] by the respective components of g W d .

Example 4 . 3

 43 Consider the scaling defined by A = 2 3 .

24 ,

 24 Lemma 4.1, 4.2 and 12.2].

  k,1 = • • • = λ Aβ k,ℓ k = 1 for all k. It implies that each β k,j is in the kernel of A. Thus A is the matrix having kernel K = [β1,1, . . . , β m,ℓm ].

We have shown how to reduce polynomial systems of equations by scaling symmetries. This can be extended to dynamical systems and, more generally, to the reduction of systems of differential and algebraic equations. We intend to report on our progress with this in a future publication.

Example 5.4 Consider the system of polynomial equations

presented in [START_REF] Lemaire | A method for semi-rectifying algebraic and differential systems using scaling type Lie point symmetries with linear algebra[END_REF]Example 3.14]. On one hand we can look for the solutions that have a zero component. They are part of the two-parameter family of solutions given by (0, 0, α, β).

On the other hand we can determine a scaling symmetry for this system with the method of Appendix A which gives

A unimodular multiplier V , and its inverse W , to obtain the Hermite normal form of A are

The reduced system is thus obtained by substituting (z1, z2, z3, z4) by (y1, y2)

The latter system has a solution set consisting of a single point. It provides a two parameter solution to the original system:

. By Theorem 5.3, any solution, without zero component, of the original system is obtained in this way. Since A • V = I2 0 , the pair (λ1, λ2) providing the given solution is unique. It can be read from the columns of

For the geometric interpretation note that the underlying rational section is the variety of (z1 -1, z2z4 -z1). One can check that the intersection of the solution set of the original system with this section is (1, 1) W d = (1, 1, 1, 1). Any element in the orbit of this point solves the original system.

The semi-rectified system obtained in [START_REF] Lemaire | A method for semi-rectifying algebraic and differential systems using scaling type Lie point symmetries with linear algebra[END_REF] is different than our reduced system. The process described there introduces square roots and the semi-rectified system has two solutions. This owes to the row-echelon form used. In our approach we get a clear connection between the toric solutions of the reduced system and of the original system. As we are free of fractional powers, we avoid having to pay attention to the sign of the components in the solution set.

Example 5.5 Consider the polynomial system of 3 equations in 5 variables given by

On one hand there is a three-parameter family of solutions given by (0, 0, α, β, γ). On the other hand, a symmetry of this system is given by the 2 × 5 matrix A of Example 4.4.

The reduced system

is obtained with the substitution:

The solution set of the above reduced system consists of the 4 points (2, 1, 3), (2, 3, 1), (3, 3+ √ 5, 3-√ 5) and (3, 3-√ 5, 3+ √ 5). In this case the underlying rational section is the variety of (z1z2z3z4-1, z2z4-1). The intersection of the solution set of the original system are the four points (2, 1, 3)

Any element in the orbits of these points is a solution of the original system. We thus have four parameterized two dimensional solution subsets. For example,

) is a parameterized two-dimensional subset of solutions. By Theorem 5.3, all solutions, without zero component, of the original system are obtained in this way.

CONCLUSION

In this paper we have made use of the Hermite Normal Form of the matrix of exponents of a scaling symmetry. Invariants, rewrite rules and rational section for a scaling are all determined from an associated unmimodular multiplier and its inverse. We have also illustrated how scaling can be used to reduce polynomial systems of equations. All the algorithms in this paper have been implemented in the computer algebra system Maple with the code available from the authors.

There are a number of research topics that follow from our work. The Hermite Normal Form is not the only rankrevealing or normalizing transformation of an integer matrix. Other possibilities include using the Smith Normal Form of the scaling matrix or lattice reduction basis (i.e. LLL) for the normal unimodular multiplier. We are interested in the invariants, rewrite rules and sections that result from using these alternate forms, in particular seeing when these are simpler than those that result from the use of the Hermite form.