Sagar Verma

Kavya Gupta
email: kavya.gupta100@gmail.com

Robustness of Neural Networks used in Electrical Motor Time-Series

Electrical motors are widely used in industrial and emerging applications such as electrical automotive. Industrial 4.0 has led to the usage of neural networks for electrical motor tasks like fault detection, monitoring, and control of electrical motors. The growing increase of neural networks in safety-critical systems requires an in-depth analysis of their robustness and stability. This paper studies the robustness of neural networks used in time-series tasks like system modeling, signal denoising, speed-torque estimation, temperature estimation, and fault detection. The dataset collected for these problems has all types of noise from the operating environment, sensors, and the system itself. This affects the performance of different network architectures during training and inference. We train and analyze under perturbations several different architectures that range from simple linear, convolutional and sequential networks to complex networks like 1D ResNet and Transformers.

Code is available at https://github.com/sagarverma/robust-motor.

Introduction

Electrical motors are one of the most used heavy devices in industrial and non-industrial places. In heavy industry, they can be found in cranes, tunnel boring machines, and trains, while at home, they can be found inside all electrical appliances like washing machines, fans, and rotational drives. Each of these applications requires different operating reliability from the motor used. These motors also have different types of operating environments and scenarios. A brushless DC motor inside a rotational drive has a consistent operating paradigm. In contrast, an induction motor inside a tunnel boring machine has to face extreme heat, humidity, and dust while having a very inconsistent operation cycle. Given the nature of the operation, it has been vital for the drive control community to use fault detection and observation methods (1; 2). Recently neural network based methods have been proposed for such tasks (3; 4; 5). The scale with which neural network based methods have been proposed for electrical motor tasks does not match the very much required robustness and stability analysis of such methods.

Figure 1 shows how naturally occurring perturbation in inputs can cause a neural network to give the wrong output. When such neural networks are cascaded to drive a control system, it can lead to catastrophic failures. In this case, meta-denoiser [START_REF] Verma | Neural speed-torque estimator for induction motors in the presence of measurement noise[END_REF] and speed-torque estimator [START_REF] Verma | Neural networks based speed-torque estimators for induction motors and performance metrics[END_REF] together take denoised currents and voltages and estimate speed and torque which can then be used to drive the control system. Currents and voltages are measured using sensors that can be affected by extreme heat, water, dust, or material faults. Sensors can also perform poorly due to aging. Motors can age and get affected due to their environment and will behave differently. Given that meta-denoiser and DiagBiRNN have not been trained on a dataset that considers such varied inputs and motor states, the networks are bound to give wrong predictions, which can affect the downstream task of control. In [START_REF] Verma | Modeling electrical motor dynamics using encoder-decoder with recurrent skip connection[END_REF], convolutional, feed-forward, and sequential neural networks have been used to model electrical motor dynamics by modeling the input-output relationship of its quantities in a data-driven manner. An encoder-decoder based network called DiagBiRNN has also been proposed which is then used in [START_REF] Verma | Neural networks based speed-torque estimators for induction motors and performance metrics[END_REF] to estimate speed-torque from currents and voltages. To apply this network in real-world setting where currents and voltages are noisy, a meta-denoiser network has been proposed in [START_REF] Verma | Neural speed-torque estimator for induction motors in the presence of measurement noise[END_REF] to denoise noisy currents and voltages. To model electrical motor dynamics, a multi-scale pyramid and lightweight residual networks have been proposed in (9; 10). Estimating the temperature of different parts of an electrical motor is important to understand its thermal evolution. Given the complexity of rotating parts, [START_REF] Kirchgässner | Estimating electric motor temperatures with deep residual machine learning[END_REF] proposed an induction motor temperature dataset. They use convolution and recurrent network-based benchmarks to predict permanent magnet temperature using several electrical motor quantities and temperatures of different motor parts, which are easy to record. Several electrical motor fault datasets cover different categories of faults occurring in different types of motors. [START_REF] Maciejewski | A systematic review of fault detection and diagnosis methods for induction motors[END_REF] proposed fault detection and classification dataset to identify the number of broken bars from electrical motor quantities and vibrations recorded using accelerometers.

Robustness Issue in Neural Networks

Test time instability of neural networks is a well-known and active area of research leading to a more explainable and reliable A.I. In [START_REF] Szegedy | Intriguing properties of neural networks[END_REF], the concept of adversarial attacks was first proposed to fool neural networks. Adding a well-crafted subtle perturbation to the input of the neural network produces a misclassification. This scenario is possible even when the model has good clean accuracy. These attacks pose a huge threat to the performance of neural networks. There has been a multitude of works introducing stronger adversarial attacks and their defenses.

Experimental Setup

We use 9 different architectures proposed in [START_REF] Verma | Modeling electrical motor dynamics using encoder-decoder with recurrent skip connection[END_REF] for motor dynamics, denoise, and speed-torque tasks. We use networks named FNN, RNN, LSTM, and CNN for baselines. We also use encoderdecoder variants from the paper named Deep, Skip, RNN-Skip, BiRNN-Skip, and DiagBiRNN-Skip to understand robustness behavior with respect to network complexity. Details of these networks can be found in [START_REF] Verma | Modeling electrical motor dynamics using encoder-decoder with recurrent skip connection[END_REF]. For the temperature task we use DiagBiRNN-Skip and FedFormer [START_REF] Zhou | Fedformer: Frequency enhanced decomposed transformer for long-term series forecasting[END_REF]. For the broken bars task, we use 1D variant of three classification networks namely CRNN (28), ResNet-18 [START_REF] He | Deep residual learning for image recognition[END_REF], and RegNet-20 [START_REF] Radosavovic | Designing network design spaces[END_REF].

For generating adversarial attacks, we use FGSM and DeepFool. The Value of ϵ is taken at 0.01 and 0. Table 4: Classification results for broken bars task. Table 4 shows results obtained by CRNN, ResNet, and RegNet on broken bars task. In this case, RegNet gives the best clean accuracy. When attacked with FGSM and DeepFool at ϵ = 0.01 and ϵ = 0.1, the accuracy of all three networks decreases, but the order remains the same. Although at ϵ = 0.1, RegNet is still more robust compared to the other two networks.

Conclusion and Future Work

We present a robustness analysis of neural networks used in five different electrical motor tasks. We train a wide array of networks and generate adversarial attacks on them to show their instability. Although our experiments show that networks are somewhat unstable to input perturbations, we still need more sophisticated perturbations to understand the robustness of neural network in electrical motors. In future, it will would be interesting to consider domain knowledge and sequential dynamics of data to generate better attacks and improve the robustness of neural networks for electrical motors. It is also essential to understand the sensitivity of the individual inputs with respect to neural network stability.

B Metrics

M AE(y, ŷ) = 1 T T t=1 |y t -ŷt | (1)
SM AP E(y, ŷ) = 100

T T t=1 | ŷt -y t | | ŷt | + |y t | (2) R 2 (y, ŷ) = 1 - T t=1 ( ŷt -ȳ) 2 T t=1 (y t -ȳ) 2 (3)
RM SE(y, ŷ) = 1 T T t=1 (y t -ŷt ) 2 (4)
where y t is the ground truth, ŷt is the predicted output of the model at time t, and T is the total experiment duration. ȳ denotes the mean of ground truth y. Figure 2 shows an example trajectory from the validation set of the motor dynamics dataset. In the top sub-figure normalized values of u d , u q , and ω r are showed as normal lines. FGSM is used with ϵ = 0.01 to attack the DiagBiRNN-Skip network to generate an adversarial example shown using the dotted lines in the same sub-figure. It can be seen that the adversarial example has an offset when compared to the clean input, but this offset can be positive and negative. There is also intermittent noise like big offsets, for example, one in the 90s. The middle sub-figure shows the ground truth of output signals i d , i q , and τ em using normal lines and DiagBiRNN-Skip predictions using dotted lines.

It can be seen that the network has poor predictions during the first ramp between 5s and 20s. The bottom figure shows ground truth as normal lines and dotted lines are the predictions of DiagBiRNN when the generated adversarial example is given as the input. It can be seen that the adversarial predictions are very noisy compared to clean predictions when the perturbations in the input are minimal. This shows that the attacks on the networks are strong and establishes that robustness study of such networks is important.

Tables 5 shows results obtained by simple networks proposed in [START_REF] Verma | Modeling electrical motor dynamics using encoder-decoder with recurrent skip connection[END_REF] for motor dynamics task. It shows MAE, SMAPE, R 2 , and RMSE for clean predictions and FGSM predictions at ϵ = 0.01 and ϵ = 0.1. CNN variant achieves the best clean predictions MAE (0.02), SMAPE (4.86%) and R 2 (0.76). When attacked, RNN is most robust at both epsilon values.

Table 6 shows results of the encoder-decoder variants trained for denoise task. RNN-Skip obtains the best SMAPE (0.14%) among all the variants. R 2 is 0.99 for all the networks. However, when attacked with FGSM at ϵ = 0.01, DiagBiRNN-Skip outperforms every other network with the lowest SMAPE (1.53%). With a more aggressive attack of ϵ = 0.1, DiagBiRNN-Skip still outperforms every other network with SMAPE (13.6%) and R 2 (0.72).

Figure 1 :

 1 Figure 1: Different sources of perturbations in inputs to neural networks used in electrical motor tasks like denoising and speed-torque estimation.

Figure 2 :

 2 Figure 2: A sample from validation set of motor dynamics task showing clean input, clean output, DiagBiRNN-Skip clean prediction, FGSM generated adversarial example and adversarial prediction.

  box attacker is introduced in[START_REF] Su | One pixel attack for fooling deep neural networks[END_REF]. Such attackers do not know the model but can interact with it. Ballet et al. proposed a white box attacker specifically for handling tabular[START_REF] Ballet | Imperceptible adversarial attacks on tabular data[END_REF] for classification tasks. A similar approach using the Jacobian property of the neural network for tabular data is proposed in Gupta et al.[START_REF] Gupta | An adversarial attacker for neural networks in regression problems[END_REF] for regression tasks. These attacks and defenses constitute the adversarial robustness of neural networks. Robustness of time-series networks due to thermal evolution can be considered as a generalization problem. Such problem have been very well studied in(25; 26).

Goodfellow et al. (14)

proposed the Fast Gradient Sign Method (FGSM) to generate ℓ ∞ bounded adversarial attacks. This is a white box attack, i.e., it has access to network structure, parameter weights, and all the related training details. The generated inputs are misclassified by adding perturbations and linearizing the cost function in the gradient direction. FGSM is a single-step attack, Madry et al.

[START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF]

proposed a multi-step variant of FGSM called Projected Gradient Descent (PGD) attack. Kurakin et al.

[START_REF] Kurakin | Adversarial examples in the physical world[END_REF]

proposed an optimized FGSM, Iterative Gradient Sign Method (IGSM), which adds perturbations in multiple smaller steps and clips the results after each iteration ensuring that the perturbations are restricted to the neighborhood of the example. Dong et al.

[START_REF] Dong | Boosting adversarial attacks with momentum[END_REF]

added momentum to IGSM attacks. Moosavi et al.

[START_REF] Moosavi-Dezfooli | Deepfool: a simple and accurate method to fool deep neural networks[END_REF]

proposed Deepfool as a non-targeted attack that tries to find the decision boundary closest to the sample in the input space and then uses the classification boundary to fool the classifier. Moosavi et al.

[START_REF] Moosavi-Dezfooli | Universal adversarial perturbations[END_REF]

proposed a universal image-agnostic perturbation attack method that fools the classifier by adding a single perturbation to all images in the dataset. Carlini et al.

[START_REF] Carlini | Towards evaluating the robustness of neural networks[END_REF]

proposed a powerful attack based on L-BFGS. In

[START_REF] Balda | Perturbation analysis of learning algorithms: A unifying perspective on generation of adversarial examples[END_REF]

, the authors propose a general framework for the generation of adversarial examples in both classification and regression tasks for applications in the image domain.

Most of these methods belong to the class of white box attackers, i.e., the attacker has access to the information related to the trained neural network model, including the model architecture and its parameters. A black

