Jean-Loup Terraillon

ESA UNCLASSIFIED -For ESA Official Use Only Digital transformation in the European Space Industry • Category: Regular Paper

Keywords: Model-based system engineering, digitalisation, space, spacecraft

Digitalisation is a trend in most industrial domains. The Space domain has embarked on it a couple of years ago. Starting from a Model Based for System Engineering initiative, the discussion between Space Agencies and Industry has intensified with several topical working groups. The scope has been enlarged, from MBSE, to full engineering digitalisation, aiming at producing the enablers that will allow to develop digital twins. The paper describes and positions the ESA digitalisation project, as a joint Space Community endeavour, proposing a development approach, and giving programmatic elements as well as the initial panorama of MBSE deployment in Space projects.

CONTEXT

The ESA Agenda 2025 [START_REF]Make space for Europe[END_REF] is a document prepared by the European Space Agency Director General when he took up duty, and indicating to the Space Community, and in particular the ESA Member's States Delegations, the directions for the next four years. It says in particular:

• "In Europe, ESA has the unique ability to implement, together with industry, complex and ambitious space missions and programmes on an equal footing with other leading space agencies worldwide. We will ensure that this ESA strength and value is further reinforced." • "ESA will therefore digitalise its full project management, enabling the development of digital twins, both for engineering by using Model Based System Engineering, and for procurement and finance, achieving full digital continuity with industry."

Digitalisation is the process of representing all the artefacts of space systems under a (structured) digital representation, on which computers can reason and elaborate. The most explicit example of such digitalisation process is the Model Based technique, where the information, traditionally contained in the form of documents, is instead expressed in a set of data, structured into a model. Computers can be programmed to navigate and search into the models, and create relations between associated data, allowing to discover more properties, and to derive added value such as traceability, optimisation, technical budgets, trends, and knowledge.

Digitalisation includes also e.g. databases or excel sheets, or any format where data is structured, curated and associated to a semantic that allows to unambiguously understand it with a computer. This transformation relies on common standards and new infrastructures that facilitate the exchange of data but also the collaboration along the whole supply chain.

THE DIGITAL SPACECRAFT

General Concept

Digitalisation is under way in many domains: automotive The Digital Spacecraft is a concept derived from these similar initiatives, and introduced in ESA to cover the digital transformation of space, ground, launcher segments development and operation, as a new way to collaborate within the space ecosystem throughout the full project lifecycle. It is based on digitalisation and combines as an umbrella a wide spectrum of topics like MBSE, digital transformation, digital twins and full data integration into a single consistent concept covering all aspects related to a spacecraft.

Digitalisation is already ubiquitous in the engineering domain. It allows expressing the concept of operations, structuring the requirements, and tracking them through design and manufacturing up to testing. It is intended to support the optimisation of the design, to make informed trade-offs and to clarify the interfaces. It allows the systems engineers and the project teams to master the complexity of the space system, relying on an authoritative source of truth of the system, communicating knowledge and exchanging data in an unambiguous way. It enables quick access to key parameters via dashboards, understanding the impact of changes and managing those, building knowledge from lessons learned for optimisation and/or for future reuse. It also allows maintaining a continuous and homogeneous flow of information between the different disciplines of the system, along its life cycle, and across its supply chain.

Besides engineering, project management and product assurance are also transitioning to digital, supporting the workflows related to schedule, changes, deviations and non-compliances in an automated, traceable and searchable way. Finally, procurement complements the picture with the digitalisation of the steps included in the preparation of the Invitation To Tender (ITT) package, management of the resulting contract, deliverables, contract change process and the contract closure, associated to adequate legally compliant processes.

Space domain characteristics

Producing spacecraft would not appear a priori much different from producing aircraft or cars. The overall life cycles are similar (specification, design, manufacturing, tests). However: Therefore, the Space domain must deploy digitalisation in a context constrained by contractual rules, processes, organisation and technological heritage. This boils down to an essential need: interoperability of all the tools, across disciplines, along the life cycle, and through the Supply Chain. This need appeared in 2018 during a workshop organized by the French Space Agency (CNES) on MBSE [10], where it appeared clearly that industry had internally matured some digital technology, but was facing issues in the collaboration between the stakeholders of a project. ESA had therefore a harmonisation role to play.

A Joint European Vision

Digital transformation of space systems is an ESA Member States endeavour.

Digitalisation is a change process. The key of its efficiency is the digital continuity in the three dimensions of space systems development: disciplines, life cycle and supply chain. This means that all space actors are essential for digitalisation. Space actors are not progressing at the same pace, though: some are more advanced in functional system engineering, other in manufacturing, disciplines are not evenly digitalised, and principally, The success of the change process will be as strong as its weakest link. Consequently, a widespread, staged development and incremental implementation approach is of strategic importance to bring all industrial actors at the same level, and this is where ESA and its Member States have a role to play.

The most important change lies on the new "ways of working" even more than on evolving the processes and tools. Digitalization is not about doing what we are currently doing better or in a smarter way, it is about changing what we do and the way we do it. The Digital Spacecraft is a way to change drastically the way Agencies, primes and supply-chain work together, switching from a 100% customer/supplier relation to a mix between coengineering approach and contractual relation. This mind-set change is the key enabler for future European success and digitalization is its enabler. Digital engineering come along with higher transparency, trust, partnership and objectives alignment.

A multi-level harmonisation forum

Digitalisation involves the space European community through a number of European joint agency-industry working groups led by ESA:

• the MB4SE

• the Digital Spacecraft Think Tank [13]

This multidisciplinary group has been established in December 2020, with ESA and Industry (i.e. Airbus Defence and Space, Thales Alenia Space, Ariane Group, RUAG and OHB/MT Aerospace). It was established by ESA's Executive Board to engage in identifying and harmonizing the steps to be undertaken for the digital transformation of the end-to-end space mission development and operation, with the aim to be beneficial for all stakeholders in terms of technical efficiency, schedule and consequently costs. This team was mandated to prepare a detailed plan for the progressive deployment of the Digital Spacecraft approach across the Agency in close cooperation with industry.

The Think Tank is steered by a Digital Spacecraft Steering Committee gathering higher managerial levels of stakeholders in view of endorsing the plans and empowering the teams.

Figure 1 depicts the digitalisation as a rocket, where the stages and boosters are the working groups of industry and agencies, delivering the Digital Spacecraft in orbit… IT platform and Data Management are addressed in 3.3 and 3.4.

Figure 1 A systematic, multilayer, collaboration

In the Digital Spacecraft Think Tank, several discussions were held on the definition of the Digital Spacecraft and on the support of the "Digital Transformation", which is a myriad of new thinking and development in the areas of data and lifecycle management, throughout the entire ecosystem, and that can present many unforeseen challenges. The term "Digital Spacecraft" represents a concept for an end-to-end digital continuous way of working on space missions in the European ecosystem. Leveraging the new breakthroughs on coupling the simulation results with physical data in continuous synch (digital twin technologies), the Digital Spacecraft allows for feedback and learning (e.g. from operations back to development, and among projects). The Digital Spacecraft therefore enables understanding, learning, reasoning and dynamically recalibrating models, for an improved decision-making.

DIGITALISATION IMPLEMENTATION

Principle

The goal is to identify the digital threads occurring in Space projects, such as to ensure the digital continuity in three dimensions.

• The data shared between disciplines should be defined and understood the same way by everyone, and exchanged continuously between engineers. • The Spacecraft data state reached at a particular milestone of the life cycle should be propagated in the next phase, in order to ensure traceability and avoid distortion along the development.

• The relationship Customer-Supplier should be based on exchanges of models and data rather than of documents.

To identify the data threads, it is necessary to identify the processes followed by these data, as well as the overall data model. The processes indicate the exchanges between the disciplines or the stakeholder, i.e. the point where we want to be interoperable. Defining process and data at the global level of a spacecraft will fail. Instead, applying the concept of divide and conquer, the identification of processes and data models is first done at discipline level, for which relevant experts can support the local digitalisation of the discipline that they know.

In a second step, putting together the data models shows that some data are shared between disciplines. For example, the system product tree is used by Product Assurance, the centre of gravity of the CAD tool is used by the control system, etc. It is essential that the two disciplines have the same understanding of the shared data: same meaning (dry mass, wet mass), same referential, same units, same structure, same financial reference (for cost data), etc. This means that each data must have a unique semantic for everyone.

Defining the common semantic of data is done at the level of an ontology, which is commonly discussed and agreed in the OSMoSE group [12]. Indeed, a set of data can have a physical representation (e.g. XML), a logical representation (e.g. a meta-model), and a conceptual representation (an entity-relation concept, called here ontology). The ontology language selected is ORM [12], [14]. ORM allows to define the agreed entity-relationship of the data set, as well as (thanks to the specific mechanism of "derivation"), any semantically equivalent expression preferred by one or another stakeholder. This semantic equivalence allows generating automatically a physical representation of the data set appropriate for each stakeholder, as well as the tool that translates one format into another one. This allows achieving what is called "semantic interoperability" (Figure 2).

It is therefore key that the data sets identified by each disciplines are abstracted into an ontology, all ontologies are harmonised into a single "Space System Ontology (SSO), allowing for semantic interoperability of the tools between the disciplines. This applies in the same way to the exchanges between customer and supplier. • alignment of the data models with help of the Space System Ontology • deployment in the Supply Chain to exchanges between each level of the Customer Supplier relationship.

Figure 3 Illustrative example of Digitalisation of each discipline, then digital continuity, then data exploitation

Some disciplines are illustrated here; they need [START_REF]Make space for Europe[END_REF] to increase their level of digitalisation, using model-based or other techniques, (2) to identify where are the data in the process, (3) to identify their own set of tools that will later be connected to achieve digital continuity. When these digitalisation enablers are available, data are exploited (4) to optimise and reuse designs, to produce digital twins, to verify test coverage, to make model correlations with the actual data of the physical items. The "as operated" twin is the ultimate achievement allowing managing efficiently the operations of the real spacecraft. Design2Produce is an ESA R&D programme.