Table 1 :

 1 1. In the case of DeepFool number of iterations used is 100. For the broken bars task, we report clean accuracy and FGSM and DeepFool attack accuracy. For all the regression tasks, we report clean and FGSM attack values of Mean Absolute Error (MAE), Symmetric Mean Absolute Percentage Error (SMAPE), coefficient of determination (R 2 ) (31), and Root Mean Squared Error (RMSE). Metrics of clean and adversarial predictions from all the encoder-decoder variants trained for motor dynamics task. Tables1shows results obtained by training encoder-decoder networks proposed in[START_REF] Verma | Modeling electrical motor dynamics using encoder-decoder with recurrent skip connection[END_REF] for motor dynamics task. It shows MAE, SMAPE, R 2 , and RMSE for clean predictions and FGSM predictions at ϵ = 0.01 and ϵ = 0.1. Skip encoder-decoder variant achieves the best clean predictions SMAPE (4.62%) and R 2 (0.77). When attacked, RNN-Skip is most robust at ϵ = 0.01 with SMAPE (20.36%), followed by DiagBiRNN-Skip with SMAPE (21.31%). Skip achieves the second worst performance when attacked.

	Network	Attack	MAE SMAPE(%)	R 2	RMSE
	Deep	Clean FGSM ϵ = 0.01 0.11 0.026	5.15 22.89	0.73 -1.02	0.06 0.15
		FGSM ϵ = 0.1	0.15	32.11	-2.90	0.21
	Skip	Clean FGSM ϵ = 0.01 0.11 0.02	4.62 24.94	0.77 -1.14	0.05 0.16
		FGSM ϵ = 0.1	0.39	94.92	-21.99	0.52
	RNN-Skip	Clean FGSM ϵ = 0.01 0.09 0.03	6.73 20.36	0.72 -0.54	0.06 0.13
		FGSM ϵ = 0.1	0.29	73.5	-10.87	0.37
	BiRNN-Skip	Clean FGSM ϵ = 0.01 0.13 0.03	6.82 26.09	0.72 -1.85	0.06 0.18
		FGSM ϵ = 0.1	0.69	76.03	-84.77	0.99
	DiagBiRNN-Skip	Clean FGSM ϵ = 0.01 0.10 0.02	4.70 21.31	0.76 -0.83	0.05 0.15
		FGSM ϵ = 0.1	0.32	58.40	-16.23	0.44
	In case of denoise task, RNN-Skip obtains the best SMAPE (0.14%) among all the variants. R 2
	is 0.99 for all the networks. However, when attacked with FGSM at ϵ = 0.01, DiagBiRNN-Skip
	outperforms every other network with the lowest SMAPE (1.53%). With a more aggressive attack
	of ϵ = 0.1, DiagBiRNN-Skip still outperforms every other network with SMAPE (13.6%) and R 2
	(0.72).
	Table 2 shows results of the encoder-decoder variants trained for speed-torque estimation task.

Encoder-decoder variant Skip shows the best SMAPE (0.18%) among all the variants. R 2 is 0.99 for all the networks. However, when attacked with FGSM at ϵ = 0.01, DiagBiRNN-Skip outperforms every other network with the lowest SMAPE (2.70%). With a more aggressive attack of ϵ = 0.1, RNN-Skip outperforms every other network with SMAPE (17.96%) and R 2 (-0.56). DiagBiRNN-Skip achieves the best R 2 of -0.49.

Table 2 :

 2 Metrics of clean and adversarial predictions from all the networks trained for speed-torque estimation task.

	Network	Attack MAE SMAPE(%) R 2	RMSE
	FedFormer	Clean FGSM 0.03 0.03	6.47 7.53	0.96 0.95	0.04 0.05
	DiagBiRNN-Skip	Clean FGSM 0.03 0.00	0.82 7.73	1.00 0.97	0.01 0.04

Table 3 :

 3 Metrics for clean and adversarial predictions for the two networks trained for permanent magnet temperature prediction task.

Table 3

 3

	ϵ	Method Clean(%) FGSM(%) DeepFool(%)
		CRNN	80.0	79.0	79.0
	0.01	ResNet	90.0	89.0	89.0
		RegNet	93.0	92.0	92.0
		CRNN	79.4	61.4	60.1
	0.1	ResNet	88.9	80.0	79.6
		RegNet	92.3	86.8	86.6

shows results for FedFormer and DiagBiRNN-SKip trained to do permanent magnet temperature prediction task. In this case, it can be seen that FedFormer has performed very poorly when compared to DiagBiRNN in terms of clean predictions. However, when attacked with FGSM at ϵ = 0.01, FedFormer manages to be robust and give the same result as DiagBiRNN. This shows that FedFormer is very robust to adversarial examples. It should be noted that the clean metrics of FedFormer can be improved with a better training strategy as we have used default hyperparameters to train the network.

Table 5 :

 5 Metrics of clean and adversarial predictions from all the simple networks trained for motor dynamics task.

	Network		Attack	MAE SMAPE(%)	R 2	RMSE
	FNN	Clean FGSM ϵ = 0.01 0.12 0.03	5.97 24.06	0.72 -1.57	0.06 0.17
		FGSM ϵ = 0.1	0.82	66.11	-130.99	1.23
	CNN	Clean FGSM ϵ = 0.01 0.11 0.02	4.86 22.02	0.76 -1.05	0.05 0.15
		FGSMϵ = 0.1	0.56	94.63	-45.14	0.73
	RNN	Clean FGSM ϵ = 0.01 0.11 0.03	6.33 21.91	0.73 -0.77	0.06 0.14
		FGSM ϵ = 0.1	0.22	45.53	-6.99	0.30
	LSTM	Clean FGSM ϵ = 0.01 0.12 0.03	5.05 24.73	0.75 -1.90	0.05 0.18
		FGSM ϵ = 0.1	0.39	65.19	-32.92	0.63
	Network		Attack		MAE SMAPE(%) R 2	RMSE
	Deep		Clean FGSM ϵ = 0.01 0.01 0.00	0.22 1.63	0.99 0.99	0.00 0.01
			FGSM ϵ = 0.1	0.06	13.95	0.58	0.09
	Skip		Clean FGSM ϵ = 0.01 0.01 0.00	0.18 1.59	0.99 1.00	0.00 0.01
			FGSM ϵ = 0.1	0.07	15.25	0.67	0.08
	RNN-Skip		Clean FGSM ϵ = 0.01 0.01 0.00	0.14 1.76	0.99 1.00	0.00 0.01
			FGSM ϵ = 0.1	0.08	16.16	0.66	0.08
	BiRNN-Skip		Clean FGSM ϵ = 0.01 0.01 0.00	0.15 1.59	0.99 1.00	0.00 0.01
			FGSM ϵ = 0.1	0.06	14.04	0.71	0.08
	DiagBiRNN-Skip	Clean FGSM ϵ = 0.01 0.01 0.00	0.18 1.53	0.99 1.00	0.00 0.01
			FGSM ϵ = 0.1	0.07	13.6	0.72	0.08

Table 6 :

 6 Metrics of clean and adversarial predictions from all the networks trained for motor denoise task.

A Appendix A Datasets

We use dataset proposed in [START_REF] Verma | Neural speed-torque estimator for induction motors in the presence of measurement noise[END_REF] for motor dynamics, denoise, and speed-torque tasks. The dataset consists of following quantities currents (i d , i q ), voltages (u d , u q ), noisy currents ( îd , îq ), noisy voltages ( ûd , ûq ), rotor speed (ω r ), and mechanical torque (τ em ). The dataset consists of simulations using the control law proposed in [START_REF] Jadot | Adaptive regulation of vectorcontrolled induction motors[END_REF]. The dataset contains 100 hours of simulation data which cover a wide range of operating trajectories. All three tasks are regression problems where some motor quantities are estimated from other quantities. In case of motor dynamics inputs are voltages (u d , u q ) and rotor speed (ω r ). The quantities that have to be predicted are currents (i d , i q ) and mechanical torque (τ em ). The denoise problem deals with denoising noisy currents ( îd , îq ), noisy voltages ( ûd , ûq ). For the speed-torque estimation we predict rotor speed (ω r ), and mechanical torque (τ em ) from currents (i d , i q ) and voltages (u d , u q ). Temperature dataset [START_REF] Kirchgässner | Estimating electric motor temperatures with deep residual machine learning[END_REF] has been used for data-driven thermal modeling to remove or reduce the cost of placing thermal sensors deep inside moving parts of motors. It consists of different experiments where the temperature of the stator and rotor were measured in real operating conditions. Currents (i d , i q ), voltages (u d , u q ), speed (ω r ), and torque (τ em ) are the electrical motor quantities. Permanent magnet (ϑ P M ), stator yoke (ϑ SY ), stator tooth (ϑ ST ), stator winding (ϑ SW ), ambient temperature outside of stator (ϑ a ), and coolant temperature (ϑ c ) are the recorded temperatures. The objective is to predict permanent magnet (ϑ P M ) temperature from all other quantities, making this a regression task.

Broken bars dataset ( 12) is a multiclass classification dataset. The data set contains currents, voltages, and torque as electrical signals. Accelerometers placed in 5 different motor parts are used to collect vibrations/mechanical signals. In total, 400 experiments, each lasting 20 seconds, are performed. The objective is to predict how many broken bars are in the motor from its electrical and mechanical signals.


Carnet Martin Vernier

L Bruneau

Q Devers

A Didier

S Monnier

C Gaillard

H Forestier

C Camerlynck

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

HISTORIQUE DE LA MISSION

La Mission Archéologique Franco-Indienne au Ladakh (MAFIL) a été créée en 2012 après cinq années de contacts informels entre les deux co-directeurs : Laurianne Bruneau et Mr. S.B. Ota, l'un des cinq directeurs régionaux de l'Archaeological Survey of India (ASI).

Ce projet sur quatre ans (2013-2016) a été approuvé par le comité de l'ASI à l'automne 2012. Il s'agit de la première coopération entre l'Archaeological Survey of India et une équipe française, tout comme il s'agit de la première mission archéologique au Ladakh.

Le noyau dur de l'équipe francophone est constitué de l'équipe TEDAHL (Team for the Exploration and Documentation of the Archaeological Heritage of Ladakh) en les personnes de Laurianne Bruneau, Martin Vernier et Quentin Devers.

LA CAMPAGNE 2013

Le projet a pour objectif principal d'établir une séquence chronoculturelle de la vallée de la Nubra. Ceci implique l'étude et le sondage de plusieurs sites et il n'est pas possible d'établir une base fixe pour la mission. De plus, bien que la Nubra soit ouverte au tourisme depuis 1995, on n'y trouve que de petites infrastructures d'accueil. Afin que l'équipe soit mobile et que la vingtaine de personnes la composant puisse être accueillie il a été décidé de camper. Des terrains privés ou monastiques ont été utilisés par le campement de la mission.

L'organisation quotidienne du camp était assurée par une équipe locale (2 cuisinières, 1 aide de camp et 2 chauffeurs).

L'équipe comptait 16 membres : 9 français et 7 indiens.

Les premiers jours de la mission se sont déroulés à Leh (3500 m) dans une pension de famille. Ces jours nécessaires d'acclimatation à l'altitude ont permis de faire connaissance avec les membres de l'équipe indienne et de déterminer, en accord avec Mr. Ota-le codirecteur indien-, le rôle et les objectifs de chacun sur le terrain.

Pour le terrain, l'équipe s'est rendue dans la vallée de la Nubra par une route qui s'enorgueillit du titre de 'plus haute route carrossable au monde'. Après 5h de piste (115km de distance seulement) et le franchissement du col du Khardong (5359 m d'altitude), l'équipe a atteint le village de Panamik, lieu de son premier camp, à mi-chemin entre les sites de Tirisha et Murgi Tokpo.

Après une quinzaine de jours, le camp a été déplacé de l'autre côté de la vallée, à Deskit, nous permettant d'être au pied du troisième site étudié dans le cadre de cette première campagne.