Figure 4 Artist impression of the propagation of digital continuity along the supply chain

The digitalisation enablers are connected through the Supply Chain, generally between the same discipline, allowing experts to work together. Depending on the metier of the Supplier, only some disciplines need to be connected.

The IT Platform

The next issue is the one of the informatics environment supporting the digitalisation. At ESA, it is called "IT Platform". It should ultimately be similar to an (Extended) Enterprise Architecture. This paper will not address the "corporate" part of it dedicated to management, contractual or financial aspects.

Figure 5 is an attempt to understand which tools, presently used in ESA, should be connected to ensure digital continuity.

The main interest of the figure is its complexity that illustrates the difficulty to implement such a platform. In this figure, all discipline tools are connected to a central exchange tool called "data hub", making sure that everyone has the right value of the right data at the right time.

Figure 5 status of spacecraft engineering tools to be included in an IT platform

At the bottom are the system tools: requirement engineering, functional, mechanical, and electrical. The discipline tools come as an umbrella around the central Data Hubs (early phase, later phase, and ground segment specific). The data hub is connected to the IT Platform and the (extended) Entreprise. COMET is used in early phases of spacecraft development (called phase 0/A/B1) to centralise all the data of the discipline involved in the concurrent design. Data refreshed by one discipline are immediately pushed to the others. This allows converging quickly during the early mission and spacecraft concept definition. COMET is also used in an activity called Digital Engineering Hub Pathfinder (DEHP) [START_REF]the ECSS-E-TM-10-25 Tool Ecosystem A[END_REF], where it intends ultimately to connect all the tools depicted in Figure 6.

Figure 6 The spoke wheel concept of the Engineering Hub (courtesy Rhea)

This wheel shows that, up to phase B1, the number of tools is "relatively" limited. The complexity arrives in later phases, where the complete workshop of engineering, operations, product assurance and management tools are deployed. ESA is running some activities (not yet completed) to develop Data Hubs for future phases.

Data management

Digitalisation is not yet fully achieved once data threads are identified and IT Platform is available... Other issues appear such as:

• data ownership and visibility: in the relationship between customer and supplier, the exchange of documents has traditionally allowed the supplier to control the visibility that he wanted to give to his customer on the design. However, "you cannot hide behind the data". Delivering the supplier model can expose a lot of information, including some know-how, to the customer. ESA observes more and more industry reluctance to deliver some models, whereas ESA needs it to perform his tasks. It is important to establish a relation of trust, of course supported in a legal frame, allowing the supplier to know which data are needed by the customer and to do what. • this applies not only to the verification performed by ESA projects teams on industry design and tests, but also to the ESA reviews. Reviews are milestones in the life cycle where the status of the project is analysed, is compared to an expected maturity at that stage, and results into mitigation actions to palliate the potential weaknesses. ESA reviews are often done by independent reviewers, working for ESA, but not directly in the project team. This raises the question of visibility that the reviewers should get on the models. It should be enough for them to detect flaws, but less than the one given to the project team.

Another issue is the ability of the reviewers to understand models, and the appropriate packaging of these data for reviewers. For example, reviewers could have only a web interface access to the model, supported by documents giving the context of the model, the "user story". • security: even with the best trust relationship, informatics exchanges are subject to security threats, and it is vital for companies to implement security measures at all levels. This requires a threat analysis, in order to decide where the protections must be placed. The design of the IT platform is generally necessary to understand where the threats are.

These topics need to be addressed at a different level than the pure technical level. They are discussed in the space community in the Data Management working group, a sub-group of the Digital Spacecraft Think Tank (Figure 1).

STATUS IN ESA PROJECTS

To date, digitalisation is mainly deployed in ESA projects through the Model Based System Engineering (MBSE) techniques. It addresses the functional part of the system with some links to physical architecture. But the link with the physical world (CAD, testing, etc.) is not yet achieved. Figure 7 shows the ESA projects implemented with MBSE. MBSE is now introduced in the beginning of the life cycle, as early as the CDF study in phase 0. Supported by ESA, models are then developed, by ESA or industry, in phase A and B1 and then propagated to phase B2.

ESA is working with Large System Integrators, which uses different MBSE technologies. Tools like Capella, Cameo, Entreprise Architect or Genesys are used for similar purpose of functional description. As said before, it is impossible to impose the same tool to all. For its own purpose, ESA will favour SysML (with a particular profile called "MBSE Space") and Cameo, although Science projects like Euclid and Plato are based on Entreprise Architect. However, ESA is able to work with any of these tools. A competence centre has been established to provide licences, tool support and training to projects.

In order to prepare the digitalisation of projects, a large R&D plan over 5 years has been established, in a Harmonisation process within Member States, addressing methodology, ontology, tooling, and project deployment. A low Technology Readiness Level call for ideas [18] has been made, resulting in the funding of 22 activities. The difficulty resides in the mandatory coordination of all the R&D activities of ESA and industry towards the same goal of interoperability and digitalisation.

TOWARDS DIGITAL TWINS

The availability of digitalisation enablers open the way to the exploitation of data. System engineers have access to dashboards of key parameters offering a synthetic view of the system, allowing design optimisation, traceability to reply to such questions as "What if this equipment is not compliant?" or "what if I introduce this change?".

Further, the measure of the real values of the data on the physical items can be fed back into the models used for the design (this is called "model correlation"), allowing to sue better models in the next project (thermal models, structural models, environmental models, control models, etc.).

The same applies to simulators, which -when fed with the real data of the physical item measured during operation -becomes dynamically representative of the physical item, and are called digital twins. Twins of avionics equipment may be used to anticipate software verification before the availability of the hardware. With proper mechanical sensors inserted in the structure (e.g. with use of Advanced Manufacturing methods), a twin of the structural model can be produced. Finally, the connexion of the operational simulator to the real telemetry downloaded from the spacecraft allows having a spacecraft twin, representative in real time of the real one, and much closer to the one located at hundreds or millions of kilometres… Failure investigation and operation optimisation and prediction are example of capabilities enabled by the digital twin.

Beside the Spacecraft related twins, ESA (through the Earth Observation directorate), has launched the Digital Twin Earth [19]. It will help visualise, monitor and forecast natural and human activity on the planet. The model will be able to monitor the health of the planet, perform simulations of Earth's interconnected system with human behaviour, and support the field of sustainable development, therefore, reinforcing Europe's efforts for a better environment in order to respond to the urgent challenges and targets addressed by the Green Deal.

Similar twins for e.g. scientific data of the universe, or human data of astronauts, are investigated.

CONCLUSIONS AND RECOMMENDATIONS

Empowered by the Director General, in line with the strategic technology objectives, ESA has embarked in the change process to digitalisation. ESA is not alone. The change is supported by, and performed together with, the whole space community, national Space Agencies, and Industry.

Aiming at the digital continuity in space projects thanks to the interoperability of tools, a step-wise approach is planned. Many local progresses have been made, but the dots need to be connected. Several discussion forum are organized, allowing Agencies and Large System Integrators to progress together within industrial or programmatic constraints. The next step is to involve better the low end of the Supply Chain.

The main challenges are to maintain the synchronisation of the whole process, to keep awareness by dissemination, to convince gradually all the community without imposing, to ensure the communication of the progress and difficulty between all the actors such that we can solve the problems together, and to survey any opportunity to introduce digitalisation.

  [2], railways [3], aircraft [4], construction [5], airports (Schiphol twin) [6], medical [7], Eurocontrol [8].

FigureFigure 3

 3 Figure 2 Semantic interoperability

  This architecture is inspired by the ESA IT platform of the Concurrent Design Facility [15] called COMET[16]

Figure 7

 7 Figure 7 Status of MBSE introduction in ESA projectsMBSE was first introduced in Euclid, thanks to the presence in the team of a SysML guru who needed to solve a particular problem: the payload operation planning. He shared a preliminary model with the scientist community, and they found beneficial to collaborate on it. The model was further developed to include the payload architecture, then the platform/payload interface, etc.

  Advisory Group [11] , This group has been established in 2019 with the objective to deploy Model Based System Engineering in Space projects. It includes five space agencies (ESA, CNES, DLR, ASI, and UKSA) and four Large Systems Integrators (ADS, TAS, OHB, and ArianeGroup). It advises ESA on the technical aspects of MBSE research and development, and mainly on interoperability of tools, through the seamless exchange of the associated data. The MB4SE AG serves as Steering Group of the OSMoSE Governance [12] group. The "Overall Semantic Modelling for System Engineering" initiative arises from the need of enhancing the way information and knowledge is exchanged among the stakeholders involved, enabling efficient interoperability among model-based infrastructures used. The OSMoSE initiative addresses interoperability at semantic level, merging all stakeholder's concepts into a global conceptual data model resulting in the so-called Space System Ontology (see 3.1).

  The Digital Spacecraft is more a set of digitalisation enablers, than a single product, or a particular technology. It includes a number of technologies such as Model Based System Engineering (MBSE), Computer Aided Design (CAD), simulation techniques, Augmented, Virtual and Mixed Reality (AR/VR/MR), Artificial Intelligence (AI) and various communication, collaboration and project control and management technologies at infrastructure level.

Beside the technological challenges, data management and governance is an essential topic to be addressed together, without which the whole initiative could fail.

But the success already observed, and the positive feedback received by project managers and industry, indicates that we are in the right direction. Let us get digital!


Amaury Habrard
email: amaury.habrard@univ-st-etienne.fr

Marc Bernard
email: marc.bernard@univ-st-etienne.fr

Marc Sebban
email: marc.sebban@univ-st-etienne.fr

Detecting Irrelevant Subtrees to Improve Probabilistic Learning from Tree-structured Data

Keywords: data reduction, tree-structured data, noisy data, stochastic tree automata

In front of the large increase of the available amount of structured data (such as XML documents), many algorithms have emerged for dealing with tree-structured data. In this article, we present a probabilistic approach which aims at a priori pruning noisy or irrelevant subtrees in a set of trees. The originality of this approach, in comparison with classic data reduction techniques, comes from the fact that only a part of a tree (i.e. a subtree) can be deleted, rather than the whole tree itself. Our method is based on the use of confidence intervals, on a partition of subtrees, computed according to a given probability distribution. We propose an original approach to assess these intervals on tree-structured data and we experimentally show its interest in the presence of noise.

Introduction

The use of structured or semi-structured data is increasing in research domains such as knowledge discovery in databases or machine learning. One of the main reasons of this trend is the fact that modern Address for correspondence: EURISE, Faculté des Sciences, 23 rue du Dr Paul Michelon, 42023 Saint-Etienne cedex 2, France data are often stored in relational databases that provide a higher expressiveness. Thus, it is in the interest of machine learning and data mining approaches to take advantage of the structure of data in order to infer better classification models. The increasing interest for directly dealing with such data has led to the new so-called multi-relational learning field [START_REF] De Raedt | Data mining in Multi-Relational Databases[END_REF].

While a linear representation is sufficient for treating single relational databases, more complex structures, such as trees or graphs, are required for modeling multi-relational databases. In this paper, we focus on tree-structured data which provide an interesting compromise between graphs and linear representations. Actually, trees permit the expression of hierarchical dependences and are less costly, from a computational point of view, than graphs. A lot of applications can be modelized using tree-based representations such as in medicine and biology. Moreover, two main fields have recently stimulated the interest for tree-structured data. The first one is natural language processing, which consists in building language models from a set of sentences. In this context, the tree representation, called Treebanks, allows one to embed the grammatical structure of a sentence. The other field, probably the most active one, concerns applications issued from the World Wide Web. Indeed, tree-structured data are natural candidates to represent the information available on the web, such as XML data. Because of the huge quantity of available information, it becomes necessary to have efficient Machine Learning or Data Mining approaches to deal with such data.

From a data mining standpoint, new approaches have been proposed for specifically extracting knowledge from a set of trees. The probably most interesting trend consists in adapting the well known algorithm Apriori [START_REF] Agrawal | Fast Algorithms for Mining Association Rules[END_REF] to tree-structured data. Apriori, proposed by Agrawal and Srikant in 1994, aims at extracting frequent itemsets, that are objects appearing with a significant number of occurrences in a database made of flat representations. In [START_REF] Zaki | Efficiently mining frequent trees in a forest[END_REF], Zaki proposed an adaptation of this approach to extract all frequent subtrees from a forest. In [START_REF] Termier | TreeFinder: a First Step towards XML Data Mining[END_REF], Termier et al. proposed a similar work based on an approximation procedure, which decreases the computational cost. Miyaharah et al. [START_REF] Miyahara | Discovery of Frequent Tag Tree Patterns in Semistructured Web Documents[END_REF] proposed to extract edge labeled tree patterns. More recently, Nijssen and Kok [START_REF] Nijssen | Efficient Discovery of Frequent Unordered Trees[END_REF] extended the previous approaches to unordered tree patterns.

From a machine learning point of view, several approaches have been proposed to learn tree patterns. In [START_REF] Goldman | On Learning Unions of Pattern Languages and Tree Patterns[END_REF], Goldman et al. presented a polynomial algorithm able to learn union of tree patterns from a constant number of patterns. Amoth et al. studied an exact inference method to learn unordered tree patterns from a set of unordered trees [START_REF] Amoth | On Exact Learning of Unordered Tree Patterns[END_REF]. Grammatical Inference presents also an interesting framework for learning models from a set of trees. The objective consists in inferring a grammar representing a tree language that corresponds to the learning sample. The grammar can be represented by a tree automaton [START_REF] Comon | Tree Automata Techniques and Applications[END_REF][START_REF] Gécseg | Tree Automata[END_REF] allowing to define a concept. In this framework, Knuutila [START_REF] Knuutila | Inference of tree languages from a finite sample: an algebraic approach[END_REF] proposed to learn finite tree automata from positive and negative learning trees. García and Oncina [START_REF] Garcia | Inference of recognizable tree sets[END_REF] proposed to learn tree automata from skeleton trees, that are trees without label on internal nodes. To avoid the use of negative examples, Rico et al. [START_REF] Rico-Juan | Probabilistic k-Testable Tree-Languages[END_REF] dealt with the learning of specific tree automata, called k-testable tree automata. Another approach to avoid the use of negative examples consists in learning statistical models. In this context, the objective is to infer stochastic tree automata that allow to define a probabilistic distribution over a set of trees. Carrasco et al. [START_REF] Carrasco | Stochastic Inference of Regular Tree Languages[END_REF] proposed an adaptation of previous works of Knuutila [START_REF] Knuutila | Inference of tree languages from a finite sample: an algebraic approach[END_REF] and García and Oncina [START_REF] Garcia | Inference of recognizable tree sets[END_REF] in order to learn stochastic tree automata. Rico et al. [START_REF] Rico-Juan | Stochastic k-testable Tree Languages and Applications[END_REF] also extended their own work to learn k-testable stochastic tree automata. Various applications on tree-structured data used the grammatical inference framework based on trees. Abe et al. [START_REF] Abe | Predicting protein secondary structure using stochastic tree grammars[END_REF] applied stochastic tree automata to predict the secondary structure of proteins represented by trees. Kosala et al. [START_REF] Kosala | Information Extraction in Structured Documents using Tree Automata Induction[END_REF] used the k-testable approach to extract knowledge from XML data. Habrard et al. [START_REF] Habrard | Generalized stochastic tree automata for multi-relational data mining, 6th International Colloquium on Grammatical Inference[END_REF] proposed a generalization of stochastic tree automata to extract tree patterns and then allow knowledge extraction from medical data [START_REF] Habrard | Multi-Relational Data Mining in Medical Databases[END_REF].

Machine learning and data mining algorithms dealing with structured data have to overcome the same couple of drawbacks than the one imposed by unstructured data. First, in front of modern databases, they require to process huge amounts of data. This algorithmic constraint becomes particularly important in the context of tree-structured data which are obviously harder to process than linear representations. Second, they also have to deal with a high level of noise, which can have dramatic impacts on the quality of the inferred models. In such a context, a classic strategy consists in removing some instances from the dataset which are either irrelevant, because of the weak information they provide, or detected as being noisy. These tasks are the matter of data reduction which can be achieved via two ways: prototype selection (PS) [START_REF] Wilson | Reduction Techniques for Instance-Based Learning Algorithms[END_REF] and feature selection (FS) [START_REF] John | Irrelevant Features and the Subset Selection Problem[END_REF]. It is important to note here that these methods usually require counter-examples and aim at totally deleting either an example (PS) or a feature (FS). Originally proposed to tackle the problem of storage requirements of case-based learning algorithms, such as k-Nearest-Neighbors [START_REF] Cover | Nearest Neighbor Pattern Classification[END_REF], data reduction techniques have rarely been applied, so far, to structured data.

In this paper, we focus more specifically on the ability of data reduction techniques to deal with irrelevant or noisy instances. We propose an approach allowing to detect such data in a set of trees. In this context, we can assume that only some particular subtrees of a given tree are noisy or irrelevant and then deserve to be removed. The suppression of a subtree can be seen as a hybrid approach of data reduction. It looks like prototype selection when a tree is completely deleted, and it looks like a local feature selection when only subtrees are removed. Recent complexity theoretic results show that the problems of PS and FS are NP-hard [START_REF] Nock | Sharper Bounds for the Hardness of Prototype and Feature Selection[END_REF]. This advocates of the use of heuristics for selecting relevant instances in a set of trees.

The goal of our approach is to improve the learning of probabilistic models from a set of trees in the presence of noise. In the probabilistic framework, the objective is not to learn a classifier which is able to discriminate positive from negative examples, but to learn a probability distribution over the data. A good probabilistic model gives a correct estimation of the probability of each example. Such models are usually inferred from a set of positive examples only, which can be useful for many real world applications. However the presence of irrelevant or noisy data can dramatically affect the quality of the inferred distribution. The goal of this paper is to provide an approach allowing us to deal with such data in the framework of probabilistic learning. In fact, our main objective is not to highly reduce the size of the learning set, but rather to improve the probability estimations of stochastic models in order to increase their predictive ability.

To achieve this goal, we propose a probabilistic data reduction approach specifically adapted to treestructured data. The method is based on a partitioning of the whole set of subtrees, using on regular tree patterns (or contexts), and on the evaluation of the relevance of the probability of a subtree to be in a given partition. Subtrees with a too small probability are deleted. This task is carried out thanks to a confidence interval computed from the subtrees belonging to the partition. We decided to evaluate our approach in the context of learning stochastic tree automata. These models allow us to define a probability distribution on a set of trees using the representation of a probabilistic automata. Such automata define a probabilistic tree language and are learned using statistical information from a learning set constituted of trees. These automata are then very suited for learning a probability distribution over a set of trees.

The paper is organized as follows. Section 2 deals with some definitions and notations. In Section 3, we introduce our data reduction approach. Section 4 presents a theoretical analysis of the impact of noise. In Section 5, we describe our experimental results. Finally, we conclude this paper in Section 6.

Definitions and Notations

In this section, we formally define the notion of tree, and we illustrate our definitions using an example presented in Figure 1. In this example, that we will use as illustration all along this paper, we consider a database of hospital patients affected by a given disease. For each patient, we have two of the main characteristic symptoms of the disease, his blood group and the stage of the disease.

The definitions introduced in this section correspond to a classic framework, and are inspired by the thesis of Kilpeläinen [START_REF] Kilpeläinen | Tree Matching Problems with Applications to Structured Text Databases[END_REF].

R 1 = {(x, y) | (x, y) ∈ D 2 } R n+1 = {(x, y) | ∃z ∈ D such that (x, z) ∈ R and (z, y) ∈ R n , n > 0} R + = n>0 R n Definition 3.
A tree t is defined by a triplet (N t , A t , root(t)) where N t is a set of nodes, A t ⊆ N 2 t is a binary relation, and root(t) is a special node called the root of the tree t. For each pair (u, v) ∈ A t , (u, v) is called an edge of the tree and u is the parent of v, which is denoted by u = parent(v). A t must verify the following conditions:

• root(t) has no parent.