La mission s'est achevée par deux jours à Leh qui ont permis à chacun des membres de finaliser leur rapport. Ce temps a également été mis à profit pour réaliser des copies des données (numériques et papier) pour que chacun des directeurs de la mission dispose de l'ensemble des informations. Les prospections menées à proximité de ce site rupestre on révélé l'existence de structures funéraires, les premières de cette nature pour l'ensemble du Ladakh. La typologie de surface des tombes (enclos de pierres circulaire ou rectangulaire), ainsi que leur proximité avec les pétroglyphes, laisse penser qu'elles sont liées aux cultures des steppes de l'Âge du Bronze ou de l'Âge du Fer.

Le site de Deskit comporte également des vestiges bouddhiques dont un groupe de trois petites chapelles en ruines faisant partie d'un ancien complexe religieux.

Le site funéraire de Deskit sera l'objet de fouilles lors de la prochaine mission en 2014. A l'issue de cette première campagne le bureau de Leh a décidé de proposer les sites de Murgi et Tirisha au comité de protection de l'ASI. Le formulaire de demande de protection a été rempli pour chaque site et soumis en Septembre 2013. Nous nous réjouissons de l'implication du partenaire indien pour la préservation du patrimoine local qui induit une meilleure visibilité des activités archéologiques au Ladakh.

$

  Les résultats de la première campagne de la MAFIL sont très prometteurs. De plus, le terrain s'est déroulé de manière très satisfaisante sur le plan de la coopération. Trois équipes mixtes (français et indiens) et interdisciplinaire (archéologues, environnementalistes) ont travaillé au quotidien : deux équipes étaient sur le terrain sur l'un des sites choisis pour le quadriennal et une autre restait au camp pour l'étude du matériel.Le déroulement des opérations et les résultats préliminaires sont évoqués ci-dessous en quelques images, au gré des notes de terrain et de quelques documents choisis. Le rapport détaillé et officiel sera disponible en ligne dès le mois de janvier 2014 à l'adresse suivante: http://tedahl.org/projects/ mafil/ LE SITE DE MURGI Le site rupestre de Murgi se trouve sur la rive droite de la rivière Siachen, au nord du village éponyme, sur la rive opposée au village de Panamik. Il a été documenté dans son intégralité (relevé photographique et copies in situ) par TEDAHL (L. Bruneau, Martin Vernier et Quentin Devers) entre 2006 et 2011. Six zones totalisant plus de 1000 blocs gravés et 3000 pétroglyphes composent le site rupestre. Les motifs, thèmes et styles des pétroglyphes de Murgi attestent de liens forts avec le monde des steppe à l'Âge du Bronze (fin du III e et II e millénaires av. n.è.) et illustrent l'antiquité des contacts entre la Nubra et l'Asie centrale. Lors de la campagne 2013, afin de mieux comprendre la localisation du site rupestre une étude géomorphologique y a été menée. Une prospection élargie a également révélée des vestiges variés en lien avec le site rupestre. LE SITE DE TIRISHA Tirisha, situé sur la rive gauche de la rivière Siachen, à quelques kilomètres au sud du village de Panamik, a été repéré en 1992 lors de la prospection menée par l'ASI. Le rapport succinct fait mention de vestiges préhistoriques et fortifiés ainsi que de pétroglyphes à proximité du lac de Tirisha. Ces derniers ont été documentés par TEADHL de manière systématique. Deux concentrations ont été identifiées. La première, autour du lac, comprend uniquement des représentations zoomorphes (yaks et bouquetins) de patine très foncée gravées sur les blocs. La seconde correspond aux parois externes du promontoire rocheux abritant le lac et présente des gravures bouddhiques. Ces deux concentrations bien distinctes spatialement et chronologiquement trouvent une correspondance avec les autres types de vestiges recensés. Le lac de Tirisha : un site pré-historique de plein air L'aire dite du lac de Tirisha est connue comme un site préhistorique dans la littérature scientifique depuis une vingtaine d'années. Dans le cadre de la mission MAFIL 2013, une prospection dans cette formation volcanique que l'histoire géologique et les évènements glaciaires ont façonnée en « roches moutonnées » fortement patinées dans une teinte brune, a confirmé l'intérêt du site. La récolte compte 57 objets lithiques taillés ramassés sur les versants (internes, externes) du lac ainsi que sur les crêtes. Les vestiges bouddhiques Des gravures bouddhiques ont été documentées par TEDAHL sur les parois externes de l'ensemble rocheux de Tirisha en 2006. Parmi celles-ci on compte une inscription de douze lignes en tibétain accompagnant des représentations de stūpa. L'inscription présente des archaïsmes orthographiques pouvant remonter à l'époque impériale tibétaine (milieu du 7 e -milieu du 9 e siècle de n.è.). Cette inscription unique pour l'ensemble de la Nubra trouva un écho en 2011 lors de la découverte à quelques centaines de mètres à l'est, d'un ancien stūpa en pierre. Erigé sur une plateforme rectangulaire (20m par 25m environ) délimitée sur ses quatre côtés par un mur, ce stūpa en état de ruines avancé présente une base et des plateformes dont la forme est incertaine (circulaire, rectangulaire ou encore cruciforme). Des échelles, ou escaliers, descendent depuis le dôme éventré jusqu'au sol sur chacune des quatre faces du monument. Que ce soit par ses dimensions ou sa typologie ce stupa est unique pour l'ensemble du Ladakh. Toutefois, de tels monuments existent en Asie centrale (Adjina Tepe, Tadjikistan ; Rawak, Xinjiang) et au Cachemire (Ushkur et Parihasapura) où ils sont attribués au dernier quart du premier millénaire de n.è. Il est donc possible que le stūpa de Tirisha soit l'un des plus anciens témoignages du Bouddhisme dans la Nubra, mais aussi au Ladakh. Il est espéré que les échantillons de bois prélevés cette année au niveau de la plateforme et du stūpa central préciseront la date du monument par le biais d'analyses C14. Outre la collection d'échantillons, les opérations menées en 2013 sur le site bouddhique de Tirisha ont consisté en la réalisation d'un plan au moyen d'un GPS différentiel à partir des structures de surface. Un ramassage de surface a révélé le premier et unique tesson inscrit connu à ce jour pour l'ensemble du Ladakh. Il s'agit d'une lettre ("ga") en tibétain. LE SITE DE SUMUR Découvert en 2010, ce site dominant la vallée de la Nubra est l'un des plus grands sites fortifiés du Ladakh. Situé à 2h de marche audessus du village de Sumur (800m de dénivelé environ) il se compose d'une forteresse centrale protégée par un double rempart à tours circulaires. Un fossé et deux tours d'avant-poste renforcent le dispositif défensif. Le rempart extérieur comporte seulement deux pièces alors que le rempart intérieur en contient environ 80. Le plan à double rempart et tours circulaires de cette forteresse est singulier pour le Ladakh. Ce plan est inconnu du monde tibétain ou encore du Baltistan (nord du Pakistan). Une étude architecturale préliminaire laisse penser qu'il est lié aux fortifications médiévales de l'Hindukush et du Pamir. Aucune source, qu'elle soit écrite ou orale, ne mentionne la forteresse et aucun évènement historique ne lui ait associé de mémoire. Il est espéré que les échantillons de bois prélevés cette année permettent de fixer dans le temps cet ensemble monumental. La localisation reculée du site a permis une conservation exceptionnelle des pièces : foyers et matériel céramique sont en place. Cette année un ramassage systématique de la céramique de surface d'une des pièces a été réalisé. Une grille de 50cm par 50cm a été mise en place dans la pièce n°4 : 373 tessons ont été collectés. Après remontage 5 à 7 jarres globulaires à long col et bord évasé ont été identifiés. ETUDE DU MATERIEL CERAMIQUE La première campagne de la MAFIL avait pour objectif d'étudier le matériel céramique rassemblé lors des prospections précédentes de TEDAHL. Il s'agissait de réaliser une première étude céramique pour le Ladakh, opération qui n'avait jamais été réalisée jusqu'à présent. Le matériel étudié était constitué des ramassages de surface réalisés entre 2006 et 2011 sur 72 sites sur l'ensemble du Ladakh. A la vue de la quantité de matériel et du caractère novateur de l'étude les chefs de mission ont décidé que seule la céramique de la Nubra pourrait être traitée de manière satisfaisante dans le temps imparti par la campagne. La céramique provient de sites variés : sites bouddhiques, fortifiés, funéraire ou encore anciennes habitations. Aucun tesson ne provient d'un contexte stratigraphique et qu'aucune datation n'est assurée pour les sites. L'objectif de l'étude n'était donc pas d'obtenir une typo-chronologie de la céramique de la Nubra mais de réaliser une classification technologique et typologique pour chaque site. Un travail de comparaison inter-sites a permis d'identifier des ensembles de référence qui pourront être utilisés lors de futures opérations de terrain et lors d'études céramique intra et supra régionales. LE SITE DE DESKIT En 2010 et 2011, la documentation d'un autre site rupestre dans la vallée, à Deskit, confirma la continuité des contacts de la vallée de la Nubra avec le domaine steppique au 1 er millénaire av. n.è.

  de la MAFIL a donné lieu à des échanges avec les populations locales impliquées d'une manière plus ou moins directe dans ses investigations. Ces événements locaux en marge du terrain ont étés riches en enseignement pour notre futur travail sur place. Ils ont révélés d'une part la puissance des réseaux locaux de communication et d'autre part le rôle central des autorités religieuses. L'attention portée au patrimoine local de la part des habitants de la vallée et leur méfiance vis à vis des ingérences étrangères (quand bien même indienne) sont à prendre en compte. A ce niveau, les diverses autorisations et permis issus par le gouvernement central de Delhi et les autorités régionales de Leh dont bénéficiait la mission n'ont pas suffi à convaincre d'emblée les villageois. Les différentes rencontres et débats survenus lors de la campagne entre les représentants de la MAFIL d'une part, les délégués des communautés villageoises, les élus locaux et les membres du clergé bouddhique d'autre part ont révélé l'importance pour l'avenir de la mission de l'établissement de liens suivis et privilégiés sur place. Il apparait également que les collectivités locales désirent non seulement être tenues au courant des actions de la mission dans la Nubra, mais désirent également être tenues au courant des résultats obtenus. Nous ne pouvons ici que saluer cet élan d'intérêt et ce juste retour des choses, une démarche trop souvent ignorée par le passé de la part des différents chercheurs et intervenant étrangers au Ladakh.

$ $


Dessins Réalisés Par

Martin Vernier

Laurianne Bruneau

sur$ le$ terrain$ et$ les$ difficultés$ accrues$ qui$ en$ découlent$ pour$la$mission,$ceci$afin$de$les$contextualiser$au$mieux.

gestion$ ne$ sont$ que$ très$ récentes,$ a$ induit$ au$ Ladakh$ (une$ région$ à$ l'équilibre$ très$ fragile$ du$ fait$ de$ son$ cadre$ tant$ géographique$ qu'historique)$ des$ effets$ secondaires$ majeurs$ tant$ au$ niveau$ social$ qu'économique,$ climatique$ et$ écologique.$ Corollaire$ de$ cet$ engouement$ touristique$ et$ alimenté$ par$ l'aspect$ tant$ authentiquement$ traditionnel$ qu'anachronique$ de$ sa$ société,$ le$ Ladakh$ a$ connu,$ dès$ son$ ouverture$ au$ tourisme,$l'implication$de$très$nombreuses$ONG$étrangères.$L'implication$ d'organisations$ non$ gouvernementales,$ tout$ d'abord$ principalement$ tournées$ vers$ les$ domaines$ de$ l'éducation$ et$ de$ la$ santé$ se$ sont$ multipliées$ et$ diversifiées$ au$ fil$ du$ temps$ pour$ finir$ par$ toucher$ tous$ les$ aspects$de$la$vie$locale.