• Each node in t (except the root) has exactly one parent.

• From the root, we can reach any node of t in following a path defined by the edges of t, i.e. ∀v ∈ N t , v = root(t), (root(t), v) ∈ A + t . Let t be a tree and let u ∈ N t , we now formally define the notion of children and descendants of a node u.

descendants(u) = {v ∈ N t | (u, v) ∈ A + t } Definition 6.
The subtree of t with root u is the tree

(N t[u] , A t[u]
, u) such that:

• N t[u] = {u} ∪ descendants(u) • A t[u] = A t ∩ (N t[u] × N t[u] )
Trees, we are interested in, are constructed over a signature. This signature allows to label each node by a functional symbol, such that all the nodes labeled by the same symbol have exactly the same number of children. Finally, the symbols are typed and the children ordered.

Definition 7.

A signature Σ is a 4-tuple (τ, V, arity, σ) where:

• τ is a finite set whose elements are called sorts,

• V is a finite set whose elements are called function symbols, V called the alphabet,

• arity is a mapping function from V into IN , arity(f ) called the arity of the function symbol f ,

• σ is a mapping function from V into τ , σ(f ) called the sort of f . We denote by Σ T the set of trees defined relatively to a signature Σ. Definition 8. A labeled tree t over a signature Σ is a tree such that each node u ∈ N t is mapped with a symbol f ∈ V such that |children(u)| = arity(f )

We use the notation t = f (t 1 , . . . , t n ) to define a tree having the root labeled by the symbol f and having n subtrees t 1 , . . . , t n such that children(root(t)) = {root(t 1 ), . . . , root(t n )}. A total order is defined on the set of children of t such that t 1 is the first subtree and t n is the last one.

For example, the first of the four trees of Figure 1 represents a patient having symptoms ID1 and ID2, with A+ as blood group and a disease at a severe stage. The label of the root is patient, and the labels of the three children of the root are symptoms, blood and stage. We denote this tree by patient(symptoms(ID1, ID2), blood(A+), stage(severe)).

In the following, when there is no ambiguity, we will describe the node of a tree by its label.

Definition 9.

A position is a couple (f, p) (denoted by f.p) where f ∈ V and p ∈ IN such that 1 ≤ p ≤ arity(f ). A position defines the subtree corresponding to the child number p of the symbol f (the children are ordered from left to right). The special position p root defines the symbol at the root of a tree.

For example, in the first tree of Figure 1, the subtree symptoms(ID1, ID2) is at position patient.1 of the tree patient(symptoms(ID1, ID2), blood(A+), stage(severe)) and the subtree ID2 is at position symptoms.2 of the subtree symptoms(ID1, ID2).

Definition 10. Let T be a sample of trees. We denote by Sub(T ) the set of subtrees of T and M Sub(T ) the multi-set of subtrees of T .

For example, if we consider the subset composed of the first two trees of the sample T of Figure 1: Let us now consider the problem of noisy data. In our example, the subtree blood(Cu) of the second tree and the subtree stage(peter) of the fourth one, are clearly corrupted, probably due to a typing error, and should be removed. However, the other subtrees of these trees deserve to be kept because they bring relevant information. One of the interest of a data reduction approach is to reduce the dataset size by removing useless or noisy data without calling into question the probabilistic distribution of the learning set. Our idea is then to assess this distribution and remove data having a too weak probability density, that characterizes both useless and noisy data. This leads us to propose a definition of the relevance of a subtree. This definition is in relation with the one of relevant features introduced in [START_REF] John | Irrelevant Features and the Subset Selection Problem[END_REF]. Definition 11. Let D be a distribution on a set of subtrees S, a subtree t is relevant in S if and only if its probability estimation pD (t) is not significantly smaller than the mean of the probabilities of subtrees of S.

Sub(T ) = {ID1,
Roughly speaking, this definition expresses the idea that a relevant subtree must cover a significant part of the probability density of the learning set. Then, to assess this notion of significance, we propose, in the next section, to use the concept of confidence intervals, widely used in statistical inference theory.

Pruning Subtrees using Confidence Intervals

In this section, we introduce the probabilistic framework of our approach. First, we compute a probability distribution over a set of trees, based on "N-grams" models [START_REF] Ney | On Structuring Probabilistic Dependences in Stochastic Language Modelling[END_REF] and adapted to tree-structured data. Using this distribution, we draw a confidence interval around the mean of the probabilities of subtrees. The lower bound of this interval is then used as a critical threshold for testing the relevance of a subtree.

All this process requires to take into account, in the considered learning set, only comparable subtrees. Actually, while blood(A+) and blood(O+) are two subtrees characterizing the same "concept", it is obviously irrelevant to compare blood(A+) and stage(severe). In other words, it means that one must formally define a notion of concept for permitting the construction of efficient confidence intervals. We present this formalism at the end of this section, based on a partitioning method using regular tree patterns.

Tree-based Probability Distribution

Given a learning sample T of trees, we aim at constructing a probability distribution on the whole set T . To achieve this task, we compute a probability for each subtree in Sub(T ) according to an approach similar to the one of "N-grams" often used in natural language modeling [START_REF] Brown | Class-Based n-gram Models of Natural Language[END_REF]. This approach assumes that the probability of a given symbol in a string can be computed using the n -1 previous symbols. We use a similar principle, with n = 2, computing the probability of a symbol relatively to its parent. Note that a different adaptation of this approach in the context of trees has been proposed in [START_REF] Rico-Juan | Stochastic k-testable Tree Languages and Applications[END_REF]. For each symbol a of the learning set T , we assess its probability pc (a | f.i) to be the child number i of any symbol f . Formally, if # T f.i (a) is the number of nodes labeled by a at position f.i in the set T and if # T (f ) corresponds to the number of nodes labeled by f in T , we have:

∀a ∈ V , ∀f ∈ V , ∀1 ≤ i ≤ arity(f ), pc (a | f.i) = # T f.i (a) # T (f )
Moreover we compute for each symbol its probability to be the root of a tree.

∀a ∈ V , pr (a) = # T proot (a) |T |
where |T | is the cardinality of the set T .

Finally the probability of a tree t = f (t 1 , . . . , t n ) is computed as follows:

pa (f (t 1 , . . . , t n )) = pr (f ) × ppos (t 1 | f.1) × • • • × ppos (t n | f.n)
where ppos is recursively defined by:

ppos (g(u 1 , . . . , u m ) | f.i) = pc (g | f.i) × ppos (u 1 | g.1) × • • • × ppos (u m | g.m)
For example, the set of trees of Figure 1 and the probability of the tree t = patient(symptoms(ID1, ID2), blood(A+), stage(severe)) is computed as follows:

pa (t) = pr (patient) × pc (symptoms | patient.1) × pc (blood | patient.2) × pc (stage | patient.3) × pc (ID1 | symptoms.1) × pc (ID2 | symptoms.2) × pc (A+ | blood.1) × pc (severe | stage.1) = 1 × 1 × 1 × 1 × 1 2 × 1 2 × 1 4 × 1 2 = 1 32
If t ′ is a subtree of a tree, assuming that t ′ is different than the whole tree, then we compute its probability taking into account its position relatively to its parent. For example, the probability of the subtree blood(A+) of the previous tree t is computed as follows:

ppos (blood(A+) | patient.2) = pc (blood | patient.2) × pc (A+ | blood.1) = 4 4 × 1 4 = 1 4
The probability distribution allows us to compute the lower bound of a confidence interval which helps us to detect irrelevant instances. However, when a confidence interval is estimated with a small number of examples, the lower bound can be negative. It is then impossible to detect very rare instances. To overcome this drawback, we propose to slightly modify the probability distribution in order to automatically delete very rare instances, i.e. that occur only once. For this purpose, to compute the probability of a subtree t, we adapt the probability distribution such that the instance of t is not taken into account. Formally, if pc (a|f.i) is involved in the computation of the probability estimation of t, then pc (a|f.i) is replaced by:

   0 if # T (f ) = # t (f ) # T f.i (a)-# t f.i (a) # T (f )-# t (f ) otherwise where # t f.i (a)
is the number of symbols a at position f.i in t, and # t (f ) the number of labels f in t. For example, the probability of the subtree blood(A+) is actually evaluated as follows:

ppos (blood(A+) | patient.2) = pc (blood | patient.2) × pc (A+ | blood.1) = 3 3 × 0 3 = 0
This modification allows us to associate a null probability to instances occurring once in the dataset. In our approach, all subtrees with a null probability are automatically removed.

Probabilistic Pruning Rule

In the previous section, we have proposed a way to construct a probability distribution from a set of trees T . We show here how we can use this distribution to a priori (i.e. before any learning process) prune subtrees considered statistically irrelevant, thanks to a statistical test. Let us consider a subset S of M Sub(T ). We compute a confidence interval, according to a risk α (called the level of significance of the test, or Type I error). We look for an interval [pmin; 1] such that the theoretical probability p a (t) of a subtree satisfies the following constraint:

p(p a (t) ≥ pmin) = 1 -α.
According to the Central Limit Theorem, the mean pa (t S ) of probabilities of the elements of S follows a normal distribution with an expected value µ and a standard deviation σ √

|S|

. Then the confidence interval around µ is defined as follows:

µ ∈ pa (t S ) ± σ |S| × u α
where σ is the estimated standard deviation and u α the (1α)-percentile of the normal distribution. Let pmin be the lower bound of this interval, such that:

pmin = pa (t S ) - σ |S| × u α
When the size of S is not sufficient (|S| < 30) for approximating the distribution of the random variable p a (t) by the normal distribution, p a (t) follows a Student distribution with |S| -1 degrees of freedom.

Once this lower bound is computed, our decision rule consists in deleting all subtrees of S that have a probability smaller than pmin. Then, we can refine Definition 11 on the relevance of a subtree taking into account this notion of confidence interval.

Definition 12.

Let D be a distribution on a set of subtrees S, and let α be a risk.

A subtree t is (1 -α)- relevant in S if and only if pa (t) ≥ pa (t S ) -σ √ |S| × u α .
We claim that such pruning strategy is particularly suited for removing noisy subtrees. In fact, such data have by nature an individual weak probability. Actually, in the opposite case, they would constitute a part of the concept to learn, and then would deserve to be kept in the learning set.

Partitioning Subtrees with Regular Tree Patterns

So far, we assumed that we have a learning sample T of trees, from which we are now able to detect irrelevant data. However, we think that the previous pruning strategy is relevant if the probability of a subtree is computed relatively to those characterizing the same concept. Roughly speaking, we must compare only what is comparable. In the definitions of Section 2, we considered that children of a node are ordered and we proposed a definition for the position of a subtree. Then, we are able to define subtrees representing the same concept as subtrees that appear exactly at the same position. Indeed, because they appear at the same position, they represent instances of the same concept. In the example of hospital patients (see Figure 1), subtrees at position patient.3 are instances of the concept representing the stage of the disease.

In fact, we can go farther in our definition of a concept. With the position of a subtree, we can also take into account some information given by subtrees appearing at other positions. In our example on patients, subtrees at position patient.2 define the concept blood group of a person. We can refine this context by taking into account subtrees appearing at positions patient.1 and patient.3. For example, we can consider blood groups of patients having the symptoms ID1 and ID2 and being at a severe stage of the disease. Subtrees corresponding to this concept of blood group are those appearing at position patient.2 with the subtree symptoms(ID1, ID2) at position patient.1 and the subtree stage(severe) at position patient.3. In this case, a concept is defined by a context taking into account the maximum of local information available.

To assess this notion of context, we propose a method of partitioning using regular tree patterns, i.e. tree patterns with only one variable. This approach ensures that two subtrees that appear in the same context (i.e. subtrees with the same ancestors and siblings) will be in the same partition. This kind of tree patterns corresponds exactly to our notion of context. In fact, we can easily construct such tree patterns by replacing only one subtree in a tree by a variable. If we iterate this process in order to consider all the nodes of T , we can construct all definable contexts in this set. Before presenting our partitioning method, we give a formal definition of regular tree patterns. Definition 13. A regular tree pattern is a tree t defined on a signature (τ, V ∪ {X}, arity, σ) where X is a variable and t has exactly one leaf labeled by X. Let t be a regular tree pattern and t ′ be a classic tree. We denote by t. # t ′ the substitution of the variable X of t by the tree t ′ . Definition 14. The set of all the regular tree patterns, that are tree patterns with exactly one variable, definable on a signature Σ = (τ, V ∪ {X}, arity, σ) by Σ X T .

For example, Figure 2 shows the result of the concatenation of the subtree symptoms(ID1, ID2) with the tree pattern patient(X, blood(A+), stage(severe)). To construct a partition of the multi-set of subtrees, our approach consists in extracting all the regular tree patterns definable from T . As seen before, the number of such tree patterns corresponds exactly to the number of nodes of T . Then formally, the set of all regular tree patterns can be defined by {t | ∃t ′ ∈ M Sub(T ) and t. # t ′ ∈ T }. Figure 3 shows all the tree patterns definable from the tree patient(symptoms(ID1, ID2), blood(A+), stage(severe)). Each pattern t allows us to define a class π t of the partition of the multi-set of subtrees. The subtrees which can be concatenated to t to obtain a tree of the learning sample belong to this partition:

π t = {t ′ ∈ M Sub(T ) | t. # t ′ ∈ T }.
We construct all partitions definable from a set of trees with a quadratic time complexity in the number of nodes in T . This time complexity gives an upper bound of the complexity of our approach. Figure 4 shows examples of the sample t selected by the tree pattern patient(symptoms(ID1, ID2), X, stage(severe)). Note that the subtree blood(O+) of the third tree is not selected because the subtrees at position patient.3 in this tree and in the regular tree pattern are different. To end this section, we synthesize the main steps of our pruning method in Algorithm 1.

Data

Theoretical Results in the Presence of Noise

As we said before, an important aspect of our work is its capacity to deal with noisy data. In this section, we propose to draw a theoretical study of the impact of noise on our method. To begin with, we define the protocol of the data corruption process we consider. Then, under reasonable assumptions about the nature of noise, we study the impact of noisy data on the probability distribution we have to build. We show that it has a direct influence on the number of deleted subtrees. We finish this study with the examination of the impact of noise on subtrees. From a global point of view, this study has the objective to point out the kind of data that can be efficiently preprocessed in the presence of noise.

We assume that the noise is uniformly distributed on the leaves of the learning set T . We think that such assumption is reasonable in the context of tree-structured data because, in most of applications, the precise information concerning the concept is often stored in leaves (for example A+, severe), while the other nodes characterize more global information. Let γ be the level of noise, which corresponds to the percentage of leaves that have been corrupted. We assume that a noisy leaf is replaced by a different leaf, randomly chosen from the other leaves of the dataset. In the following, we denote by L T the whole set of leaves in T (without repetitions).

According to our experimental set up, only probabilities of symbols located at the leaves, that we will call "constant", are affected by the noise. Then, we will only consider probabilities p(a|f.n) where a is such a constant and f a symbol such that 1 ≤ n ≤ arity(f ). In all the section, we assume that for any position f.n, a∈V , arity(a)=0 p(a|f.n) = 1.

In the presence of an uniformly distributed noise γ, we can easily determine the probability of any constant a given any position f.n:

P γ (a|f.n) = (1 -γ) * p(a|f.n) + (1 -p(a|f.n)) * γ |L T |-1 = (1 -|L T | * p(a|f.n)) * γ |L T |-1 + p(a|f.n) P γ (a | f.n) is composed of two terms.
The first one represents the weighted proportion of leaves a that are not affected by the noise, while the second corresponds to the weighted proportion of corrupted data that were originally different from a before their modification into a (due to the noise). An important point to remark is that P γ (a | f.n) evolutes linearly in function of γ.

Let us now study the behavior of P γ (a|f.n).

P γ (a|f.n) = (1 -|L T | * p(a|f.n)) * γ |L T | -1 + p(a|f.n) then ∂P γ (a|f.n) ∂γ = (1 -|L T | * p(a|f.n)) * 1 |L T | -1
Then it is easy to see that P γ (a|f.n) increases with the level of noise when p(a|f.n) < 1 |L T | , and decreases when p(a|f.n) > 1

|L T | . ⊓ ⊔
This result shows that when the noise level increases, the probability of the constant a (whatever its nature) tends to the same value 1 |L T | . The number of leaves plays an important role in the estimation of the distribution. We have experimentally observed that, for a given level of noise, the increase of the number of leaves tends to highly disturb the original distribution, that may have a direct impact on our pruning method. To confirm this phenomenon, we theoretically study, here, the deviation between p(a|f.n) and P γ (a|f.n).

Theorem 4.2. The deviation

D L T (a | f.n) = p(a|f.n) -P γ (a|f.n) is an increasing function in |L T |. Proof: D L T (a | f.n) = p(a|f.n) -P γ (a|f.n) = p(a|f.n) -(1 -γ) * p(a|f.n) -(1 -p(a|f.n)) * γ |L T |-1 = γ * p(a|f.n) -(1 -p(a|f.n)) * γ |L T |-1 Then ∂D L T (a | f.n) ∂L T = - -(1 -p(a|f.n)) * γ (|L T | -1) 2 = (1 -p(a|f.n)) * γ (|L T | -1) 2 ≥ 0 which is positive. ⊓ ⊔
The deviation between the two probabilities increases with |L T |, and implies that the probability distribution is highly modified, whatever the level of noise γ. This result can be easily interpreted. Indeed, when the number of leaves is high, those originally labeled by a are replaced by others, and at the same time, there is only a small proportion of leaves different from a modified into a. Then, given a level of noise, the probability p(a|f.n) is modified with the increase of |L T |.

Since the number of occurrences of a given tree is used for drawing the probability distribution, we aim here at computing the probability to modify this number according to the level of noise γ. Let N t be the set of trees having the same number of leaves as t and differing from it in at least one leaf. In other words, for each tree t ′ ∈ N t , we can define a bijection between the leaves of t ′ and the ones of t such that we can obtain t from t ′ . Given a tree t ′ ∈ N t , let dif f (t, t ′ ) be the number of different leaves between t and t ′ . We denote by N L t the number of leaves of a tree t, and by N O t the number of occurrences of a tree t in the set T . Theorem 4.3. The probability that the number of occurrences of a tree t is modified by γ is

(1 -(1 -γ)) N Lt * N O t |T | + t ′ ∈Nt γ * 1 |L T | -1 dif f (t ′ ,t) * (1 -γ) (N Lt-dif f (t ′ ,t)) * N O t ′ |T |

Proof:

Noise may corrupt the number of occurrences of a tree t via two ways. On the one hand, it can affect the leaves of t, on the other hand it can corrupt a tree of N t which becomes an instance of t.

The probability to corrupt at least one leaf of t is equal to the complementary of the probability not to add noise to any leaf of t, that is 1 -(1γ) N Lt . This quantity requires then to be multiplied by the probability to have the tree t in the set T : N Ot |T | . Moreover, for any tree t ′ ∈ N t , if dif f (t, t ′ ) = n, then we have to add noise to n leaves of t ′ such that each of them becomes exactly equal to the one of t, and we do not corrupt the other leaves. The probability that t ′ becomes equal to t is (γ

* 1 |L T |-1 ) dif f (t,t ′ ) * (1 -γ) (N Lt-dif f (t,t ′ ))
. We must multiply this probability by the one of having t ′ :

N O t ′
|T | . We repeat this for each tree in N t and holds

t ′ ∈Nt (γ * 1 |L T |-1 ) dif f (t,t ′ ) * (1 -γ) (N Lt-dif f (t,t ′ )) * N O t ′ |T |
. Then, at the end of the corruption, the probability that the number of occurrences of a tree t is modified by γ is

(1 -(1 -γ)) N Lt * N O t |T | + t ′ ∈Nt γ * 1 |L T | -1 dif f (t,t ′ ) * (1 -γ) (N Lt-dif f (t,t ′ )) * N O t ′ |T | ⊓ ⊔

Evaluation in the Context of Learning Stochastic Tree Automata

We present, in this section, experimental results which justify the interest of our method to preprocess the learning sample in presence of noisy data. Since we work on trees, we propose to evaluate our data reduction approach in the framework of learning stochastic tree automata from a learning set [START_REF] Carrasco | Stochastic Inference of Regular Tree Languages[END_REF][START_REF] Garcia | Inference of recognizable tree sets[END_REF][START_REF] Sakakibara | Efficient Learning of Context-Free Grammars from Positive Structural Examples[END_REF].

In such a context, we have a sample of trees, supposed to be generated from a probability distribution.

The objective is to learn the probabilistic model which has generated the data. Thus, the main goal of such an approach is not to learn a classifier which can discriminate negative from positive examples, but rather to learn a statistical distribution over the learning sample. We propose to compare the automata inferred from noisy data and those induced after our pruning process. To carry out this task, we can achieve two series of experiments. The first one deals with learning problems where the target automaton is a priori known. In this case, we can use a measure of distance between the inferred model and the target automaton. However, since the target model is often unknown, in a second series of experiments, we also evaluate our approach using a perplexity measure. This criterion assesses the relevance of the model on a test sample.

In this section, we first specify automata we work on, called many-sorted stochastic tree automata, defined relatively to a signature. Then, we present the algorithm we use for inferring stochastic tree automata (STA). Finally, after having detailed the main criteria allowing us to assess the efficiency of our pruning method, we carry out a large experimental study showing the interest of our approach.

Stochastic Many-Sorted Tree Automata

Deterministic Tree Automata (DTA) generalize Deterministic Finite-state Automata (DFA). In contrast to DFA, that parse strings from left to right, DTA work bottom-up. A state of the automaton is associated to each node of the tree. The label of each node is defined by a transition function, and the state of the root determines if the tree belongs to the language or not. To illustrate this informal description, we give a graphical representation of such automata in Figure 5. In this example, states are represented by a circle, final states by a double circle and transitions by a triangle containing the symbol involved in the transition. Let us define formally the concept of stochastic tree automata able to recognize trees defined on a signature Σ (already presented in Section 2). Definition 15. A SMDTA is a 5-tuple A = (Σ, Q, r, δ, p) where -Σ is a signature (τ, V, arity, σ),

-Q = ∪ s∈τ Q s is a finite set of states, each state having a sort in S, -r : Q -→ [0, 1]
is the probability for a state to be a final state,

-δ : V × Q * -→ Q is the transition function, -p : V × Q * -→ [0, 1] is the probability of a transition.
The transition function δ is recursively extended to a function δ ′ : V × (Σ T ) * -→ Q as follows:

δ ′ (f ) = δ(f ) if arity(f ) = 0 δ ′ (f (t 1 , . . . , t n )) = δ(f, δ ′ (t 1 ), . . . , δ ′ (t n )) otherwise
Note that we consider deterministic automata with the following properties. The transition rules of δ are valid, that is for each rule (f, q 1 , . . . , q n ) -→ q, arity(f ) = n and σ(f ) = σ(q). Probabilities are normalized, so that probabilities of transitions leading to the same state sum to one.

The probability of a tree t parsed by a tree automaton A is computed as follows:

p(t | A) = r(δ ′ (t)) × π(t)
where π(t) is recursively given by:

π(f (t 1 , . . . , t n )) = p(f, δ ′ (t 1 ), . . . , δ ′ (t n )) × π(t 1 ) × • • • × π(t n )
π(f ) stops when f is a constant symbol, that is when arity(f ) = 0. We say that an SMDTA A accepts a tree t if and only if p(t | A) > 0. The language recognized by an automaton is the set of all trees accepted by the automaton. For example, let us consider the automaton A in Figure 5 which is defined with the following transitions and probabilities:

1.0 : ID1 -→ q 1 0.6 : A+ -→ q 4 1.0 : ID2 -→ q 2 0.4 : O+ -→ q 4 1.0 : symptoms(q 1 , q 2 ) -→ q 3 1.0 : blood(q 4 ) -→ q 5 0.2 : medium -→ q 6 0.8 : severe -→ q 6 1.0 : stage(q 6 ) -→ q7

1.0 : patient(q 3 , q 5 , q 7 ) -→ q 8 r(q 8 ) = 1.0

This automaton recognizes the first tree of the base on patients of Figure 1: t = patient(symptoms(ID1, ID2), blood(A+), stage(severe))) with the probability p(t | A) = 0.48.

p(t | A) = r(δ ′ (t)) × π(t)
= r(q 8 ) × p(patients, δ ′ (symptoms(ID1, ID2)), δ ′ (blood(A+)), δ ′ (stage(severe))) × π(symptoms(ID1, ID2)) × π(blood(A+)) × π(stage(severe)) = 1.0 × p(patients, q 3 , q 5 , q 7 ) × p(symptoms, δ

′ (ID1), δ ′ (ID2)) × π(ID1) × π(ID2) × p(blood, δ ′ (A+)) × π(A+) × p(stage, δ ′ (severe)) × π(severe) = 1.0 × 1.0 × p(patients, q 3 , q 5 , q 7 ) × p(symptoms, q 1 , q 2 ) × p(ID1) × p(ID2) × p(blood, q 4 ) × p(A+) × p(stage, q 6 ) × p(severe) = 1.0 × 1.0 × 1.0 × 1.0 × 1.0 × 1.0 × 0.6 × 1.0 × 0.8 = 0.48
An important feature of a stochastic tree automaton is its consistency since it allows to define a statistical distribution over Σ T , that is:

t∈Σ T p(t | A) = 1
In our inference procedure, probabilities of the SMDTA are computed from random samples and thus consistency is always preserved [START_REF] Chaudhuri | Approximating Grammar Probabilities: Solution of a Conjecture[END_REF][START_REF] Sakakibara | Efficient Learning of Context-Free Grammars from Positive Structural Examples[END_REF].

Note that these stochastic tree automata are able to recognize ordered trees which are defined on a ranked alphabet (that is where the arity of the nodes are fixed). As far as we know, there are no attempts for learning tree automata with unordered trees (which seems to be a difficult task), only data mining approaches [START_REF] Nijssen | Efficient Discovery of Frequent Unordered Trees[END_REF] or machine learning of tree pattern languages [START_REF] Amoth | On Exact Learning of Unordered Tree Patterns[END_REF] have tried to investigate this field. However, we can notice that [START_REF] Kosala | Information Extraction from web documents based on local unranked tree automaton inference[END_REF] tries to learn unranked tree automata with ordered trees but in a non probabilistic framework. In this paper, we rather focus on learning stochastic tree automata working with ordered trees defined over a ranked alphabet.

Induction of Stochastic Tree Automata

In stochastic grammatical inference, Carrasco et al. [START_REF] Carrasco | Stochastic Inference of Regular Tree Languages[END_REF] proposed an efficient algorithm to learn stochastic tree automata. Abe et al. [START_REF] Abe | Predicting protein secondary structure using stochastic tree grammars[END_REF] dealt with learning stochastic tree grammars to predict protein secondary structure. Rico et al. [START_REF] Rico-Juan | Probabilistic k-Testable Tree-Languages[END_REF] presented a generalization of k-gram models for stochastic tree languages.

Our inference procedure is an extension of [START_REF] Carrasco | Stochastic Inference of Regular Tree Languages[END_REF], that takes sorts into account [START_REF] Habrard | Generalized stochastic tree automata for multi-relational data mining, 6th International Colloquium on Grammatical Inference[END_REF]. Algorithm 2 gives an idea of the main steps of the inference. For formally details, the interested reader may refer to [START_REF] Carrasco | Stochastic Inference of Regular Tree Languages[END_REF][START_REF] Habrard | Generalized stochastic tree automata for multi-relational data mining, 6th International Colloquium on Grammatical Inference[END_REF]. The input of the algorithm is a training set T of trees and the output is a SMDTA which respects the distribution over T .

The algorithm computes the transition function considering all subtrees of the training set. A total order is defined on subtrees comparing their depth. Each subtree is mapped to a state, taking into account the fact that if two subtrees are similar in the training set, then they have the same state. We denote by [t] the state mapped to the subtree t. To compute the similarity of two subtrees (comp function), the algorithm uses a statistical test [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] depending on a parameter 0 ≤ β ≤ 1, which corresponds to the Data: T : a training set of trees, Σ = (τ, V, arity, σ): a signature

Result: A = (Σ, Q, δ, p, r): a SMDTA begin W ← Sub(T ) Q ← ∅ while W = ∅ do x ← g(t 1 , . . . , t n ) = min W W ← W \{x} if ∃y ∈ Q | σ(x) = σ(y) and comp(x, y, β) then δ(g, [t 1 ], . . . , [t n ]) = y else Q ← Q ∪ {x} δ(g, [t 1 ], . . . , [t n ]) = x end end compute probabilities(T, δ, p, r) end Algorithm 2: Inference of a SMDTA.
Type I error of a similarity test of two subtrees. Intuitively β represents a tolerance parameter for the merging of two subtrees into a same state. The comp function is described in Algorithm 3. The notation C T (t) corresponds to the number of occurrences of a subtree t in the learning set T . The similarity of two subtrees is assessed by using the regular tree patterns of Σ X T , the test evaluates if two subtrees are statistically equivalent in a same context. The probabilities are then computed counting subtree occurrences in the training set, with respect to the normalization of SMDTA.

Data: x a subtree of Sub(T ) y a subtree of Sub(T )

β a real ∈ [0; 1] begin foreach ∀z ∈ Σ X T such that z. # x ∈ T or z. # y ∈ T do if C T (z. # x) C T (x) - C T (z. # y) C T (y) > 1 2 * ln 2 β * 1 √ C T (x) + 1 √ C T (y)
then return false return true end Algorithm 3: The comp function The algorithm has the following properties: it is polynomial in the number of different subtrees of the training set, and it converges to the limit under the Gold paradigm [START_REF] Gold | Language Identification in the limit[END_REF]. If the set T of terms has been generated with a target stochastic tree automaton A target and if A(T ) is the automaton learned from T , then we have the following property:

lim |T |-→∞ t∈Σ T
p(t|A target )p(t|A(T )) = 0

Evaluation of Stochastic Tree Automata

The evaluation of non-probabilistic models is often based on the correct classification rate. This is not the case for our approach aiming at learning a probability distribution from a learning sample. Probabilistic models are rather assessed on their ability to correctly predict the probability of the examples of a test sample. When the target model is known, the correctness is evaluated by the distance between the statistical distribution of the learned model and the target model [START_REF] Calera-Rubio | Computing the relative entropy between regular tree languages[END_REF]. Nevertheless, when we work on real applications, the target model is often unknown, and the quality of the learned model can be evaluated with a measure of perplexity.

Probabilistic Distance

Lyngsø et al. [START_REF] Lyngsø | Metrics and Similarity Measures for Hidden Markov Models[END_REF] defined distances between two hidden Markov models introducing the co-emission probability, as the probability that two independent models generate the same string. Carrasco et al. [START_REF] Carrasco | A similarity between probabilistic tree languages: application to XML document families, Pattern Recognition[END_REF] presents an adaptation of the co-emission to stochastic tree automata. The probability that two probabilistic models, A and A ′ , generate the same tree is defined by

C(A, A ′ ) = t∈Σ T p A (t) × p A ′ (t)
Where P A (t) is the probability of t given the model A. The co-emission probability allows us to define a distance D a which can be interpreted as the measure of the angle between the vectors representing automata in a space whose base is the set of trees of Σ T . Definition 16. The distance D a between two automata A1 and A2 is defined by:

D a (A1, A2) = arccos C(A1, A2) C(A1, A1) * C(A2, A2)
In the context of stochastic automata, Carrasco et al. [START_REF] Carrasco | A similarity between probabilistic tree languages: application to XML document families, Pattern Recognition[END_REF] proposed a recursive definition of the coemission in order to compute a distance between two stochastic automata. Then, the co-emission can be written such that

C(A, A ′ ) = q∈Q q ′ ∈Q r A (q) × r A ′ (q ′ ) × ν q,q ′
where ν q,q ′ = f ∈Σ s.t. f (q i1 ,...,q im )→q, f (q j1 ,...,q jm )→q ′ p(f (q i1 , . . . , q im ) → q) × p ′ (f (q i1 , . . . , q im ) → q) × ν qi1,qj1 × . . . × ν qim,qjm

The recursive definition of ν q,q ′ stops for constant symbols arriving on q or q ′ .

Perplexity

In the case of stochastic tree automata the quality of a model A on a test set S test can be evaluated by the following measure:

LL = 1 || S test || t∈Stest log p(t | A)
where || S test || is the number of nodes of every tree of S test .

A perfect model can predict each element of the test set with a probability equal to one, and so LL = 0. In a general way, we consider the perplexity of the test set which is defined by P P = 2 LL . A minimal perplexity (P P = 1) is reached when the model can predict each element of the test sample. Therefore we consider that a model is more predictive than another if its perplexity is lower.

A problem occurs when a tree of the test sample cannot be recognized by the automaton. Actually the probability of this example is 0 and the perplexity cannot be computed. To avoid this problem, a classical method consists in smoothing the distribution of the learned model using an interpolation approach [START_REF] Ney | On Structuring Probabilistic Dependences in Stochastic Language Modelling[END_REF] with a unigram model A 0 recognizing all trees of Σ T . This automaton has only one state, and for each function symbol of the signature, there is a transition starting from and ending in this state. Finally, a transition is added for any unknown symbol. The probabilities of transition rules are computed from the training set, keeping a small ratio for the transition involving unknown symbols. In the smoothed model, a tree t has the probability:

P (t) = λ.p(t|A) + (1 -λ).p(t|A 0 )
where 0 ≤ λ ≤ 1.

Experimentations

In this section, we present a set of experiments showing the interest of our method in the context of learning in presence of noisy data. We study the ability of our method to remove irrelevant or noisy subtrees to learn stochastic tree automata from a set of trees.

To verify this behavior, we carried out two series of experiments. First, we consider datasets where the target automaton is known and we evaluate the quality of the learned model by computing the D a distance. For this experiment, we used five artificial datasets.

• The dataset Stacks is produced by an automaton representing stacks of objects (squares and triangles) [START_REF] Bernard | GIFT: Grammatical Inference for Terms, Late Breaking paper at the 9th International Conference on Inductive Logic Programming[END_REF]. Each object is described by its shape and its color. This dataset has an alphabet constituted of 8 different leaves and allows to generate trees with a comb pattern representing the size of the stack. A sample of 5000 examples is generated for this dataset.

• The dataset Bool is generated by an automaton modeling boolean expressions. The alphabet includes only two leaves (true and false) and the generated trees define boolean expressions with operators and, or and not. We use a sample of 5000 trees for this dataset.

• The dataset Cond is defined an automaton representing conditional statements of a programming language [START_REF] Carrasco | Stochastic Inference of Regular Tree Languages[END_REF]. This dataset has an alphabet with 13 leaves and allows to generate wide and depth trees. We infer automata from a sample of 3000 trees.

• The datasets Art1 and Art2, are generated by automata represented in Figure 6, and define simple languages with different leaves. In these datasets, the location of the leaves has an important effect on the language. In this case, each dataset is composed of 5000 trees. The other experiments concern samples for which we do not know the target model. Then we measure the quality of the learned models by the perplexity measure. In this context, we re-use the five previous samples and we also evaluate our approach on 3 real datasets.

• The database Loan of the UCI Irvine [START_REF] Blake | University of California Irvine Repository of machine learning databases[END_REF]. This dataset corresponds to structured data in 1st order logic and is converted into trees according to the principle presented in [START_REF] Bernard | GIFT: Grammatical Inference for Terms, Late Breaking paper at the 9th International Conference on Inductive Logic Programming[END_REF]. This sample has 1000 examples composed of 143 different leaves.

• The database Tacrine comes from a dataset on the toxicity of the tacrine molecule presented in [START_REF] King | Relating chemical activity to structure: An examination of ILP successes[END_REF]. This dataset is also structured in 1st order logic and is also converted into trees with the principle proposed in [START_REF] Bernard | GIFT: Grammatical Inference for Terms, Late Breaking paper at the 9th International Conference on Inductive Logic Programming[END_REF]. This dataset has 1000 examples with 42 different leaves, but has larger trees than the previous one.

• We also use a sample proposed for the PKDD'02 discovery challenge1 (dataset on hepatitis); the transformation of data into trees is described in [START_REF] Habrard | Generalized stochastic tree automata for multi-relational data mining, 6th International Colloquium on Grammatical Inference[END_REF]. This dataset has 4000 examples with 253 leaves.

Our experimental setup consists in adding noise in each dataset, as previously described in Section 4, with a level γ from 0 to 25%. For experiments with an unknown target, we use a 5 fold cross-validation, where only the learning sample is noisy. Then we preprocess each corrupted sample with our approach using a Type I error α between 0.25 and 0.01. For each level of noise, we keep the α value which minimizes the quality measure. In order to show the efficiency of our pruning technique, we compare it with a Monte-Carlo sampling which randomly removes α% of the subtrees.

In our experiments, we study two variants of our pruning method. In the first one (called M 1 ), the removed subtree is replaced by a special symbol that does not appear in the dataset. This way to proceed looks like to the one used in classic data reduction techniques. The other one (called M 2 ) consists in replacing a deleted subtree by the most probable one of the partition, in order not to lose a part of the information. In the Monte-Carlo approach, this subtree is chosen randomly among the other subtrees.

We use two statistical measures to evaluate the results: the mean and the standard deviation of the quality criterion (distance or perplexity) for the different levels of noise.

The results are presented in Tables 1, 2 and 3. In each of them, we indicate the pruning rate according to the number of nodes removed in column Red. The global size (in the total number of nodes) of the datasets is indicated by IS. The results obtained without a preprocessing are stored in a column with a suffix N (the prefix corresponds to the mean for the criteria D a and P erp), those obtained by our approach with CI. The column M C corresponds to the Monte-Carlo sampling method previously mentioned. Finally, the column Sig indicates the significance of the results between N and CI using a Student paired t-test over the means with a critical risk of 5%. The column Sig2 indicates the significance of the results between CI and M C using the same comparison test.

Experimentations Knowing the Target Automaton

Before detailing the behavior of our pruning method, we present in Figure 7, the evolution of the mean of variances, before the preprocessing, for each dataset. The interest of this experiment is to empirically show the effect of the Theorem 4.2. Actually, the database Bool, which presents a steady variance, is the one having the smallest alphabet size. It confirms that the probabilistic distribution has not been changed a lot in the presence of noise, that has a direct impact on the pruning method. On the other hand, the databases Stacks and Cond, which have a higher alphabet size, present a more disturbed variance. Table 1 synthesizes results for the variant M 1 which replaces, as we said before, the deleted subtree by a special symbol. The results for the variant M 2 , which replaces the deleted subtree by the most probable one, are presented in Table 2. We give the average distance D a observed between the target automaton and the inferred automaton ± the standard deviation. The first point to note is the fact that our approach is useful for inferring better models in presence of noise, than an approach without preprocessing. Actually, this behavior is true for M 1 and M 2 , but the latter seems to have better results. We can easily explain this behavior by the fact that our learning algorithm (here a stochastic automata learning algorithm) is based on the statistical information contained in the dataset. Then, it requires a lot of examples to refine the estimations. This remark is very important because it expresses a particularity of the data reduction techniques that can be used for improving stochastic automata learning algorithms. In the context of probability distribution estimation, our experiments show that a radical deletion is not the optimal way to proceed, and that the replacement by a relevant tree (the most probable one) is more performing. This phenomenon is not surprising, and this kind of approach has already shown its efficiency in Data Mining for dealing with missing attributes. Actually, in the specific field of grammatical inference, a minimal number of examples is needed in order to infer the correct structure of the automaton [START_REF] Dupont | What Is the Search Space of the Regular Inference?[END_REF]. Consequently, the suppression of the structure of some examples can affect the quality of the learned automaton and then the quality of the probability distribution inferred.

Base

We can finally notice that the significance tests between N and CI are all in favor of our approach that confirms its interest for preprocessing noisy data. Moreover, those between CI and M C are in favor of our approach, except for the base Art1 with the method M 2 . Since Tables 1 and2 are synthetic, we also present the behavior of our method for the specific base Bool in Figure 8. We can make the following remarks. For both of the alternative variants M 1 and M 2 , CI allows to infer automata that are always significantly better than the ones learned from noisy data without preprocessing. Moreover, CI is always better than the Monte-Carlo approach that justifies the claim that we are able to detect and remove noisy subtrees.

The base Bool is an example of a correct behavior of our approach. However this is not always so significant. For example, let consider the behavior of our approach on the base Art1, represented in Figure 9. Our two alternative procedures give good results until a level of noise of 7.5%. Beyond this point, M C has a behavior similar and sometimes better, which shows that our approach has some difficulties to deal with high levels of noise.

An explanation of this phenomenon is that the presence of noise tends to smooth the repartition of the data. Actually, we noticed that when the level of noise increases, the average number of subtrees in a partition tends to decrease. In fact, there are more partitions and less examples in each partition. For example, in the case of the Art1 database, there is an average of 5.37 subtrees in a partition with 1% of noise and only 2.36 subtrees when the noise level is at 10%. In this context, when the noise level is increasing, the estimations of the bounds of the confidence interval are sharpness, resulting in larger intervals. Thus, it is more difficult to detect and remove irrelevant instances. On the other hand, M C always removes a given proportion of trees, whatever the level of noise is. Then, when this level is high, the probability that M C removes a corrupted subtree increases and allows this approach to have a better behavior.

Experimentations without Knowing the Target Automaton

In this context, we divide the sample of trees in two sets: a training set and a test set. Since we want to evaluate our approach in the context of noise, we only add noise to the training set. From this one, we infer two automata: the first one is learned without preprocessing, the second one is inferred after the pruning process. The noise-free test set is then parsed by the two automata resulting in the computation of two perplexity measures. Note that all the experiments are achieved using a 5 fold cross-validation. Since the variant M 2 consisting in replacing a noisy subtree by the most probable has already shown its efficiency with the D a criterion, we only test this approach for the second series of experiments. The results are presented in Table 3. From a general point of view, these results confirm the behavior already seen in the previous experiments. Our pruning method CI permits to efficiently preprocess all the databases except the base Bool. Moreover, an interesting remark is that our approach has a smaller standard deviation than the one computed from the unpreprocessed sets, that denotes a better robustness. One of the interest of this series of experiments is also to observe the behavior of CI on real datasets. The results are always in favor of our method, but the most interesting effect is certainly obtained for the base PKDD'02, with a high reduction rate and a large decrease of the perplexity. As for the previous criterion D a , let us study the behavior of CI on a single database (here the base Loan, see Figure 10). Whatever the level of noise, CI dramatically decreases the perplexity in comparison with the unpreprocessed dataset. Moreover, the level of the deviation between the curves N and CI is kept with the increase of the noise. In comparison with the Monte-Carlo sampling, CI provides better results until 10% of noise. Beyond this rate, it begins to have some difficulties to remain performing, which confirms the fact our approach is not very suited for dealing with high levels of noise. In order to compare the two measures we used for evaluating the performances, we summarize all our results, obtained with the variant M 2 , in Figure 11. Each dot represents a database. A dot under the bisecting line expresses the fact that our pruning approach CI is better than the one without pruning.

Base

Conclusion

In this paper we have presented an original approach allowing to deal with irrelevant and noisy subtrees in a set of trees. This approach is a data reduction technique that can be considered as a hybrid approach. It can actually delete either a whole irrelevant tree or only some of its subtrees. Our pruning method is based on the use of confidence intervals computed from a probability distribution on subtrees appearing in a same context. Our experiments have shown that our approach is efficient and robust resulting in the inference of automata closer to the target concept in the presence of noisy data.

Despite this interesting general behavior, we have experimentally noted that our pruning method has some difficulties to deal with datasets with a small alphabet like the one of boolean expressions or parity functions. Moreover, our approach is based on confidence intervals which depend on the size of the learning set. Then, its efficiency is only ensured with large databases, that is not a too strong hypothesis considering the size of the modern databases. Finally, our method depends on the partitioning technique for which we propose a first solution based on the notion of context. We think that this solution requires a relatively strong constraint on the trees. Indeed, when there is a too small number of elements in a partition, the computation of the confidence intervals is inaccurate and our approach becomes less efficient, especially for high levels of noise. We are working on other relaxing partitioning approaches which deserve further investigations. Finally, we think that an interesting improvement of our method would concern its adaptation to unordered trees, which are for example suited for dealing with XML data.

Figure 1 .Definition 2 .

 12 Figure 1. Set of trees T representing 4 patients.

Definition 4 .Definition 5 .

 45 The children of u are defined bychildren(u) = {v ∈ N t | (u, v) ∈ A t }The descendants of u by:

2 4 1 4 1 4 2 4 1 4

 21121 leads to the following conditional probabilities (only the non null probabilities are indicated): pc (ID1 | symptoms.1) = pc (A+ | blood.1) = pc (medium | stage.1) = pc (ID2 | symptoms.2) = pc (Cu | blood.1) = pc (peter | stage.1) = 1 4 pc (ID7 | symptoms.1) = 2 4 pc (O+ | blood.1) = 2 4 pc (stage | patient.3) = 4 4 pc (ID5 | symptoms.2) = 2 4 pc (severe | stage.1) = 2 4 pc (blood | patient.2) = 4 4 pc (symptoms | patient.1) = 4 4 pr (patient) = 4 4

Figure 2 .

 2 Figure 2. Regular tree pattern and concatenation.

Figure 3 .

 3 Figure 3. Tree patterns definable from patient(symptoms(ID1, ID2), blood(A+), stage(severe)).

Figure 4 .

 4 Figure 4. Construction of a partition.

Algorithm 1 :

 1 : T : a set of trees α: a real ∈ [0; 1] begin Construct the probability distribution over T T ← partitioning M Sub(T ) foreach S ∈ T do Compute an interval [pmin; 1] for probabilities of subtrees of S to the risk α foreach t ∈ S do Delete t if it is not (1α)-relevant or if pa (t) = 0 end end end Pruning subtrees using confidence intervals.

Theorem 4 . 1 .

 41 P γ (a|f.n) is an increasing function of γ if p(a|f.n) < 1 |L T | and a decreasing function of γ if p(a|f.n) > 1 |L T | Proof:

Figure 5 .

 5 Figure 5. An example of stochastic tree automaton.

Figure 6 .

 6 Figure 6. Databases Art1 and Art2.

Figure 7 .

 7 Figure 7. Mean of variances of probabilities for the 5 artificial datasets.

Figure 8 .

 8 Figure 8. Behavior on the Bool database.

Figure 9 .

 9 Figure 9. Behavior on the Art1 database.

Figure 10 .

 10 Figure 10. Behavior for Loan with perplexity and for the variant M 2 .

Figure 11 .

 11 Figure 11. Results of the experimentations obtained with the variant M 2 .

Table 1 .

 1 Distances D a to the target automaton with the variant M 1 .

		IS	Red	D a .N	D a .CI	D a .M C	Sig	Sig2
	Stacks	35724	3.5%	0.30±0.11	0.23±0.15	0.60±0.45	yes	yes
	Cond	71683	14%	0.60±0.22	0.44±0.12	1.00±0.18	yes	yes
	Bool	43185	76%	0.22±0.08	0.16±0.09	0.17±0.10	yes	yes
	Art1 Art2	33137 30113	8.6% 1.3%	1.26 ±0.28 0.19±0.15	0.51±0.20 0.16±0.15	0.56±0.21 0.18±0.15	yes yes	yes yes
	Average	42678	27%	0.51 ±0.16	0.30±0.14	0.35±0.22	yes	yes
	Base	IS	Red	D a .N	D a .CI	D a .M C	Sig	Sig2
	Stacks	35724	1.4%	0.30±0.11	0.11±0.10	0.13±0.08	yes	yes
	Cond	71683	6%	0.60±0.22	0.59±0.23	0.57±0.07	yes	yes
	Bool	43185	61%	0.22±0.08	0.10±0.04	0.17±0.09	yes	yes
	Art1 Art2	33137 30113	1.7% 1.1%	1.26 ±0.28 0.19±0.15	0.38±0.06 0.17±0.15	0.39±0.07 0.18±0.15	yes yes	no yes
	Average	42678	14%	0.51±0.11	0.27±0.12	0.29±0.09	yes	yes

Table 2 .

 2 Distances D a to the target automaton with the variant M 2 .

Table 3 .

 3 Perplexity results obtained with the variant M 2 .

		IS	Red	P erp.N	P erp.CI	P erp.M C	Sig	Sig2
	Stacks	35724	2%	1.93±0.15	1.83±0.07	1.86±0.08	yes	yes
	Cond	71683	3.9%	1.47±0.21	1.33±0.07	1.42±0.10	yes	yes
	Bool	43185	3.8%	3.41±0.16	3.56±0.09	3.95±0.21	yes	yes
	Art1	33137	2.5%	3.68±0.43	2.50±0.12	2.57±0.15	yes	yes
	Art2	30113	1.8%	1.33±0.12	1.30±0.10	1.32±0.11	yes	no
	Loan	14117	1%	9.02±2.63	5.10±1.30	5.75±0.49	yes	yes
	Tacrine	41130	2.6%	4.60±2.84	3.14±0.77	3.21±0.80	yes	yes
	PKDD'02	115173	20%	12.2±4.60	8.75±2.50	9.00±2.00	yes	no
	Average	47999	4.7%	4.71±1.39	3.44±0.63	3.64±0.49	yes	yes

http://lisp.vse.cz/challenge/ecmlpkdd2002/

Acknowledgment

This work was supported in part by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002-506778. This publication only reflects the authors' views.