$$ $ La$conservation,$la$protection$et$la$gestion$du$patrimoine$culturel,$ architectural,$ artistique,$ historique$ et$ archéologique$ du$ pays$ ne$ font$ pas$ exception$ et$ les$ ONG$ impliquées$ dans$ ces$ domaines$ sont$ aujourd'hui$ nombreuses$ au$ Ladakh.$ Malheureusement,$ à$ l'heure$ actuelle,$ il$ n'existe$ aucun$ organe$ institutionnel$ au$ niveau$ local$ visant$ à$ s'assurer$ de$ l'application$de$la$législation$centrale$(celle$de$l'ASI)$et$régionale$(de$l'état$ du$ Jammu$ et$ Cachemire)$ concernant$ le$ patrimoine$ historique$ et$ archéologique.$ Il$ en$ ressort$ une$ situation$ confuse,$ chaque$ organisme$ menant$son$projet$comme$il$l'entend,$
$ de$ nombreux$ dégâts,$ heureusement$ principalement$ matériels.$ L'itinéraire$arrêté$initialement$pour$la$campagne,$à$savoir$le$passage$par$le$ col$du$Wari$(5200$m$d'altitude)$pour$atteindre$la$vallée$de$la$Nubra$n'a$été$ confirmé$comme$praticable$qu'au$moment$même$du$départ.$Cet$itinéraire a$impliqué$en$de$nombreux$endroits$le$dégagement$par$l'équipe$de$roches$ éboulées$sur$la$piste$afin$de$permettre$le$passage$des$véhicules.$$$ $$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ ) Le#site#de#Murgi# # ) "Nous) arrivons) à) Murgi) à) 13h15.) Notre) véhicule) matériel) est) en) cours) de) déchargement) lorsqu'un) groupe) d'une) dizaine) de) villageois) (yulL pa,) goLpa,) members)) s'approche) de) la) maison) de) notre) hôte) puis) s'interpose) à) notre) équipe) en) train) de) décharger) le) matériel.) Le) ton) est) agressif.)Je)prends)à)part)mes)collègues)occidentaux)et)nous)nous)retirons) de)la)discussion,)à)l'abri)de)la)pluie,)contre)la)maison,)laissant)Rigzin)et)nos) chauffeurs,)Spalzing)et)Stanzing)discuter)avec)le)groupe)des)murgiLpa.)Leur) position)est)sans)appel,)hors)de)question)pour)nous)de)camper)au)village,) encore)moins)d'y)travailler,)c'est)tout)juste)s'ils)nous)autorisent)à)prendre) un) repas) sur) place) avant) de) repartir.) Dans) la) discussion,) qui) prends) vite) une)allure)de)confrontation)le)mot)de)"doctor")revient)à)plusieurs)reprises.) Nous) apprendrons) plus) tard,) malgré) la) reluctance) de) nos) accompagnateurs) visLàLvis) de) ce) qui) s'apparente) pour) eux) a) un) acte) de) délation)(et)confirmation)du)DSPT)de)Murgi)ultérieurement))qu'il)s'agit)du) docteur)Sonam)Angchuk)KhardongLpa)de)Leh.)La)même)personne)donc)qui) avait)déjà)travaillé)à)l'échec)de)la)mission)2014)à)Diskit.)Ce)dernier)semble) ainsi)vouloir)s'assurer)avec)acharnement)l'exclusivité)de)la)documentation) et) de) la) protection) du) patrimoine) historique) du) Ladakh) et) ceci) tout) spécialement)dans)la)région)de)la)Nubra)dont)il)est)originaire.

)) "Si) vous) allez) sur) le) site) nous) vous) lancerons) des) pierres",) "partez) et) ne) revenez) pas",) la) famille) du) DSPT) qui) se) proposait) de) nous) héberger) à) Murgi,)comme)depuis)plus)de)cinq)ans,)est)menacée.)Au)milieu)du)ton)qui) monte,) je) m'interpose) et) assure) les) villageois) que) dès) le) repas) pris) nous) partirons)de)Murgi,)sans)halte)sur)le)site.)Le)repas)avalé)à)l'abri)de)la)pluie) chez) nos) hôtes,) nous) gagnons) Panamik.) Au) passage) en) contrebas) du) site) rupestre) nous) apercevons) des) guetteurs) envoyés) sur) le) haut) du) site) (sommet)de)la)zone)II))qui)s'y)assurent)que)nous)ne)nous)y)arrêtions)pas.)Le) site) est) à) présent) couronné) de) deux) mâts) de) prière) et) de) drapeaux) de) prière)(sommet)des)zones)I)et)II),)notre)séjour)à)Murgi)aura)duré)moins)de) 2)heures.")

Extraits$du$journal$de$mission$de$M. $Vernier,$23.08.2015

) $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ D'
$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ Yulkam$Tokpo,$ report$sur$acétate$ de$la$surface$principale.$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ En$chemin,$à$Panamik.$$ Un$cimetière$à$l'abandon$conserve$les$tombes$des$caravaniers$musulmans$ en$provenance$de$Yarkand.$$ $ $ $
Ces$ représentations$ de$ stupa$ sont$ uniques$ pour$ l'ensemble$ du$ Ladakh$ et$ correspondent,$ typologiquement,$ à$ certaines$ gravures$ de$ la$ région$de$Chilas$(région$de$Gilgit5Baltistan,$Pakistan).$En$suivant$le$cours$de$ la$Shyok,$on$pouvait$parvenir$en$quelques$jours$de$marche$à$la$région$Chilas$ depuis$Digar$et$de$manière$plus$générale$depuis$la$Nubra.$

$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $
Il est intéressant de noter que les trois temples en ruines présents sur le site proposent la même séquence de construction : un premier corps de bâtiment auquel s'ajoute en un second temps un portique d'entrée. Une observation attentive des parois intérieure du temple a permis la documentation de restes de surfaces couvertes d'enduit pictural ocre en deux endroits, de pigments de couleur bleue et d'enduit blanc ont été également relevés à proximité des restes d'ocre de la paroi USM008.

Plusieurs prélèvements ont été effectués dans les ruines des temples. Un fragment d'enduit mural avec traces de couleur ocre sur la paroi sud du temple 2 et plusieurs fragments de modelé en terre crue, de bois peint et d'enduit pictural issu du dégagement en cours de travail dans le sondage. Parallèlement, et a des fins de datation par radiocarbone, six prélèvements de matière organique (paille, brindille balle) ont été effectués, dont 1 dans le mortier issu du temple 1 et 5 issus des enduits muraux des temples 1, 2 et 3.

Lors de son travail sur le site de Choskhor, en fin de séjour, l'équipe a reçu la visite des représentants du village voisin de Gompa, accompagnés de trois moines. Si la prise de contact fut tout d'abord relativement houleuse, une conversation téléphonique avec le co-directeur indien du projet, en direct depuis le site, a permis d'établir un climat de discussion serein par la suite.

Sur invitation du co-directeur français de la MAFIL, Sunder Paul, directeur du bureau de l'ASI de Leh, a accepté de venir rencontrer la délégation des villageois et des moines au camp de la MAFIL le jour même afin de discuter ensemble des possibilités de collaboration et des enjeux liés au site. Suite à la discussion, menée par M. Paul, les moines se sont montrés intéressés par le travail de la mission, ouvert à sa continuation, y compris celle du sondage dans le temple 1, et ont souhaité être tenus au courant par la suite des résultats des recherches de l'équipe. La conclusion positive et intéressée de cette rencontre marque un tournant décisif dans la courte histoire de la MAFIL, qui s'en réjouit et compte travailler à la consolidation de ce lien pour sa campagne 2016.

  un$ commun$ accord$ avec$ S.B.$ Ota,$ avec$ qui$ M.$ Vernier$ s'est$ entretenu$ à$ Panamik$ le$ jour$ même,$ il$ a$ été$ convenu$ de$ se$ retirer$ de$ la$ Nubra.$$ $ Afin$de$mettre$à$profit$le$temps$imparti$ainsi$que$les$compétences$ techniques$ et$ scientifiques$ de$ l'équipe$ tout$ en$ visant$ une$ complétion$ optimale$ du$ quadriennal$ de$ la$ MAFIL$ au$ Ladakh,$ les$ co5directeurs$ de$ la$ mission$ ont$ retenu$ la$ proposition$ avancée$ par$ M.$ Vernier$ de$ porter$ désormais$l'attention$de$la$MAFIL$sur$les$sites$pouvant$se$rattacher$à$l'axe$ d'étude$ fixé$ par$ le$ quadriennal,$ mais$ situés$ au$ Ladakh$ central,$ de$ l'autre$ côté$des$sommets$et$cols$séparant$ce$dernier$de$la$Nubra.$$ $ Entre$ Murgi$ et$ Leh,$ des$ opérations$ de$ documentation$ et$ de$ prospection$ ont$ été$ brièvement$ menées$ sur$ le$ site$ rupestre$ de$ Yulkam$ Tokpo$ et$ sur$ les$ villages$ fortifiés$ en$ ruines$ de$ Hundar$ Brog$ et$ Digar$ Kharpoche.$

  dont$les$compétences$techniques$et$ l'éthique$ sont,$ le$ plus$ souvent,$ évalués$ par$ les$ propriétaires$ des$ sites$ en$

	Le terrain
	$	Les$pluies$et$inondations$survenues$au$Ladakh$durant$tout$le$mois$
	de$ juillet$ 2015$ ont$ mis$ à$ rude$ épreuve$ le$ réseau$ routier$ du$ pays$ et$
	engendré
	fonction$ du$ montant$ des$ budgets$ investis.$ Restaurations$ fantasques,$
	pillage,$ démarches$ d'origines$ religieuses,$ tentatives$ malheureuses,$
	réalisations$exemplaires…$le$Ladakh$peine$à$s'y$retrouver,$fatigue$devant$
	l'ingérence$ et,$ ne$ sachant$ plus$ à$ qui$ se$ fier,$ tend$ à$ se$ refermer$ sur$ lui5
	même.$
		$
	$	Dans$ce$contexte,$il$n'est$pas$étonnant$que$la$MAFIL$rencontre$des$
	difficultés$ dans$ la$ réalisation$ de$ ses$ objectifs$ et$ nous$ ne$ pouvons$
	qu'espérer$ que$ les$ démarches$ d'information$ et$ de$ vulgarisation$ initiées$
	par$la$mission$dès$la$première$campagne$finiront$par$porter$leurs$fruits.$$
	$
	$
	$

La$ Mission$ Archéologique$ Franco5Indienne$ au$ Ladakh$ (MAFIL)$ a$ été$ créée$ en$ 2012$ après$ cinq$ années$ de$ contacts$ informels$ $ entre$ le$ Dr$ Laurianne$ Bruneau$ (maître$ de$ conférences$ à$ l'École$ Pratique$ des$ Hautes$ Études,$ rattachée$ à$ l'UMR8155/CRCAO,$ Paris),$ et$ Simadri$ Bihari$ Ota,$ l'un$ des$ cinq$ directeurs$ régionaux$ (zone$ centrale,$ Bhopal)$ de$ l'Archaeological$ Survey$of$India$(ASI).$$ Il$ s'agit$ de$ la$ première$ coopération$ entre$ l'Archaeological$ Survey$ of$ India$ et$ une$ équipe$ française,$ tout$ comme$ il$ s'agit$ de$ la$ première$ mission$archéologique$au$Ladakh.$$ Pour$ des$ raisons$ médicales,$ Laurianne$ Bruneau$ n'a$ pas$ été$ en$ mesure$ de$ diriger$ la$ campagne$ 2015.$ La$ direction$ (côté$ français)$ a$ été$ assurée$ par$ Martin$ Vernier,$ archéologue$ indépendant$ suisse.$ L.$ Bruneau$ et$ M.$ Vernier$ collaborent$ depuis$ 2006,$ à$ la$ fois$ sur$ le$ terrain$ et$ pour$ la$ publication$ des$ données.$ Ils$ ont$ réalisé$ trois$ campagnes$ de$ relevés$ d'art$ rupestre$ ensemble$ (2006,$ 2007$ et$ 2011)$ et$ écrits$ cinq$ articles$ conjointement.$ Par$ ailleurs,$ M.$ Vernier$ se$ rend$ au$ Ladakh$ de$ façon$ annuelle$depuis$près$de$30$ans$et$en$connaît$parfaitement$la$langue$et$les$ us$et$coutumes.$Il$a$initié$la$documentation$systématique$de$l'art$rupestre$ du$ Ladakh$ dès$ 1996$ et$ a$ publié$ la$ première,$ et$ pour$ l'instant$ l'unique,$ monographie$consacrée$au$sujet.$Depuis$une$dizaine$d'années,$M.$Vernier$ a$ étendu$ ses$ champs$ de$ recherches$ et$ de$ terrain$ au$ patrimoine$ bouddhique$ ancien$ du$ Ladakh$ (stèles$ et$ reliefs$ mais$ aussi$ vestiges$ de$ temples).$$ En$2013$et$2014,$lors$des$deux$premières$campagnes$de$la$MAFIL,$ M.$Vernier$avait$le$rôle$de$directeur$adjoint.$En$sus$d'être$en$charge$des$ aspects$ logistiques$ du$ terrain,$ il$ assurait$ la$ fonction$ de$ dessinateur.$ Fort$ de$ses$diverses$expériences$et$compétences,$la$direction$de$la$campagne$ 2015$lui$a$été$confiée.$ LA CAMPAGNE 2015 Préambule $ Tout$comme$les$deux$années$précédentes$de$la$MAFIL,$le$contexte$ socio5politique$et$culturel,$du$Ladakh$a$impliqué$de$nombreuses$difficultés$ pour$ la$ MAFIL$:$ absence$ de$ soutiens$ et$ d'anticipation$ de$ l'ASI$ au$ niveau$ local,$ ignorance$ de$ la$ chose$ archéologique$ de$ la$ part$ des$ populations,$ superstitions$ et$ croyances$ diverses$ concernant$ tout$ ce$ qui$ touche$ aux$ vestiges$religieux$et$structures$funéraires$et$toute$intervention$dans$le$sol$ de$manière$générale.$$ $ De$ plus,$ cette$ année,$ la$ mission$ a$ malheureusement$ eut$ la$ confirmation$ des$ rumeurs$ rapportées$ les$ années$ précédentes$ quant$ à$ l'implication$active$de$certains$acteurs$culturels$locaux$à$l'encontre$du$bon$ déroulement$ du$ travail$ de$ la$ MAFIL,$ ceci$ tout$ particulièrement$ dans$ la$ région$ de$ la$ Nubra.$ Ce$ dernier$ fait$ illustre$ une$ tendance$ générale$ au$ Ladakh$ qui,$ de$ manière$ de$ plus$ en$ plus$ perceptible,$ tend$ à$ repousser$ toute$ingérence$perçue$comme$étrangère$dans$la$gestion$des$affaires$de$la$ région,$qui$est$dotée,$rappelons5le,$d'un$gouvernement$local$indépendant$ (Ladakh$Autonomous$Hill$Development$Council,$LAHDC).$A$ce$propos$il$est$ intéressant$de$remarquer$que$l'implication$de$l'administration$centrale$de$ Delhi$ est$ perçue$ comme$ "étrangère",$ au$ même$ titre$ que$ celle$ d'organismes$et$d'individus$d'origine$non$indienne.$ $ $ Il$nous$semble$pertinent$de$résumer$ici$brièvement$certaines$des$ raisons$ qui$ peuvent,$ en$ partie,$ expliquer$ la$ montée$ récente$ d'une$ forme$ de$ xénophobie$ $$ $ $ Depuis$une$trentaine$d'années,$le$Ladakh$jouit$à$l'étranger,$et$de$ manière$ plus$ récente$ dans$ le$ reste$ de$ l'Inde,$ mais$ pour$ des$ $ Cette$ idéalisation$ du$ Ladakh,$liée$en$partie$aux$mystères$prétendus$du$bouddhisme$tibétain,$à$ l'inaccessibilité$ de$ la$ région$ et$ à$ sa$ relativement$ récente$ ouverture$ aux$ visiteurs$ étrangers$ est$ à$ la$ base$ d'une$ exploitation$ touristique$ subite,$ massive$ et$ intensive.$ Cette$ nouvelle$ industrie,$ dont$ les$ tentatives$ de$


Alexandre S Saidi
email: alexandre.saidi@liris.cnrs.fr

Using Grammatical Inference For Structure Induction

Given the huge quantity of the current available textual information, Text Mining process tackles the task of searching useful knowledge in a natural language document.

When dealing with a free-format textual corpus (e.g. a Job announcement) where the linguistic rules are not respected, the time consuming morpho-syntactic analysis is not of a great help. However, text mining techniques process may exploit linguistic sub-structures in the text.

In this paper, we present an applications of Grammatical Inference (GI) in a machine learning system applied to a text corpus. We specify and use the process of the Grammatical Inference as an instance of the Constraint Satisfaction Problem that instantiates automata in a (language inclusion) lattice.

Introduction

Textual databases constitute the major part of the current available information. Significant research work concentrates on the Information Extraction (IE) from these databases.

Given a textual corpus, the information extraction process applied by the techniques of Text Mining (e.g. [START_REF]fayyad & all From DataMining to Knowledge discovery : An overview[END_REF], [START_REF] Hearst | Text Data Mining : Issues, Techniques and Relationship to Information Axxess[END_REF], [START_REF] Grishman | Information Extraction: Techniques and Challenges[END_REF], [START_REF] Ahohen | Forming Grammars for structured documents[END_REF]) consists of the search for no-explicit informations in such corpora. As an example, Text Mining can extract significant information from Marine catastrphes bulletins like the prior event sequence of such disasters.

In a basic approach, IE task would be tedious if no a priori structural information is available about the text. On the other hand, given the cost of a syntactical analysis, an IE process based on a whole morpho-syntactic analysis of documents would not often be realistic. When dealing with free-format texts, such analysis would not be of a great interest in a text mining process usually based on key patterns.

In the case of free format texts, the rules of linguistic grammars are seldom respected. These texts rather contain few words without using entities such as determinant, verb and other punctuation.

In the current work, we are interested in the structures of sub-languages in free-format texts. For example, suppose an advertisement of an exposition on Egypt that will take place in Paris. The knowledge of the structure of the sub-language representing the address (where the exposition takes Place) may avoid concluding too quickly (and wrongly) on the place of the exposition upon the simple presence of Egypt city name.

Text Mining research field has been focused on since 1991 through MUC programs. However, it is still domain specific and time-consuming to build a new system or to adapt an existing one to a new domain. Although symbolic and statistical methods have been applied in some IE systems (e.g. [START_REF] Califf | Relational Learning of Pattern-Match Rules for I[END_REF], [START_REF] Huffman | Learning information extraction from examples[END_REF]), not a lot have combined Grammatical Inference with (naive) statistical information.

Techniques of Grammatical Inference (GI) ( [START_REF]Grammatical Inference : Algorithms and Applications[END_REF], [START_REF]Grammatical Inference : Algorithms and Applications[END_REF], [START_REF]Grammatical Inference : Algorithms and Applications[END_REF]) promise to be useful in this field. They carry the process of Text Mining to capitalize the (partial) morphosyntactic structure of patterns (or of sub languages) with a few amount of information on the contents structure. These techniques attempt to induce the structures of a source data (flow of signs) by a set of production rules of a regular grammar. The induced grammar being an element of a (language-inclusion) lattice, the text mining is concerned by an informed search (seen as a generalization) within this lattice carrying required information and semantics.

This paper describes a research work on the design and implementation of GI process that was successfully applied first in a Pattern Recognition project on documents like summaries, dictionaries, scientific reports and so on. Here, whenever the linguistic structure of these documents are extracted, Textual DataMining technics ( [START_REF]fayyad & all From DataMining to Knowledge discovery : An overview[END_REF], [START_REF] Hearst | Text Data Mining : Issues, Techniques and Relationship to Information Axxess[END_REF], [START_REF] Feldman | Dagan Knowledge Discovery in textuel databases (KDT)[END_REF], [START_REF] Grishman | Information Extraction: Techniques and Challenges[END_REF], [START_REF] Ahonen | Applying data mining techniques for descriptive phrase extraction in digital documents[END_REF], [START_REF] Dixon | An Overview of Document Mining Technology[END_REF]) are applied to such documents and extract valuable knowledge from the data.

For example, a given report document (among the corpus) can be (logically) structured by a production rule like: report ← abstract, outline, chapter, sub-chapter, chapter, references. Having one rule per example, the objective is to generalize these rules in a GI process and to propose an automaton that describes the underlying language.

A second application of this process was on a seminar announcement corpus. A seminar announcement may have the following structure (one of the possible formats):

seminar ← heading, subject, speaker, date, hour, address, organizer In this second experiment, the aim is first to learn how to recongnize slot values (and their structures), and then to capture slot fillers from new announcements.

In this paper, we focus on the extraction of the structure and the content of the above announcement corpus of documents using the Grammatical Inference. We apply the process of Grammatical Inference to a set of regular production rules. As in the above examples, each rule (one for each element of the sample set) represents the (logical) structure of the sample 1 . Negative descriptions (and samples) can be provided in order to denote those structures that must be rejected. The inference engine then produces a representative regular grammar that will recognize documents in their respective context.

In the following, some background about the Regular Inference is reported.

Grammatical Induction

The problem of grammatical inference can be considered in a Constraint Satisfaction Problem framework (see e.g. [START_REF] Van Hentenryck | Constraint Satisfaction in Logic Programming[END_REF]). Although some work (e.g. [START_REF] Coste | Regular Inference as a graph coloring Problem[END_REF]) tackled this problem as an instance of graph coloring, the proposed approach gave an interesting but a quite general idea of the question.

In [START_REF] Gold | Complexity of automaton identification from given data[END_REF], Gold showed that any recursively enumerable class of language is identifiable using a complete representation with the positive and the negative data. Hence, the class of regular languages cannot be correctly identified from only the positive examples. Although the usual case in document handling is to learn from only positive examples (given in the set I + ), the induced grammar can be drastically refined by some negative examples (the set I -) and avoid over generalization 2 .

It is known that any algorithm that would construct a deterministic finite automaton (DFA) with a minimum number of states compatible with all the data already processed can identify any regular language in the limit ( [START_REF] Gold | Language identification in the limit[END_REF]).

To achieve that, we developed an original and complete algebraic framework for the Grammatical Inference. In this framework, we define a relation over the (language inclusion) lattice of automata represented by the set of all samples I =( I + ∪ I -) that leads to the construction of partitions over that search space. To realize that, an initial algebra A GI is assigned to a regular grammar G I associated to the sample set I. Then we focus on the definition of a quotient algebra A GI /R of A GI that leads to a uniquely defined isomorphism from A GI /R to the language of the induced automaton A. This automaton is supposed to govern and generalize the language structuring the sample set.

Within this algebraic framework (describing why the logical description is processed in that way), we discuss a general Constraint Satisfaction specification that characterizes the search space of the GI problem. Then, we define a set of constraints that outlines the quotient algebra above and constructs the final induced DFA (the automaton A).

The Regular Inference

The Inductive Inference paradigm is the basis of the automatic learning problem (see also [START_REF] David | Information Theory, Inference, and Learning Algorithms[END_REF]). In the Syntactical Pattern Recognition (see e.g. [START_REF]ICCSA: International Workshop on Advances in Structural and Syntactical Pattern Recognition[END_REF]), many grammatical inference algorithms are proposed that are used in the learning step of the pattern recognition tasks ( [START_REF]Grammatical Inference : Algorithms and Applications[END_REF], [START_REF]Grammatical Inference : Algorithms and Applications[END_REF], [START_REF]Grammatical Inference : Algorithms and Applications[END_REF]). As mentioned above and in order to correctly identify regular languages, positive (I + ) and negative (I -) examples are to be provided to represent the language to be learned. Example : partially from a seminar announcement textual database (see the section 5 for an announcement example), we may have some announcement message rules in the sets I + ={r 1 ,r 2 ,r 3 ,r 4 , ...}, I -={r 5 ,r 6 , ...} below:

r 1 : M essage ← "seminar", Det,
Organization, N ame. r 2 : M essage ← "seminar", Organization, T heme. r 3 : M essage ← "seminar", P ro, City, ":", T heme. r 4 : M essage ← "seminar", N ame, T heme. r 5 : M essage ← Det, ":", T heme. r 6 : M essage ← "seminar", Organization, Organization.

Here, each valid announcement begins with the word seminar. The rule r 5 denotes that a message can not begin with a Determinant (Det) while r 6 denotes that a message with two successives Organizations must be rejected. Note that saying naively that Organization will always follow seminar word is wrong.

In the next section, an algebraic specification of the GI problem is stated. Then, in the sections 4 and 4.1, some practical issues, the implementation of the proposed CSP framework together with some examples are reported. Then, some relationships with other works in this field are recalled in the section 9.

Algebraic View of the GI

In the algebraic specification below, and relative to the sample set (I = I + ∪ I -), the properties of the partitions over the terms of A GI -algebra associated to the grammar G I are depicted. Then we formally characterize a relation from these partitions to L(A), the language of the final induced automaton. This is done by the definition of a set of constraints defining a congruence relation R over the terms of A GI . The latter produces a quotient-algebra A GI /R whose terms are isomorphic to those of L(A).

Quotients of the A GI -algebra give a (language inclusion) lattice. Here, our main aim in the Grammatical (regular) Inference is to characterize this lattice and to guide the search in it.

The Grammatical Inference problem can be specified by using the relation between an initial many sorted algebra and context-free grammars ( [START_REF] Goguen | Initial Algebra Semantics and Continuous Algebra[END_REF]) 3 . To construct the algebra associated to a context-free grammar G, each non terminal of G is assigned to a class of derivation tree. Consequently, the non terminals of G are sorts of a many sorted algebra whose operations are defined by the production rules of G. The derivation tree (and the language) of any non terminal X denotes the carriers of the sort X of the algebra.

Let G =(N, T, P, S) be a context-free grammar and L G be its language with N =non terminals, T : the terminals, P : Production rules and S : the start symbol . Let associate to G the A G -algebra whose signature is ((N ∪ T ), Op) where Op is the set of names given to the productions in P . The terms of this algebra are (possibly partial) derivation trees starting from any non terminal of G.

An A G -algebra is initial in a category C based on the same signature if for all algebra B of C, there exist a unique homomorphism f : A G → B.

Let's now consider the sample set I = I + ∪ I -(with I + ∩ I -= ∅), the grammar G I from the set I , the A GI -algebra associated to G I and the language L(A) (A is the final induced DFA). We are interested in f such that f : A GI → L(A). Consider the set of finite automata associated to elements of I (one automaton per element of I) and let Tree(I) denote the tree of all these automata.

We define the automaton G I =( Q ∪{S}, Σ,P δ , S,F) associated to Tree(I) where Q is the set of all states in Tree(I), Σ is the set of terminals in I and P δ is the set of the names given to the transitions in Tree(I). The start symbole S is such that S → p 01 | p 02 |... where p ij ∈ P δ , j is the rank of the transition in the ith automaton associated to each element of I. F is the set of final states in Tree(I). G I associated to Tree(I) is possibly a no deterministic but ǫ-free (circuit-free) automaton.

If L I+ is the language of the positive samples (resp. L I-for the negative ones) generated by the final induced automaton A (that accepts only L I+ ), then, for any partition of Q containing equivalent states (cf. the section 4),

I + ⊆ L I+ and I -⊆ L I-.W eh a v eL I+ ⊆ Σ*-L I-and L I-∩ L I+ = ∅.
3 This relation is easily extended to the regular grammars.

Let consider R a congruence relation, a partition Tree(I) /R from Tree(I) and its regular grammar G R , A GI and A GI /R are the algebra assigned to G I and G R . In the following section, we will define a homomorphism homo R from A GI to A GI /R that formally defines the equivalence classes of A GI -algebra. Then, we will state a constraint satisfaction specification of the (language inclusion) lattice induced by homo R and propose a Constraint Logic Program (CLP [START_REF] Van Hentenryck | Constraint Satisfaction in Logic Programming[END_REF]) that will search, under some constraints, for a (not necessarily minimal4 canonic) DFA in that lattice.

The Quotient Algebra

Let A GI =( ( Q ∪ Σ),Op) be an algebra associated to the (regular) grammar of the sample set I. Terms of A GI are derivation trees (let note them by â or b) of the form ri(rj, rm(..., rk(rn)...) and of some sort q ∈ Q. Let R a congruence relation on A GI . Op is the set of names (like ri) of rules of G I of the form (q', α → q) or (α → q), α ∈ Σ, q,q' ∈ Q. The quotient algebra induced by R is defined by

A GI /R =((Q ∪ Σ), Op) with : 1-(Q ∪ Σ) ={ [ â] | â a derivation tree whose type is q ∈ Q} where the congruence class [â] is defined by [â]={ b a derivation tree of type q ∈ Q | (â, b) ∈ R}; 2-Op=set of ri for each element of Σ,ifri is the name of a production rule of the form α → q with q ∈ Q and ri :[ α] → [q]; 3-Op= set of ri : ([q'], [q"]) → [q] if
ri is the name of a production rule (q', q") → q with q, q', q" ∈ Q is defined by ri(rj,rm( ..., rk (rn)...)=[ ri(rj, rm(..., rk(rn)...)]. A derivation tree [â]inA GI /R is constructed using elements congruent to â ∈ A GI .

Although a term â of A GI is like ri(rj, rm(rl, ..., rk(rn)...) with r i ,r j , ... ∈ Op, for the sake of clarity, we will rewrite â by ri(α, rm(β,..., rk(γ)...) when rj (resp. rl, rn, etc.) is the name of a production rule like α → q (resp. rl : β → q and rn : γ → q, etc.). This is also motivated by the fact that [α] denotes the equivalence class of the constant α whenever

[â]=[α]. We set [α]=α for each α ∈ Σ.
Operations of A GI /R are well defined since R is reflexive, symmetric, transitive and compatible such that from

[â]=[ b] we conclude that (â, b) ∈ R.
Thus, ((AG I )r i1(α1, rj1(α2, ..., rk1(αn)...) , (AG I )r i2(β1, rj2(β2, ..., r k2 (βn)...)) ∈ R implies :

[(AG I )r i1(α1, rj1( ..., rk1(αn)...)] ≡ [(AG I )r i2(β1, rj2(..., rk2(βn)...)].

Equivalently, (r i ,r j )∈R implies r i ≡ r j (same as [r i ] ≡ [r j ]).

Quotient algebra are characterized by the universal property (up to an isomorphism [START_REF] Ehrig | Fundamentals of Algebraic Specification[END_REF]). This property is stated by the following (homomorphism) theorem applied to A GI (proofs out of the scope, avoid self reference) : Theorem 1. Let A GI associated to Tree(I) be the algebra and R a congruence relation on A GI . Then

homo R : A GI → A GI /R defined by homo R (â)=[ â] for â ∈ A GI
is a homomorphism that has the following property.

Letf:A GI → L(A) a homomorphism with the (former) congruence relation R, then there exists a unique homomorphism f such that the following diagram of mapping is commutative, i.e., f = f • homo R .

✲ P P P P P P

P P q ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✏ ✶ f homo R L(A) A GI A GI /R f = Figure 1.

Commutative Mapping Diagram

It can be first showed that homo R is a homomorphism before proving the above theorem. One may note that the quotient algebra will define equivalence classes on A GI . Defining f will let us reach our goal which is to define L(A) from A GI . In the next section, we define a CSP specification by the Congruence predicate that defines the congruence relation R (over the of terms A GI ) and hence characterizes the search space Lat R (see figure below) and the instantiations in it. Then we discuss the properties of I + and I -with respect to L I , L I+ , L I-and L(A).

In the following figure, the top element Σ * of the lattice Lat R represents the set of all the words that can be constructed over the alphabet Σ, and the button element ∅ represents the empty set. This search space contains all automata (one for each element of Σ * ) in which the final automaton L(A) is searched.

The Congruence Predicate

Recall that R is a congruence relation over (the sorts of)

A GI . Let â1 , â2 ∈ A GI where â1 =r i1 (α 1 ,r i2 (α 2 ,r i3 (α 3 ,r i4 (α 4 ,..., r in-1 (α n-1 , r in (α n )...) and ★ ✧ ✦ ✥ Σ * ∅ L(A) ? Figure 2. The search space Lat R â2 =r j1 (β 1 ,r j2 (β 2 ,r j 3 (β 3 ,r j4 (β 4 ,..., r jn-1 (β n-1 , r jn (β n )...).
The Congruence predicate constructs the store θ (a set of constraints) and assigns an equivalence class [q i ] to each q i ∈ Q. The set θ may contain constraints like xi nr ,= and =. Whenever the set of final constraints is satisfiable, if there is more than one solution, then we will choose the one which minimises the number of equivalence classes. Initially, θ = ∅.

In order to extract equivalence classes, this predicate is applied to every pair of (compound) terms of A GI . Within each couple of terms, the predicate is applied to every couple of sub-term of â1 and â2 . Backtracking is used to compute a consistent θ (which characterizes Lat R ). Initially, [q i ] is the equivalence class of each q i ∈ Q. Elements of I + and I -are distinguished, hence we recognize final states (F + and F -with F = F + ∪ F -and F + ∩ F -= ∅) of these two sets from each other and from any other equivalence class.

Predicate Congruence(r1,r2):

adds constraints to the constraint store θ Let r1 and r2 be transition rules (for â1, â2) with α,β ∈ Σ

r1 :[ α] × s ′ 1 → s1 r2 :[ β] × s ′ 2 → s2 (1) if s1 and s2 are different final states in (F+ × F-) then add [s1] =[s2]. (2) if [α]=[β] then add ([s ′ 1 ]=[s ′ 2 ] ⇒ [s1]=[s2]) (The DFA condition) (3) if [α] =[β] then add [s1] = [s2]
Givens the rules r 1 and r 2 above (depicted in the figure 3 below) , the application of the Congruence predicate can produces 3 different configurations (i.e. [s

' 1 ]=[s' 2 ] ∧ [s 1 ]=[s 2 ], [s' 1 ]=[s' 2 ] ∧ [s 1 ] = [s 2 ], [s' 1 ] = [s' 2 ] ∧ [s 1 ] = [s 2 ]).
Although [α]=α is in its simplest form, we introduced the notion of equivalence class for the alphabet using the lexical class function CL(α)=[α] where:

[α]=[β]iffα = β or CL(α)=CL(β), α,β ∈ Σ.
For example, different city names or two (possibly different) organizations (university, research laboratory) are equivalent. Obtaining the final induced automaton is a matter of search in Lat R . This automaton is the solution of a consistent instantiation in the constraint store θ. Among all solutions, we pick up the one the minimizes the number of states.

✖✕ ✗✔ ✖✕ ✗✔

[α] s' 1 s 1 ✲ ✖✕ ✗✔ ✖✕ ✗✔ [β] s' 2 s 2 ✲
The Congruence predicate is implemented as a (compiled) CLP program in GNU-Prolog 5 5 .

This predicate takes as input the sets I + and I -and generates the final DFA which is in turn an executable CLP program representing the induced Grammar. In the application (i.e. test) phase, we try to match the automaton of a new input seminar announcement. In the case of a success, further processing can take place (e.g. slot fillers value assignment in the announcement corpora, as stated briefly in the next section).

The following figure shows a more general case. Note that if we consider α 1 (resp. β 1 )a st h eleft context of α 2 (resp. β 2 ) and α 3 (resp. β 3 )a si t sright context, we will cover, to some extent, the case studied in [START_REF] Califf | Relational Learning of Pattern-Match Rules for I[END_REF]:

✒✑ ✓ s 11 ✒✑ ✓ s 12 ✒✑ ✓ s 13 ✲ [α 1 ] ✒✑ ✓ s 14 ✲ [α 2 ] ✲ [α 3 ] ✒✑ ✓ s 21 ✒✑ ✓ s 22 ✒✑ ✓ s 23 ✲ [β 1 ] ✒✑ ✓ s 24 ✲ [β 2 ] ✲ [β 3 ]

Figure 4. contextes and states

Applying the Congruence predicate to above case will produce 5 different configurations (depending on the equivalence classes of α i ,β i ) with various number of states in which the final induced minimal DFA has 4 states. Constraint store then will decide the final induced DFA considering all transitions and the negative examples.

It is worth emphasize that the Grammatical Induction applied only to positive examples (I + ) tends to overgeneralize L + (see e.g. [START_REF] Ahonen | Applying data mining techniques for descriptive phrase extraction in digital documents[END_REF]). Hence, one may express negative descriptions that are representative of the words to be rejected. For example, we may state that a seminar announcement heading containing the Hour value must be rejected. The I -set of the section 5.5 contains some negative examples for an announcement heading.

An Example

The theoretical aspects and the implementation issues of the related work were validated first by using the experimental protocol cited in [START_REF] Dupont | Regular Grammatical Inference from Positive and Negative Samples by Genetic Search : the GIG method[END_REF]. The following example reports an original one that shows some interesting aspects of the grammatical inference engine.

Example : Consider that I denotes the regular language a n b m , n, m > 0.W eh a v e ,Σ={a, b} with I + = {ab, aabb, aaabbb, aaaabbbb, ...} and I -= {a,b, aab, abb, baa, bab, ...}.

The generated automaton A and L(A) are given below. Here, notations like a/s,f over an arc means that the transition is a part of success (s) or failure (f ) derivation. The tag <s ,f >means that the transition can possibly take to a success or to a failure. It is interesting to note that even though I contains words of the Context Free language a n b n , the above DFA extracts the following underlying knowledge from the sample set I (cf. a n b m ): the DFA recognizes either an even number of a's followed by an even number of b's or an odd number of a's followed by an odd number of b's. But it rejects an even number of a's (resp. b's) followed by an odd number of b's (resp. a's) at the same time (which are words in L -). Obviously, A can not generate that context free language but learns a part of it.

L + = {a (aa) * b(bb) * } ∪ {aa (aa) * bb(bb) * } L -= {aa (aa) * b(bb) * } ∪ {a(bb) + } ∪ {b(bb) + } ∪ {a(aa) + } 0 2 3
Relative to this induction is the notion of grammatical enrichment 6 that may be defined as follows. Suppose that the state [q] is originated from I -. If there is any successful derivation of ω ∈ L(A) containing L([q]), then we say that I -enriches L + . In the above example, For example, bb derived through q 0 q 5 q 2 q 3 is in the enriched L + if ever we do not constrain that derivation to only use success (<s> or <s,f > tag) edges. ment database. An example of such announcement is given below. We want to extract various information such as the Date or the Subject in a seminar. Finals measurements like the research fields of a university (or a researcher, etc.) can then be extracted. In this process whose goal is to extract slot fillers, valuable template slot fillers are already defined by an expert 7 : he/she knows in advance which kind of information is contained (and sought) in the data base.

It is also appropriate to note that a seminar announcement can be incomplete. For instance, the Hour may be missing within an announcement or it can be expressed in a different form (for example, by the "Friday afternoon" expression).

The reminder of this paper describes the use of the Grammatical Inference engine (consolidated by a Bayesian analysis, see the section 5.3) with respect to the textual IE task applied to the seminar announcement corpus.

Slots and Fillers of the Corpus

The following slots are defined for the seminar announcements corpus (abbreviations are further used in the paper). An announcement starts with the seminar (séminaire in French) keyword.

Related Grammatical Inference

In the IE process applied to natural language texts, there are major differences between the Sentence Analysis and the traditional NLP parsers . The goal of syntactic analysis in an IE system is not to produce a complete parse tree for each sentence in the text. Instead, our system needs only to perform partial parsing. That is, it needs only to construct as much structures as the IE task requires.

Current methods (see e.g. [START_REF] Weischedel | Description of the PLUM system as used for MUC-6[END_REF], [START_REF] Appelt | FASTUS system : MUC-6 test results and analysis[END_REF]) use generally global constraints to resolve local ambiguities. But because of the gaps in the grammatical and lexical coverage, full sentence parsers may end up making poor local decisions about structures in order to create a parse spanning the entire sentence.

Furthermore, the syntactic analysis in a text mining process is avoided for several more reasons: -the cost and the complexity of this analysis, -the very few use of the results of this analysis (the goal is not to correct errors or to translate the text), -the texts may not follow the correct and complete syntax rules (of French in our case), etc.

A partial parser looks up for fragments of text that can be reliably recognized, e.g., noun and verb groups. Because of its limited coverage, a partial parser can rely on general pattern-matching techniques, particularly finite-state machines, to identify these fragments deterministically based on pure local syntactic elements. Partial parsing is well suited for information extraction applications for an additional reason : the ambiguity resolution decisions that makes full parsing difficult can be postponed until later stages of the processing where top-down expectations from information extraction task can guide the system's actions.

In our seminar announcement corpus, the subject is similar to a noun group but may not follow its rigorous syntax. Then, the inference stage helps, in this case, to retain effective rules used in the examples. Therefore, the corresponding text mining process will rather be a syntax directed process.

Starting from a sample set (positive examples and negative cases description, see the section 5.5 for an example of GI), the Grammatical Inference (GI) induces a regular grammar8 (a DFA) of this sample set. In the test phase, sentences presented to the grammar will be regarded as pertaining (or not) w.r.t. the language generated by induced grammar.

The Grammatical Inference carries out a classification of the sentences (accept or reject means belonging or not to a given language) but, in its original form, it does not handle the semantics of these constructions. Hence, Bayesian measures will guide the process by predicting the slot and its value (in its context) to be submitted to the grammar. The IE process is then achieved with more precision and reliability (see also [START_REF] Freitag | Using Grammatical Inferenec to Improve Precision in[END_REF]).

Naive Bayesian use

Several techniques of text mining use the Bayesian analysis that (even in its naive form) gives interesting results. In the method known as naive Bayesian, the document is presented as a vector of characteristics (e.g. various sections of an announcement). Other presentations such as bag of words consider the text in the form of a collection of words where any internal structure (physical, logical, morpho-syntactic or semantics) is inhibited.

The Bayesian rule is recalled below. Given a hypothesis (e.g. to have such a section of the class C in such a context inside a seminar announcement) and an announcement E over C,wehave:

Pr(C/E)= Pr(E/C) .Pr(C) Pr(E)
The idea is to express the weighted probability of the membership of a pattern or a sub-language within a class C according to the characteristic of the text E and those of other texts classified as such.

To summarise the current process, key patterns leading to recognize the various (but not all) fillers of an announcement are first defined during the training stage. Together with the key patterns, the frequency measurements and the regular production rules will help to decide (to classify)a section of the announcement. During the test phase, a pattern p first gets a probability to belong to a slot filler by the presence of a deterministic keyword (100 %) and/or by the probability (from the frequency table) of its (possibly left and right) contexts. p is then submitted to the induced grammar according to these probabilities. Failure cases are postponed to the postprocessing step 9 . The process uses the backtracking to consider other possibilities (see section 6 for the Sub filler).

Details of the GI process

It is easy to note that a simple textual search (based on keywords) cannot be appropriate for extracting knowledge from our seminar announcements. Methods of knowledge extraction based on the Bayesian analysis allow to predict the position of a given information in the text together with its average length (see e.g. [START_REF] Freitag | Using Grammatical Inferenec to Improve Precision in[END_REF]). This technique, based on the learning of the position of a section (e.g. the <Sub> section) would not be appropriate here because of the free format of the announcements. In addition, an announcement can be incomplete. Thus, getting the induced grammar of e.g. the <Adr -P lace> section will make it possible to analyse the content of that sub-language.

We use the grammatical inference in various sublanguages (e.g. the heading or the subject of an announcement) that may contain relevant information. As an example, the heading can contain a topic, a subject or an organizer that can be possibly extended in the reminder of the announcement. The subject (Sub) can add precise details to the Topic of the seminar and vice versa. Such complementary data are registered both in the frequency table and hard coded in the production rules. The sequence of operations is governed by the key patterns, the probabilities from the frequency table (table 1) and, finally, by the production rules 10 .

It may be noted that if the Grammatical Induction is processed only upon positive examples (the set I + set below), then the result tends to over-generalise the language induced. Hence, the expert may express negative descriptions that are representative of the words that must be rejected 11 . For example, he may state that a seminar announcement heading containing the Hour value must be rejected. The following example contains some negative examples for an announcement heading (the set I -).

An Example of GI

As an example, the results of the grammatical inference on the heading of announcement follows. The grammar below partially describes what the headings of the sample set contained. Hence, the following I + does not cover all possible headings in all seminar announcements, but those of the sample set.

I+={'SDON', 'S:T', 'S', 'ST','SDT','SàV:T','SN:T', ...} I-={'Sa', 'SS', 'S::T', 'S::L', 'S::N','SDD','SOO', 'Sàà', 'Sa:', 'SD:', 'SaVV', ...} where S : the "séminaire" keyword (seminar in English), D : < Det >, a determinant (e.g., 'du', 'de la', 'des') like 'of' or 'of the' in English T : <Thème> , an exposed T opic -Subject (e.g. Algorithm, Complexity , Internet and Security, etc.), N :< N om >, a Noun, e.g. name of a research laboratory , O : <Org>, an organization name (e.g. institute, laboratory, university, school...)

V : Ville, name of a City, e.g. Toulouse ':' : this character, 'à' : this character (stands for 'at' or 'in', ... in English).

10 However, we are not in the context of the so-called Probabilistic Grammars 11 For the seminar announcement case, negative examples are quite straightforward.

The induced grammar accepts the language L + (the induced language of I + ) and rejects those of L -(the induced language of I -). The final induced automaton accepts the language given below 12 . The rules that reject unsuitable constructions (i.e. words in L -) are not reported here for the sake of clarity. However, one may observe that a rejection takes place in the induced DFA when a derivation (upon a token) leads to a final failure state F -(see the section 5.4). The language of the induced finite state automaton The language induced from the set I =( I + ∪ I -) for the heading part of announcements is given below. Recall that this definition gives only the successful derivation paths.

L+ = "Séminaire" . L1 L1 = || (':' 'à') . L3 || < N om > .L 5|| <Thème> .L 6 L3 = <Org> .L 6|| (<Thème > < V ille >).L1 L5 = ':'. L3 L6 = || < N om > .L 1
Nota Bene: the induced grammar is an operational logical grammar (extended DCG). Predicates expressing constraints and actions are then added to its rules (see the Date example below). As an example of action, while recognizing (in their context):

-a<Thème> may contain a part of the Subject; then the value corresponding to the Subject will be added to the < Sub > filler; -for a <V ille>, the corresponding city value will be added to <ADR -P lace> filler 13 . Other possible adjustment actions are achieved during the post-processing phase.

An example: the Date analyser DCG

Below, some of the induced grammar rules (annotated by their semantical actions 14 given inside brackets) for the < Date > filler are given. The lack of any part of a Date (e.g., the day-name) is not reported here 15 .

< Date >:: ["date"][" : "]["le"][<Day-name >] [<Mid-day >]["le"] < Day > [< Sep >] < M onth > [< Sep >] < Y ear > . <Mid -day >:: <Word> {$1 ∈{"matin"} ; add(part_of _Heure, "8h -12h", 100) OR $1 ∈{"après -midi"} ;
add(part_of _Heure, "14h -18h", 100)}. < Month >:: < N umber > {$1 ∈{1..12} ; add(part_of _Date, $1, 100)} <Word> {$1 ∈{"jan".."dec"} ; add(part_of _Date, $1, 100)}. <Day-name>:: <Word> {$1 ∈{"lun".."sam"} ; add(part_of _Date, $1, 100)}. < Day >:: < N umber > {$1 ∈{1..31}; add(part_of _Date, $1, 100)}. < Year >:: < N umber > {$1 ≥ 1990}; add(part_of _Date, $1, 100)}. < Sep >:: ′ / ′ ′ : ′ ′ -′ ...

--a separator Nota Bene: the value 100 (parameter of the predicate add) indicates the confidence coefficient of the filler assigned to the slot. Here, the case of < Date > is rather simple and follows a known format. We may however note that the presence of "matin/après-midi" (AM/PM in English) of the < Date > will complete the <Hr> slot filler.

Frequency Measurements

The following percentage values is constructed from the input samples. 1. Frequency table of an announcement sections In the above table, a cell C i j gives the frequency (or the Support, see below for a definition) of the column j that followed the line i in the training set. The Pres (Presence) column (the last one) gives the frequency of each element of the line in the training set (e.g. the Sub is present only in 45% of the announcements). We add to this table two other values: 77% of the announcements contain a T opic in their heading, and 18% of the headings contain an indication on the organizer (Org).

The cells containing 0% are of a particular interest because they give indications on the cases that do not occur. For example, <OrgSp>never follows the heading of an announcement.

As an example, we apply the conditional probability to the section Sub of the example of section 5 where the slot of the second line is not determined. This example shows how the post-processing will help deciding that slots filler. Given the table 1 above, the probability so that the unknown section (in the example given in the section 5) is a Subject (surrounded by the Heading and the Speaker) is 12%. However, this announcement does not contain a Subject in its heading and, the Speaker is the successor of a Subject in Note that the strongest probability of the section that follows the heading is the Date section. However, one can recognize a Date by the keywords in the induced grammar.

The depth of the Morpho-Syntactic analysis engine is a system parameter. In some cases, the (partial) linguistic class from this filler can be extracted giving a (partial) Noun Group (even without any initial determinant, see e.g. [START_REF] Appelt | FASTUS system : MUC-6 test results and analysis[END_REF]).

Results for the Example

This section describes briefly some experimentations on the seminar announcement corpus.

For the grammatical induction, the GI process is applied within the morphological step in order to learn to reject useless combinations like those constructions that are liguistically ambiguous and useless for us 16 . Once the learning step is achieved on the seminar corpus, we obtained the following results for the seminar example of the section 5 (confidence coefficient for a filler value is reported at right when it is less than 100; the original database is in French): Org = "Institut de Physique Nucleaire de Lyon" Sub = "Le probleme des conversions de modes" (51) Sp = "Yves Colin de Verdiere" (51) OrgSp = "Institut Fourier Grenoble" (61) Hr = "14:30 H" Adr_Plc= "Salle 27-Rez de chaussee-Bât. Paul Dirac" Adr = "Institut de Physique Nucleaire de Lyon" Date = ""

Performances Evaluation

Several textual IE systems, notably those of MUCs, involved large training corpora with thousands of documents (see e.g. [START_REF] Grishman | Information Extraction: Techniques and Challenges[END_REF]). However, such large training corpora (and their associated templates) may not be available for most real tasks.

Experiments with smaller training collections (such as the 100 documents provided for MUC-6) suggest that fully automated learning techniques applied to a few text examples with minimal automatic syntactic processing may not be able to achieve sufficient coverage (see e.g. [START_REF] Fisher | 96 et all. Description of UMass system as used for MUC-6[END_REF]).

We paid a special attention to the over generalization pitfall of the GI engine. An amount of work was done testing the engine on different corpora (bibliography, abstract, table of content, etc.) in to improve the induction algorithm. The GI engine is parametric such that several different degrees of generalization 17 can be set (by varying the constraints over the language-inclusion lattice of automata). The output automaton is then tested against 16 Here, some linguistic knowledge is required to eliminate useless lexical class combinations from morphological analysis. 17 Three for the moment the training set and the one (that accepts all positive examples rejecting all negative one) with the least number of states is chosen. One may observe that the refinement operator is hard-coded within the the Congruence Predicate of section 4

In addition, another parameter is available in the GI engine the turns on-off the so-called enrichment issue (section 4.1).

However, we are aware that larger sample sets (and other domain specific corpora such as abstract scanning) are needed to improve the system. Larger sample set has however an inconvenience. Recall that the search space is given by the lattice of language-inclusion specified by the GI process and illustrated by the Congruence Predicate. This search space grows exponentially with the size of sample set I.

Starting with 300 examples, we applied a ten-fold cross validation and observed that the results were not significantly changed for more examples. Metric used : in the IE task (i.e. the corpus is known to contain announcements), evaluation metrics are based on the filler presence and prediction.

P recision =

N umber of Correctly assigned slots N umber of assigned slots Recall = N umber of Correctly assigned slots N umber of correct present slots

In addition, an harmonic measure called F-measure (see e.g. [START_REF] Lehnert | A performance evaluation of text-analysis technologies[END_REF]) is used to give the mean of the above values:

Fmeasure = P recision × Recall The diagram of the figure 5 shows the performance percentages we obtained.For the seminar announcements corpus, it is not surprising to have high performance values (95% and 80%) given the intended slots and the relative low risk of error. The system is quite domain specific and may even be enhanced. Student work is currently done to adapt the system to other corpora.

The Related Work

Several textual IE system have been proposed since the focus on researches started by MUC program of DARPA (e.g. [START_REF]Proc. of 4th and 5th DARPA Message Understanding Evaluation and Conference[END_REF], [START_REF] Lehnert | A performance evaluation of text-analysis technologies[END_REF]).

The use of pattern dictionary is common to many systems. Some uses clustering to create patterns by generalizing those identified by an expert (see e.g. [START_REF] Soderland | Crystal : inducing a conceptual dictionnary[END_REF]). The dictionnary used during the analysis. step contains basically keywords (and their lexical class).

Syntactic information can be used as in Autoslog ( [START_REF] Riloff | Atomatically constructing a dictionnart for information extraction tasks[END_REF], [START_REF] Riloff | Atomatically generating extraction patterns from untagged text[END_REF]) that uses a set of general syntactic patterns validated by an expert. Among these systems, some uses advanced syntactic analysis to identify the relationship between the syntactic elements and the linguistic entities (e.g. in [START_REF] Huffman | Learning information extraction from examples[END_REF]). This analysis is costly (when the semantic information is not used) and may limit the system specially if linguistic rules are not respected (like in our seminar examples).

In many IE systems, human interaction is highly required through different phases of training. Machine Learning techniques like decision trees are used ( [START_REF] Mccartht | Using decision trees for coreference resolution[END_REF]) to extract coreferences using the annotated coreference examples.

Among these systems, the current work is closed to PA-PIER system ( [START_REF] Califf | Relational Learning of Pattern-Match Rules for I[END_REF]). RAPIER is an ILP system that takes pairs of documents and filled templates and induces rules that directly extract fillers for the slots in the template. This system uses constraints on words and part-of-speech tags surrounding the fillers' left and right contexts. To some extent, our system can be seen from this point of view since, as mentioned in the GI (section 4), our grammatical Inference engine implements this technique implicitly. In addition, these results should be compared with those of the Named-Entity research work (see e.g. [START_REF] Bikel | An Algorithm that Learns What's in a Name[END_REF]) and aims to learn names by identifying all named locations, persons, organizations dates and so on.

Conclusion

In this paper, a new constraint satisfaction framework for GI has been presented and implemented by an operational constraint logic program that outputs the final DFA. Here, the algebraic specification gives a theoretical framework to state why some processing are done (e.g. merged states) before explaining how we do process. This specification allows to show that the homomorphism f (section 3.1) exists and we gave an implementation of it by the Congruence predicate which produces a set of constraints. If this set is satisfiable, then we choose a solution with the fewest number of states. Among other works in the field, [START_REF] Ahohen | Forming Grammars for structured documents[END_REF] and [START_REF] Lindžn | Structured Document Transformation[END_REF] proposed similar methods for document analysis. But in the algebraic and constraint satisfaction frameworks of the Grammatical Inference, the logical aspects for the direct grammar extraction have, as well as known, not yet been investigated.

This work was initiated in a (paper) document processing project where GI results are used to classify and then translate documents into machine readable form. Other applications dealing with more general multimedia contents (video in particular) are under the study.

The code in GNU-Prolog of the realization is available from the author.

On top of the GI part, we designed and implemented an IE system that fills slots of a template associated to seminar announcements using Bayesian measurements. Once the template are slots filled, usual techniques of Data Mining can applied to the results since the resulting values of the slots describe simply a relational database scheme. One current use of the system is to extract information like the research field of universities, laboratories or researchers. That is, to guide PHD students in their researches. This is a work in progress and the performance results are encouraging to continue the project. We plan to first enhance and then extend the system to other corpora like job announcements and marine weather announcements. The aim is to establish statistics on marine catastrophes and previsions. The system will be integrated to a (database) Datamining engine in order to establish valuable information on marine events.

Figure 3 .

 3 Figure 3. transitions for r 1 and r 2

<

  Sub > the (general) T opic and the Subject of the seminar, <Org > the organizer, i.e. a university, lab.,... < Adr -Plc>the address and/or the place where the seminar takes place, <Sp> the person who will make the talk, <OrgSp> the organization of the Speaker (e.g. the research lab. of the Speaker), < Date > the date of the seminar, <Hr> the beginning hour (or the time range) of the seminar.

1 2 (Figure 5

 25 Figure 5. Performance evaluation

Table

  Here, OrgSp abbreviates Organizer -Speaker , Pres stands for P resent , Sub for Subject , Plc for P lace , Hr for Hour and Sp for Speaker :

		Sub	Org	Date	Hr	Plc	Adr	Sp	OrgSp	End	Pres
	Ance	14	9	41	4	14	14	9	0	0	100
	Sub	0	0	4	0	9	0	23	0	9	45
	Org	0	0	4	0	4	0	0	0	0	9
	Date	0	0	0	77	9	0	4	0	4	95
	Hr	9	0	4	0	41	0	18	0	14	86
	Plc	4	0	23	0	0	36	4	0	23	91
	Adr	4	0	9	0	4	0	0	0	32	50
	Sp	4	0	9	0	4	0	0	36	4	59
	OrgSp	14	0	0	4	4	0	0	0	14	36

Various sectionslike the address section of a seminar announcement are handled in turn.

Opposite to overfitting, the extreme case of the over generalization for an alphabet Σ is the language Σ*.

"not necessarily minimal" is to be considered in a grammatical point of view, w.r.t. the number of states. The induced grammar is actually minimal w.r.t. all constraints specified in the Congruence predicate (section 4)

The final induced automaton is an extended DCG ([START_REF] Colmerauer | Metamorphosis grammars[END_REF])

The Text Mining ApplicationAs mentioned above, we used the GI system to extract linguistic structure of different parts of a seminar announce-[START_REF] Van Hentenryck | Constraint Satisfaction in Logic Programming[END_REF] similar to the well known version spaces.

The expert in this domain is just a scientifique-researcher familiar with such seminar announcements

We note that the Context-Free grammar induction is an actual and active research filed facing hard constraints making the general Context Free induction problem no-decidable.

e.g. in the case of ambiguity (or failure on p), if a pattern p ′ (p ′ = p) has been successfully recognized to fulfill a slot filler, the pattern p is tried against other related sections. Several lookup may be necessary in more complex cases. A blind application of the induced production rules is the last chance.

Notation: (X Y ) means (X or Y ). The dot denotes the monoid concatenation and ε denote the empty string.

[START_REF] Ahohen | Forming Grammars for structured documents[END_REF] In the <Adr -Plc>

context.[START_REF] Lindžn | Structured Document Transformation[END_REF] a semantical action is a term from the syntax directed and the Attributed Grammars paradigm which denotes (no syntactic) actions based on the attribute values. Distinguished from the pure syntactical analysis, such actions take place in a production rule if the

rule applied.[START_REF]Grammatical Inference : Algorithms and Applications[END_REF] [x] means an optional x; $k denotes the value of the k th literal (a.k.a. yacc compiler compiler).

cases. Therefore, the filler is predicted at 23% (weighted 51%) to be the Subject.