Thomas Paviot
email: thomas.paviot@supmeca.fr

Vincent Cheutet
email: vincent.cheutet@supmeca.fr

Samir Lamouri
email: samir.lamouri@supmeca.fr

Design and logistics IT federation through Product Lifecycle Support standard

Keywords: PLM, interoperability, PDM, ERP, PLCS

Wide diffusion of methodologies and software relevant to Product Lifecycle Management (PLM) in industrial companies faces heterogeneity of IT systems. Especially, the lack of interoperability between Product Data Management (PDM) systems, that drive virtual product development, and Enterprise Resource Planning (ERP), which manages real product, cannot lead to a coherent description of the product development process. We show that a "mediator" approach is pertinent for the coordination of these two systems. The use of open standards, and more precisely STEP Application Protocol 239, known as Product Lifecycle Support (PLCS), allow overcoming issues related to semantic part of this interoperability. The last part of the paper focuses on preliminary works in order to develop a product model, coherent according to the design or production viewpoints, for a specialization of generic PLCS data model and a future implementation.

Introduction

The current trend of complexification in the development of new products in industrial companies leads to many issues. Complexification is intended here as the multiplication of partners (subcontractors, suppliers, customers located all over the world), the stronger integration between the actors of a project (design, production, marketing, maintenance etc.) as well as the huge amount of data produced, exchanged and stored during the development phase.

Furthermore, although the economical environment is very constraining, the main goals remain to reduce the time-to-market, the costs, and improve the quality of the product. In this paper, we focus on companies in the field of aeronautics and defence industry, which can be characterised by the fact that:

• the products (aircrafts, military vehicles, satellites) have a long lifecycle (up to fifty years), • they evolve in a context of strong regulation (security, traceability, long term data retention),

• these complex products require the participation of many specialized companies, some of them being considered as small and medium business enterprises, • according to the nature of the project, many new partners may be included in the project team, • some major companies can acquire other companies to get specific technologies, • the IT system is highly heterogeneous due to economical or historical reasons. The IT that drives the product related data from design to retirement is then a strategic tool. The industrial deployment of this IT must satisfy the need of three main actors:

• the design engineer, maintenance operator, manufacturer, salesman, must be insured that the coherency of the product data for its whole lifecycle, • the IT manager must ensure the flexibility and the agility of the IT architecture, to allow quick and efficient integration of third part IT from another partner, • the head must reduce the total cost of ownership (TCO) of the IT, TCO including initial investment as well as maintenance. In such industrial companies, the choice, deployment, use and maintenance of an efficient IT must then associate these entire actor. In a few words, the systems composing the IT have to interoperate at the lowest cost and with the best quality, i.e. ensure product data coherency. However the dispersion of information over heterogeneous models requires new solutions to preserve the overall coherence of the company information system [START_REF] Roucoules | The PPO Design Model With Respect to Digital Enterprise Technologies Among Product Life Cycle[END_REF].

The purpose of this paper is to demonstrate that the definition and the deployment of an industrial IT architecture as well as a suitable product model are closely related to each other. The exclusive focus on one or the other point fails to achieve both goals previously mentioned. As a consequence, the paper is organized according to these two viewpoints: Section 2 introduces interoperability general statements and the need of standards. Section 3 then discusses the different systems used in design or logistics activities and a possible IT architecture. Section 4 deals with the semantic issue of product representation and the way to solve it using the STEP standard. Section 5 is then a synthesis of these last two sections, and proposes a possible framework to achieve PDM/ERP interoperability. Section 6 concludes this work with the further work required for implementation issues.

Interoperability and standards

According to the surveys of Kosanke [START_REF] Kosanke | ISO Standards for Interoperability: a comparison[END_REF] and [START_REF] Wegner | Interoperability[END_REF][START_REF] Panetto | Towards a classification framework for interoperability of enterprise applications[END_REF], five different definitions of interoperability can be found. However, in the following of this paper, interoperability will be defined as the ability of two or more systems to exchange information and have the meaning of that information accurately and automatically interpreted by the receiving system. This definition is the more adapted to the issue presented since it merges the technical and semantic concepts of interoperability.

When analyzed from the IT viewpoint, these close concurrent definitions can be merged in a multi-level interoperability approach [START_REF] Euzenat | Towards a principled approach to semantic interoperability[END_REF]. There are several levels of interoperability that must be completed in order to make an exchangeable representation understandable by two different systems:

• encoding: segment the representation in characters,

• lexical: segment the representation in words,

• syntactic: structure the representation in sentences,

• semantic: construct the propositional meaning of the representation,

• semiotic: construct the pragmatic meaning of the representation, or its meaning in context. This typology can be compared to [START_REF]European interoperability framework EIF[END_REF], which define three different levels for interoperable enterprise systems:

• technical level: data and message exchange,

• semantic level (i.e., information and service sharing),

• organizational level (i.e., business unit, process and people interactions across organization borders). Considering products with long lifecycles, it's necessary to ensure the product data coherency over decades. As a consequence, the product description must be robust whenever a change occurs in the enterprise organization and/or business processes. Due to the dynamic property of economical environment, these processes may be volatile whereas product information must remain stable. Baïna et al. [START_REF] Baïna | New paradigms for a product oriented modeling: Case study for traceability[END_REF] introduce the concept of 'product-oriented interoperability', i.e. the ability of different enterprise systems to manage, exchange and share product information in a complete transparency to the user. In that sense, the enterprise system interoperability problem solving must be driven by the semantic level, that is, the product representation.

The use of standards is underlined in the literature as a way to overcome technical issues in the interoperability field. According to [START_REF] Chen | Standards on enterprise integration and engineering -A state of the art[END_REF][START_REF] Lee | A system integration framework through development of ISO 10303-based product model for steel bridges[END_REF], enterprise interoperability requires a fair amount of open standards to be able to share and exchange information in a distributed organizations and heterogeneous computer environment.

There are also economical arguments in favour of standards. The American National Institute for Standards and Technology (NIST) [START_REF]Economic Impact Assessment of the International STEP Standard in Transportation Equipment Industries[END_REF] identifies three costs of interoperability: avoidance costs, migration costs and delay costs. The NIST estimates that the use of the STEP [START_REF] Pratt | ISO 10303: the STEP standard for product data exchange, and its capabilities[END_REF] standard has the potential to save up to one billion dollars per year by reducing interoperability problems in the automotive, aerospace, and shipbuilding industries.

General arguments of §2.1 and §2.2 are specialized for the need of PDM/ERP interoperability (cf. §3). The technical and economical considerations of §2.3 lead to investigate the STEP standard as a possible way to be the basis of the 'product driven interoperability' (cf. §4) approach.

Design/Logistics IT interoperability definition and needs

Design and logistics tools

The product design process is structure about two families of systems: authoring tools and Product Data Management (PDM) systems. Authoring tools are relevant to creation/modification of design documents: 3D MCAD, ECAD, requirements etc. All these authoring tools are providers of data for the Product Data Management (PDM) system. The PDM system is designed to manage product design data lifecycle.

A Product Data Management Tool must have the following features [START_REF] Audrain | Management of industrial assets: integration of a PDM software with an EAM tool[END_REF]:

• the exhaustive list of parts that compose the product,

• parts and documents maturity state management,

• integration with authoring tools,

• product breakdowns and multiview access (as-designed, as-built, as plan, as maintained) However, PDM system is not intended to manage spare parts neither physical parts (nor parts as individuals).

On the logistics side, Enterprise Resource Planning (ERP) systems are dedicated to sourcing logistics, maintenance, orders/service forecasting, production planning. ERP is not suitable for access design information, or to organize or structure the design process. There is however a narrow link between what has been developed during the design phase and how it is produced [START_REF] Roucoules | The PPO Design Model With Respect to Digital Enterprise Technologies Among Product Life Cycle[END_REF] and thus a deep relationship between the systems dedicated to each of these phases: they must interoperate to enable information exchange between the design and production. Unfortunately there is no native integration or interoperability support between PDM or ERP commercial products, although the needs expressed by end users are well known: engineering bill-of-material (EBOM) to manufacturing bill-of-material (MBOM) bidirectional conversion, inventory level accessibility for designers, access to design information for maintenance operators and As-Maintained/As designed issues [START_REF] Cimdata | PLM and ERP Integration: Business Efficiency and Value[END_REF]. The initial step to ERP/PDM integration can then be to build a semantic bridge between PDM parts/product breakdowns and production management concepts related to Material Requirement Planning (MRP) such as bill-ofmaterials, routings and work centers.

Interoperability attempts in the PLM field

The literature gives examples of interoperability involving PDM or ERP systems. The main interoperability issue in the design phase seems to be the CAD/PDM integration [START_REF] Guyot | Product data and digital mock-up exchange based on PLM[END_REF][START_REF] Oh | Mapping product structures between CAD and PDM systems using UML[END_REF][START_REF] Paviot | MultiCAD/MultiPDM integration framework[END_REF]. There are also a few works related to ERP/MES interoperability (see for instance [START_REF] Baïna | New paradigms for a product oriented modeling: Case study for traceability[END_REF]). However, according to the state of our work, it appears that the PDM/ERP interoperability field is still opened. These two families of systems involve people of different cultures that do not share the same semantic view of the product: while designers work to define a virtual product (i.e. a representation of the product using digital information) that fit the requirements, logistics focus on the real product considered as a the incoming/outgoing piece of a set of time based activities (cf. fig. 1). This semantic issue is here considered as the major issue to solve in order to achieve PDM/ERP interoperability.

Figure 1 The need/lack of a PDM/ERP interoperability

! " " " " " " " " # $ # $ # $ # $

A mediator based interoperability architecture

When attempting to implement interoperability between two systems without changing them, two different approaches can be listed: a point-to-point integration or an Enterprise Application Interface (EAI) based interoperability. Assuming a set of 2n systems to connect, point-to-point integration requires a number of translators equals to 2n(n-1). This is thus unacceptable in terms of software development and maintenance costs [START_REF] Guyot | Product data and digital mock-up exchange based on PLM[END_REF].

The EAI solution, i.e. a central subsystem responsible for the communication between all other systems, is pertinent from an economical viewpoint since the number of required translators decreases to n. This approach has been recently extended by the 'IT mediator' concept [17]. Assuming the systems are Service Oriented Architecture (SOA), the mediator organizes data conversion, process orchestration and application management. This hypothesis is here validated since current trend is to make commercial products become SOA based (for instance TeamCenter, Windchill, SAP, Adonix, MatrixOne etc.), and this approach is a possible and efficient way to consider PLM interoperability in general and design/logistics in particular.

The upcoming 2.0 release of the OMG PLM Services offers a wide range of available services in the field of PLM: part identification, product structure, documentation management, shape/transformation, classification, properties, alias identification, authorization, configuration management, change and work management, process planning and a multi language support [START_REF]OMG PLM Services Specifications[END_REF].

The product structure interchange and conversion part of this mediator is the core of this study. The next part of the paper (cf. §4) explains how the use of standard can lead the work related to this topic.

Product model driven interoperability using Product Lifecycle Support standard

Standards in PLM

In a recent survey on standards in PLM fields, Rachuri et al [START_REF] Rachuri | Information sharing and exchange in the context of product lifecycle management: Role of Standards[END_REF] propose a four-level hierarchical typology of standards:

• Type 0: standards for implementation languages,

• Type 1: information modelling standards (like EXPRESS, UML, XML for instance), • Type 2: content standards, domain of discourse: product information modelling and exchange standards (STEP), information exchange standards, product visualization standards, e-business and value chain support standards, security standards, • Type 3: architectural frameworks standards. In a product-driven interoperability, we focus on the Type Two standards. According to this typology, the authors map the scope of the major current Type Two (content) standards of the PLM field along two dimensions (product's life cycle major stages or phases, complementary aspects of the information). They conclude that there is no standard that provides full coverage of the PLM support spectrum because it is fragmented, incomplete in coverage and the limited domain of discourse adopted by the vast majority of Type Two standards for content (cf. fig. 2). Considering the design/logistics interoperability context we focus in this paper, it is clear that there is no intersection in the Design/Production/Supply area that could lead to coherent product representation. In the next subchapter, we focus on the way to overcome this issue.

The ISO 10303:239 or Product Lifecycle Support standard

The international standard ISO 10303 [START_REF] Pratt | ISO 10303: the STEP standard for product data exchange, and its capabilities[END_REF] known as Standard for the Exchange of Product model data (STEP) covers computer-interpretable representation of product data, and its exchange. The objective of ISO 10303 is to provide a means of describing product data throughout the life cycle of a product that is independent from any particular computer system [20]. The really first STEP developments were lead by CAD data representation and exchange. STEP became after that a suite of specific content standards known as Application Protocols (APs). At that time, STEP coverage scope is wide, but does not permit to describe the whole lifecycle of a given product. It only allows to structure specific industrial environment around one activity or product typology.

Two events then occurred in the early 2000's:

• In 2002, the STEP PDM Schema [START_REF] Machner | Mapping the user requirements from the VDAORG with the STEP PDM Schema[END_REF] was released. It is a core set of entities in STEP that support the mapping of concepts for Product Data Management (PDM), and built as a subset of APs 203, 214, 212 and 232. It's the first attempt of merging product semantics and data model from these differents APs. • In 2005 is published the AP239, known as Product LifeCycle Support (PLCS) [START_REF] Rosen | Federated through life-cycle support[END_REF]. PLCS is the first STEP Application Protocol addressing a wider scope than other APs and also a generic and extensible product data model. This AP is thus discussed in detail in the next subchapter because identified as a way to merge design and logistics semantics. AP239 propose a framework for the integration, exchange and management of technical data necessary for the support of a complex product and its evolution along its whole lifecycle [23]. Its rich semantic offers information model required to define a complex product and its support solution, to maintain this product, and describe configuration change management of a product and its support solution.

Scope of design/logistics interoperability

PLCS is structured around the concepts of 'product' and 'activity'. In the PLCS semantics, a product can either be a product existing in the real world, a product that may come into existence as a consequence of some realization process, or a set of functions. As well, an activity is defined as the occurrence of an action that has taken place, is taking place, or is expected to take place in the future (change, distilling, design, a process to drill a hole are example of activities). PLCS data model then includes following descriptions:

• representation of product assemblies, product through life and product history. This representation is based on the PDM Schema, • specification and planning of activities for a product, representation of the activity history of a product. These ISO 10303 statements lead to two observations for our purpose:

• in the fig. 1, the small axis of the ellipse representing PLCS location in the (lifecycle, PPE) referential should be longer, since PLCS includes a rich data model for product representation, • The scope of PLCS seems a priori suitable for PDM/ERP interoperability: the product representation, build upon the PDM Schema, match the PDM semantics whereas the activity model adds a temporal parameter that makes possible the description of design processes, manufacturing processes or routings. However, figure 2 shows that PLCS is limited in scope to the 'enterprise services' representation. PLCS aims at covering a wide lifecycle state of the product (from design to disposal or in service use). Aware that it would be impossible to fit all the specific needs of potential PLCS users, the project team designed PLCS as en extensible standard [START_REF] Rosen | Federated through life-cycle support[END_REF]. PLCS thus offers a generic data model that it's possible to specialize, under the condition of a methodology conformance, for specific business domains. This specialized data model is released in a Data Exchange Set (DEX) [24] that defines how to use it. The OASIS consortium is responsible for the development and standardization of these DEXes.

A graphical representation of PLM standards

The attempt of Rachuri et al [START_REF] Rachuri | Information sharing and exchange in the context of product lifecycle management: Role of Standards[END_REF] to map PLM standards to a two dimensional chart misses the fact that PLCS provides an extensible generic data model. This extensibility can be regarded in an other dimension related to business domain. A 3D map representation of STEP standards is proposed (cf. fig. 3), along the three following dimensions:

• lifecycle stage (LC): APLC focus on lifecycle stage (design, manufacturing etc.), • granularity: some AP offers a more detailed product representation than others.

Regarding all STEP AP, the wider is the scope, the less granular is product model, • business domain (BD): APBD cover specific business domains like automotive industry or ship building. This representation shows that the PLCS data model, unlike other APs, can be extended to fit required granularity or business domain. The 'holes' of the figure 2 can then be filled in with the appropriate data model specialization.

Functional architecture

This section presents the PDM/ERP interoperability framework (cf. fig. 4) based on a service oriented mediator (cf. §3.3) and the PLCS product data model (cf. §4). To avoid the redundancy of data, a volatile mapping between ERP and PDM objects is performed. Data flow and workflows orchestration are driven by business needs, i.e. fit the end-user of one system to grab from or populate data to the other system. This framework is composed of (from bottom to top on the figure 4): Lifecycle stages (design, manufacturing, supply, support etc.)

• a set of PLCS translators, that convert the PDM or ERP requested object to or from a PLCS object, • a data mapping director, which merges the information from the translators in a coherent PLCS description, • a complete PDM and ERP semantic representation using the PLCS specialized data model. This data model feeds the data mapping whenever needed, • a public layer intended to receive user queries and return appropriate information. This layer is the SOA part of the framework.

Implementation decisions

A set of use-cases coming from industrial partners are about to be tested. These tests will involve PTC Windchill as well as the free ERP system OpenERP. The free and open source JSDAI API will be used to access the core AP239 data model, PLM services being implemented with the Zolera SOAP Infrastructure (ZSI) framework. The technical architecture is described in fig. 5:

Conclusion and further work

The PDM/ERP interoperability is still an issue for most industrial companies, especially those focused on long lifecycle products. However, an approach based on open standards can overcome these economical as well as technical issues. The use of the STEP PLCS standard can reconcile the design and logistics viewpoints under the condition that the generic data model is specialized according to this semantic extension. The PDMSchema, partly embedded in PLCS, is a natural bridge towards PDM but the ERP semantics, based on the concept of real product and processes, still requires an ontology description. The implementation part of this work will be achieved using the framework presented above, and lead to a demonstrator designed as a proof-of-concept for an industrial deployment.

Figure 2

 2 Figure 2 Rachuri et al. PLM standards 2D map

Figure 3 3D

 3 Figure 3 3D Map representation of STEP Application Protocols

Figure 4

 4 Figure 4 The PLCS/IT mediator based architecture

Figure 5

 5 Figure 5 Technical architecture


Vincent Cheutet
email: vincent.cheutet@supmeca.fr

Samir Lamouri
email: samir.lamouri@supmeca.fr

Thomas Paviot
email: thomas.paviot@supmeca.fr

Ronan Derroisne
email: ronan.derroisne@supmeca.fr

"Evaluation and optimization of innovative production systems of goods and services" CONSISTENCY MANAGEMENT OF SIMULATION INFORMATION IN DIGITAL FACTORY

Keywords: Digital Factory, information consistency, multi layered framework

The Digital Factory aims to design, simulate and optimize the production system as early as possible in the product development process, by taking advantages of available software tools and 3D digital representations. Nevertheless, the multiplicity of simulation models and representations induce heterogeneity of data and information available, which make complex the information consistency management. This article proposes a framework based on a set of multi-layered models representing a production system at the different necessary scales, to ensure consistency between the simulation models.

INTRODUCTION

In a context of increasing competition and reducing time-to-market, the Digital Factory is born to design and simulate the production systems in parallel of the product design process. It can be defined as a set of software tools and methodologies allowing to design, simulate, initiate and optimize the production systems [START_REF] Bracht | The Digital Factory between vision and reality[END_REF], [START_REF] Kühn | Digital Factory -Integration of simulation enhancing the product and production process towards operative control and optimisation[END_REF] [START_REF] Chryssolouris | Digital manufacturing: history, perspectives, and outlook[END_REF]. This approach, coming from the concurrent engineering and from the Computer Integrated Manufacturing (CIM), aims at reducing validation loops by ensuring, as early as possible in the product lifecycle, the integration of the product manufacturability and productibility towards the enterprise constraints. This approach takes part of a Product Lifecycle Management (PLM) approach that aims at sharing information relative to a product in each phase of its lifecycle [START_REF] Cimdata | Product Lifecycle Management (PLM) Definition[END_REF].

One purpose of the Digital Factory is to support the planning process, in case of modifications of the production processes (introduction of a new product or a new workcenter, modification of the production rate, etc.) with a series of tools, such as, e.g. 3D modeling programs or simulation programs. Using these tools the planner or planning team can create a digital image of individual workplaces or even a complete factory, along with the respective production processes. By means of simulations, examinations into possible weaknesses in the planned system can be carried out. Thus, the dynamic factory occurrences can be played through, analyzed and improved. Necessary structural changes can also be carried out and changed directly in the computer model.

Previous research has highlighted the role of virtual engineering tools in the development of manufacturing machinery systems. Simulation models created for this purpose can potentially be used to provide support for other tasks, such as operational planning and service and maintenance. Furthermore, the models must be able to communicate with other business software (De [START_REF] Vin | Simulation Based Decision Support for Manufacturing System Life Cycle Management[END_REF].

Although, with available technologies and systems in CIM or Digital Factory and their related technologies, their application in manufacturing enterprises is still not a reality and cannot meet the need of the enterprises [START_REF] Nagalingam | CIM-still the solution for manufacturing industry[END_REF]. Today managers in many enterprises are confused with varying technologies and new terminologies that prevail in the public domain.

Thus, the Digital Factory is based on a large number of very different digital simulation tools, based on various representation levels of the production system. It is thus possible to realize a flow simulation at the level of a production line, in order to determine stock level necessary to obtain a satisfying customer performance criterion, or to realize the offline programming of a robotic cell, part of the same production line. This heterogeneity of tools and methods implies major problems to ensure the consistency available inside the Digital Factory, in particular between the different simulations. This consistency problem slows down the validation process included in the development process of the product and its production system. The objective of the article is to make an overview of the information management inside the Digital Factory and to propose a model allowing the information consistency management.

The article is structured as following. Section 2 presents a definition of the Digital Factory and its sources of MOSIM '10 -May 10-12, 2010 -Hammamet -Tunisia heterogeneity. Section 3 overviews some existing models or approach dealing with consistency in a digital environment. Section 4 proposes the specifications of a system ensuring the simulation information consistency inside the Digital Factory. Section 5 finally presents the conclusions and perspectives of our approach.

DIGITAL FACTORY -DEFINITION AND HETEROGENEITY

For [START_REF] Wöhlke | Digital Planning Validation in automotive industry[END_REF], Digital Manufacturing links product development [START_REF] Ullman | The Mechanical Design Process[END_REF], production planning and facility planning [START_REF] Fleischmann | Advanced planning[END_REF] (figure 1). As a consequence, the Digital Factory is attached to all enterprise layers and all time horizons, from strategic planning to operational optimization.

Figure 1: Matrix of supply chain planning [START_REF] Fleischmann | Advanced planning[END_REF].

In this context, the projects Digital Factory [START_REF] Boime | Le projet Usine numérique : Un projet du pôle de compétitivité SYSTEM@TIC Paris Région[END_REF] and Digital Factory 2 (UN2, 2008), from the SYSTEM@TIC Paris-Region cluster, have proposed a structured representation of the Digital Factory on six levels of details, corresponding to an aeronautic vision of the extended enterprise (figure 2).

Figure 2: Different layers in the Digital Factory [START_REF] Boime | Le projet Usine numérique : Un projet du pôle de compétitivité SYSTEM@TIC Paris Région[END_REF].

These layers correspond to specific needs for the design and simulation of the production system behavior, and so to specific actors of the production system development process, with their own tools and methodologies. For example, at level 1 or 2, the objective can be to determine the physical supply flows inside the extended enterprise. At level 3, the objective can be to validate a physical layout inside the plant and a line rate. At level 5 or 6, the objective can be to validate the settings of a manufacturing program in the production environment (robots, CNC machining, etc.).

For all layers, one can find specific simulation tools corresponding to specific actors, with different geometric representations and different simulation structures.

Two main families of simulation tools can be defined in the Digital Factory:

-simulation based on events: it is constituted by elements that react to some events: flow simulation, control simulation (GRAFCET for instance), virtual reality, etc. -prescriptive simulation: it describes the behavior of the production systems according to the time, i.e. the realization of an action is done at a given instant: layout analysis, offline programming of MOCN or robots, ergonomics simulation, etc.

The main reasons to use simulation based on events for system analysis in supply chain management are (i) the possibility to include dynamics and (ii) the simplicity of modeling. Discrete event simulation is suited for these kinds of studies where time-dependant relations are analyzed, whereas prescriptive simulations are suited to analysis where time is a key entry.

One can find in the literature many references or examples of simulation and analysis, at each of the previously defined levels, which can be mostly positioned according to figure 3. As an example of simulation by events from levels plantsupply chain, [START_REF] Longo | An advanced supply chain management tool based on modeling and simulation[END_REF] present an advanced modeling approach and a simulation model for supporting supply chain management. The first objective is to develop a flexible, time-efficient and parametric supply chain simulator starting from a discrete event simulation package.

As an example of prescriptive simulation from levels plant-line, [START_REF] Vitanov | A decision support tool to facilitate the design of cellular manufacturing layouts[END_REF] present a decision sup- '10 -May 10-12, 2010 -Hammamet -Tunisia port tool that can be used by practitioners and industrialists to solve practical cell formation problems. The tool is based on a cell formation algorithm that employs a set of heuristic rules to obtain a quasi-optimal solution from both component routing information and other significant production data.

MOSIM

As an example of prescriptive simulation from levels machine-tool, [START_REF] Fernandez-Madrigal | A software engineering approach for the development of heterogeneous robotic applications[END_REF] propose a framework for the integration of heterogeneous robotic software through a software engineering approach: the BABEL development system, which is aimed to cover the main phases of the application lifecycle (design, implementation, testing, and maintenance) when unavoidable heterogeneity conditions are present.

In the idea of multi-layered consideration of the digital manufacturing with a simulation by events approach, [START_REF] Zülch | Modelling of occupational health and safety aspects in the Digital Factory[END_REF] describe an occupational health and safety approach that does not focus only on ergonomic analyses and examinations of single workplaces, but have a macro-ergonomic point-of-view to digital work systems planning which considers all elements of a work system and their interactions.

In the same way, one can cite [START_REF] Honglun | Research on virtual human in ergonomic simulation[END_REF], for who ergonomics analysis is the important step for product validation in the process, and the virtual human is key to the computer-aided product ergonomics. In this paper, ergonomics simulation system is studied based on some elements of ergonomics analysis and assessment.

All these examples illustrate the diversity of simulation objectives, methods and tools that can exist in the Digital Factory. All of them contribute to define and optimize the production system and the supply chain of the extended enterprise, and so each actors participating to this development process should have access to the right information at the right moment.

DIFFERENT REPRESENTATIONS AND MODELS FOR THE DIGITAL FACTORY

These different simulations, based on different simulation core models, need several representations of the factory, either for the level of details of the desiderate simulation than for the constraints of the simulation core model. [START_REF] Drieux | Interfacing product views through a mixed shape representation -Part 2: Model processing description[END_REF] have enlightened the need to have an adequate representation according to current point-of-view, especially according to the simulation constraints.

According to these needs, several works have proposed models that take into account some aspects of the diversity of simulation models and representations.

Consistency between representations

The first source of diversity is the diversity of digital representation of the enterprise. 3D digital representations for production systems are more and more used to take both benefit of the product virtual mock-up and 3D visualization, for a better communication and understanding. In order to take into account this diversity, several approaches can be cited.

The notion of Levels Of Details (LODs) inside a digital geometric representation is a well-known notion in the domain of Computer Sciences. This type of representation has been introduced for the digital design mock-up by [START_REF] Chu | Multi-agent collaborative 3D design with geometric model at different levels of detail[END_REF], who present a scheme for collaborative 3D design using product model at various levels of detail (LODs). Design features are selectively hidden at each level from certain participants, depending on their actual needs and individual accessibility in the collaboration. This type of approach is needed to have consistency between the different digital representations of the Digital Factory, in particular to keep linked the different layers. In the same way, [START_REF] Do | Propagation of engineering changes to multiple product data views using history of product structure changes[END_REF] proposes a comprehensive procedure for engineering change propagation in order to maintain consistency between various product data views (product design, manufacturing or customer support). Unfortunately, these approaches only take into account the static description of the product, and not the complete production system implied by the product.

In order to manage all the simulation models, several solutions have been proposed from the point of view of simulation data exchange.

One can cite the approach of [START_REF] Song | Development of a lightweight CAE middleware for CAE data exchange[END_REF] who suggests a Computer Aided-Engineering (CAE) data exchange method for the effective sharing of geometric and analysis data. The method relies on heterogeneous CAE systems, a virtual reality system, and a developed lightweight CAE middleware for CAE data exchange.

They also designed a generic CAE kernel, which is a critical part of the CAE middleware. The kernel offers a way of storing analysis data from various CAE systems, and, with the aid of a script command, enabling the data to be translated for a different system.

In the same way, the concept of Simulation Lifecycle Management (SLM) has been developed by CAE software editors [START_REF] Simulia | The case for Simulation Lifecycle Management[END_REF], but this concept only deals with complete integrated environment, that is not our case.

But these two approaches are only for the domain of product behavior simulation, and so in the product development process. Such a framework has to be developed in the production system development process.

Consistency between models

The second source of diversity is the heterogeneity of models used for simulation. This diversity originates first from the two simulation families described in section 2, MOSIM'10 -May 10-12, 2010 -Hammamet -Tunisia but also from the diversity of simulation tools and the lack of manufacturing simulation standards.

Anyway, several approaches propose standardized framework for subsets of Digital Factory simulations. [START_REF] Wenzel | Classifications and conventions structure the handling of models within the Digital Factory[END_REF] present an approach, which introduces modeling conventions based on a common world view of its users by applying the metaphor of the Electronic Catalogue as well as a well-defined workflow in order to simplify the work with Digital Factory models as a substantial step towards the application of the Digital Factory to meet practical requirements.

In [START_REF] Lin | A manufacturing system engineering ontology model on the semantic web for inter-enterprise collaboration[END_REF], a general manufacturing system engineering (MSE) knowledge representation scheme, called an MSE ontology model, to facilitate communication and information exchange in interenterprise, multi-disciplinary engineering design teams has been developed and encoded in the standard semantic web language. The proposed approach focuses on how to support information autonomy that allows the individual team members to keep their own preferred languages or information models rather than requiring them all to adopt standardized terminology. The MSE ontology model provides efficient access by common mediated meta-models across all engineering design teams through semantic matching. [START_REF] Mahesh | Towards a generic distributed and collaborative digital manufacturing[END_REF] propose a framework for distributed manufacturing to facilitate collaborative product development and production among geographically distributed functional agents using digitalized information. [START_REF] Ryu | CPM: A collaborative process modeling for cooperative manufacturers[END_REF] have developed a novel modeling method referred to as Collaborative Process Modeling (CPM) to describe collaborative processes. CPM models can be transformed into marked graph models so that we can use the analysis power of Petri Nets. [START_REF] Kojima | A manufacturing XML schema definition and its application to a data management system on the shop floor[END_REF] propose a method based on manufacturing case data that has a direct relation to manufacturing operations. The data are represented in XML schema, as it can be easily applied to Web-based systems on the shop floor. [START_REF] Vichare | A Unified Manufacturing Resource Model for representing CNC machining systems[END_REF] propose a Unified Manufacturing Resource Model termed UMRM. UMRM not only has the novel capability to provide the information to define the various elements of the CNC machining system, but also has the added capability to provide support for automation of process planning decision making.

This problem of simulation model diversity is also present and tackled in the product development process, incorporating both design and industrialization.

In particular, in [START_REF] Tseng | A model for evaluating a design change and the distributed manufacturing operations in a collaborative manufacturing environment[END_REF], the effect of a design change is analyzed by evaluating the affected components and the distributed manufacturing operations from a cost-and-value perspective. The presented model is useful for analyzing the effect of a design change case in a collaborative manufacturing environment.

In [START_REF] Woerner | Security architecture integrated co-operative engineering platform for organised model exchange in a Digital Factory environment[END_REF], new methodologies for computer-supported co-operative development engineering (CSCDE) are developed. Environmental constraints for a successful application of CSCDE are identified and classified.

Nevertheless, all these approach lack to identify a management system that ensures the simulation information consistency in the complete Digital Factory. They only cover a restrictive part of the field, either in terms of levels or in terms of simulation family.

In the production and supply chain domain, one standard is currently emerging to model and simulate the supply chain behavior: the SCOR model (Supply Chain Operation Model) that is a reference model with standardized terminology and processes [START_REF] Cohen | Strategic Supply Chain Management[END_REF]). The SCOR model defines the Supply Chain behavior in four levels: Top Level (Process Types), Configuration Level (Process Categories) Process Element Level (Decompose Processes) and Implementation Level (Decompose Process Elements) (figure 4). MOSIM '10 -May 10-12, 2010 -Hammamet -Tunisia This model has been used with success to model and simulate supply chain behavior [START_REF] Persson | The development of a dynamic supply chain analysis tool -Integration of SCOR and discrete event simulation[END_REF]. But it does not take into account the digital representation of the production system elements and so the consistency between them.

SPECIFICATIONS OF A CONSISTENCY MANAGEMENT SYSTEM

As stated in the previous sections, the consistency problem in the Digital Factory originates from two different sources: digital representations and simulation models. Moreover, this problem is enforced by the multilayers framework of the Digital Factory and the heterogeneity of actors participating to the production system development process. Most of the approaches presented before are tackling the problem by managing only a part of simulation results (as rate, tack time, stock levels…), but without taking into account the simulation preparation process and in particular the 3D models that are more and more used in the Digital Factory simulations.

All these heterogeneities imply different semantics for the actors, which make the communication between actors more and more complex. Nevertheless, these different semantics are necessary for the development process, as [START_REF] Léon | Acquiring, structuring shapes and annotating them with semantics to improve design activities[END_REF] demonstrated how various categories of semantic can enhance the design process within virtual environments.

In order to structure the simulation models and specify the possible exchange between them (especially between the 3D representations used in the Digital Factory simulations), we propose to extend an existing model framework with three layers, which is able to describe any shape in context. This model framework is based on the decomposition of a shape in three layers: geometry, structure and semantics, established by the European network of excellence AIM@SHAPE [START_REF] Falcidieno | Towards the semantics of digital shapes: the AIM@SHAPE approach[END_REF].

This layered architecture shows the models and processes involved when upgrading low-level shape information to high-level shape knowledge representations (figure 5). Tools and processes are links between the different layers of such architecture. A first organization of the shape data into a computational structure gives access to the geometric level of representation. The structural level is reached by organizing the geometric information and/or shape data to reflect and/or make explicit the association between parts/components of shape geometric models or shape data. At the semantic level, which is the highest level of representation, there is the association of a specific semantics to structured and/or geometric models through annotation of shapes, or shape sub-domains according to the specific application domain. The layered architecture emphasizes the separation between the various levels of representations, depending on the knowledge embedded as well as on their mutual relationships.

Figure 5: Multi-layered model for shape description. This architecture has been proposed with success to the data and information exchange between different points of views in the product development process by [START_REF] Cheutet | Vers une structuration des représentations de composants dans une vue produit : application à la création de lignes clés esthétiques. 10ème Colloque National AIP PRIMECA[END_REF] (figure 6). If the semantic layer takes into account the knowledge environment of the actors, the concurrent engineering constraints can be successfully taken into account inside the structural level. The model communication between software is more efficient with the product shape than with the product geometry, since each actor needs his/her specific geometric model. It is also more efficient than with the semantic level, since each actor has his/her own point of view on the product. Similarly, the structural layer improves model sharing between different actors. Figure 6: Application of structured representation model to views "models preparation for FEA" and "representation by machining features" [START_REF] Cheutet | Vers une structuration des représentations de composants dans une vue produit : application à la création de lignes clés esthétiques. 10ème Colloque National AIP PRIMECA[END_REF].

This layered model is compatible with the hierarchy data / information / knowledge, based on definitions proposed by [START_REF] Tsuchiya | Improving Knowledge Creation Ability through Organizational Learning[END_REF]: when datum is sense-given through interpretative framework, it becomes information; when MOSIM'10 -May 10-12, 2010 -Hammamet -Tunisia information is sense-read through interpretative framework, it becomes knowledge. With these definitions, we can draw a parallel between geometry and data, structure and information and semantics and knowledge (figure 7).

Figure 7: Correspondence between the multi-layered model and data/information/knowledge hierarchy.

As a consequence, the exchange between different point of view is more efficient between two structural layers than the other ones, i.e. between information layers than data layers (all the conceptual model has to be rebuild to completely perform the exchange) or knowledge layers (knowledge belongs to a specific actor or point of view on the product). This is why, in the Digital Factory, the framework consistency will be based on simulation information and not simulation data nor simulation knowledge.

The structural layer is also adapted to develop a LOD model between two different levels of the Digital Factory, by using a recursive structure like tree architecture, SADT models, etc.

This approach is compatible with the one proposed by [START_REF] Gunendran | An information and knowledge framework for multiperspective design and manufacture[END_REF]. To support flexible integration between multiple views, the authors present a novel framework that capture the combination of information and knowledge in two separate but related layers. This approach provides a flexible environment that is easy to maintain and can operate on new perspectives as they are introduced and as new knowledge is identified. The purpose of our approach is to add the geometric layer (and so data) in the framework, to take into account the diversity of geometric representations, like B-Rep NURBS model, meshes or 2D sketches.

As an application, we can apply this layered model to two simulation models used in the Digital Factory (figure 8). On the left of the arrow of figure 8, we present the model applied on a flow simulation, realized with 3DCreate tool of Visual Components1 , which simulates the behavior of an aeronautic assembly line, in order to optimize the use rate of the different resources dedicated to the production line. On the right of the same arrow, we present the model applied on a robotic simulation, realized with DELMIA V5 tool of Dassault Systèmes 2 , which simulates the behavior of an automobile robotic cell, in order to validate the layout of the cell and to program off-line the robots.

Figure 8: Application of the multi-layered model to two types of simulation models in the Digital Factory.

In the flow simulation model, the geometric layer is composed on the digital representation (based on mesh) of 3DCreate. The structural layer is based on a production activity control architecture proposed by [START_REF] Huguet | A conceptual framework for shopfloor production activity control[END_REF]. This architecture is constituted by a set of decision centers that can be defined at different levels, with four main functions: plan, distribute, follow and react. Finally, the semantic layer contains all the semantic description of the simulation (especially the name of each station, product or resource).

In the robotics simulation, the geometric layer is composed on the digital representation (based on B-Rep NURBS model classically used in CAD tool), the structural layer is composed of the PPR (Process Product Resources) tree model and of the PERT model of the activities defining the complete process of the cell, and the semantic layer contains the same type of semantics as before.

In order to ensure the consistency between these two types of simulation, the links have to be established between the two structural layers, i.e. between the production activity control architecture and the aggregation of PPR tree and PERT models.

The validation of the multi-layered model for the information consistency management will be developed in the project OLDP (On-Line Digital Production) from the SYSTEM@TIC Paris-Region cluster (OLDP, 2009), which continues the projects Usine Numérique and Usine Numérique 2.

CONCLUSIONS AND PERSPECTIVES

The Digital Factory is characterized by the diversity and 2 http://www.3ds.com/fr/products/delmia/welcome/ MOSIM'10 -May 10-12, 2010 -Hammamet -Tunisia heterogeneity of simulation models that are used to design, simulate and optimize a production system as early as possible. Moreover, the problem is more complex due to the different levels of details that are necessary to perform such simulation. As a consequence, the construction of the different simulation models can be timeconsuming and very few information validation tools are available to ensure the consistency of the simulations between them.

To overcome this issue, this article proposes a framework defined by a set of multi-layered models of the product and its production system, linked through their structural representations.

The next step of this work will be to define the different multi-layered models for the different simulation models that are used in the Digital Factory and to create links between all the structural layers. To obtain such results, two main domains should be invested.

The first one is the methodology proposed by [START_REF] Curran | Digital Lean Manufacture (DLM): A New Management Methodology for Production Operations Integration[END_REF], for the systematic integration of digital manufacturing through Digital Lean Manufacturing (DLM). DLM offers a new management methodology for production operations integration that achieves vertical and horizontal integration of process, tools and systemic manufacturing effort.

The second aspect, in a very different scientific field, treats of the integration of different simulations from very different levels: the multi-physics and multi-scale modeling and simulation [START_REF] Michopoulos | Modeling and Simulation of Multiphysics Systems[END_REF]. This approach takes into account all phenomena, coupled between them, acting on the system. On the physics aspect, the approach takes into account coupling between elementary phenomena at different scale of different field. This type of modeling aims at giving a description of the phenomena at different scales. In this field, [START_REF] Gravemeier | Towards a taxonomy for multiscale methods in computational mechanics: building blocks of existing methods[END_REF] propose a step towards a taxonomy for multiscale methods in computational mechanics, that can be used to draw a parallel with our field of interest. This approach will be further explored to understand how it could enrich the proposed model.

Figure 3 :

 3 Figure 3: Positions of main simulation types.

Figure 4 :

 4 Figure 4: SCOR model decomposition (SCOR, 2009).

http://www.visualcomponents.com/index.php?id=141


Djalel Benbouzid
email: djalel.benbouzid@gmail.com

Róbert Busa-Fekete

Balázs Kégl
email: balazs.kegl@gmail.com

Fast classification using sparse decision DAGs

In this paper we propose an algorithm that builds sparse decision DAGs (directed acyclic graphs) from a list of base classifiers provided by an external learning method such as AdaBoost. The basic idea is to cast the DAG design task as a Markov decision process. Each instance can decide to use or to skip each base classifier, based on the current state of the classifier being built. The result is a sparse decision DAG where the base classifiers are selected in a data-dependent way. The method has a single hyperparameter with a clear semantics of controlling the accuracy/speed trade-off. The algorithm is competitive with state-of-the-art cascade detectors on three object-detection benchmarks, and it clearly outperforms them when there is a small number of base classifiers. Unlike cascades, it is also readily applicable for multi-class classification. Using the multi-class setup, we show on a benchmark Web page ranking data set that we can significantly improve the decision speed without harming the performance of the ranker.

Introduction

There are numerous applications where the computational requirements of classifying a test instance are as important as the performance of the classifier itself. Object detection in images [START_REF] Viola | Robust real-time face detection[END_REF] and web page ranking (Chapelle & Chang, 2011) high energy physics [START_REF] Gligorov | A single track HLT1 trigger[END_REF]. Most of these applications come with another common feature: the negative class (usually called noise or background) sometimes has orders of magnitudes higher probability than the positive class. Besides the testing time constraints, this also makes training difficult: traditional classification-error-based measures are not adequate, and using prior class probabilities in constructing training samples leads to either enormous data sizes or little representativity of the positive class.

A common solution to these problems is to design cascade classifiers [START_REF] Viola | Robust real-time face detection[END_REF]. A cascade classifier consists of stages. In each stage a binary classifier attempts to eliminate background instances by classifying them negatively. Positive classification in inner stages sends the instance to the next stage, so detection can only be made in the last stage. By using simple and fast classifiers in the first stages, "easy" background instances can be rejected fast, shortening the expected testing time. The cascade structure also allows us to use different training sets in different stages, having more difficult background samples in later stages.

Cascade classifiers, however, have many disadvantages in both the training and test phases. The training process requires a lot of hand-tuning of control parameters, and it is non-trivial how to handle the tradeoff between the performance and the complexity of the cascade. Also, each individual stage needs to be trained with examples that have been classified positively by all the previous stages, which becomes difficult to satisfy in the later stages. Moreover, during test time, the cascade structure itself has several drawbacks. First, for a given stage, the margin information of a test example is lost and is not exploited in the subsequent stages. Second, all the positive instances have to pass through all the stages for a correct clas-sification. Finally, extending the cascade architecture to the multi-class case is non-trivial. For example in web page ranking, it is just as crucial to make a fast prediction on the relevance of a web page to a query as in object detection (Chapelle et al., 2011a), but unlike in object detection, human annotation often provides more than two relevance levels.

In this paper we propose a method intended to overcome these problems. In our setup we assume that we are given a sequence of low-complexity, possibly multiclass base classifiers (or features) sorted by importance or quality. Our strategy is to design a controller or a decision maker which decides which base classifiers should be evaluated for a given instance. The controller makes its decision sequentially based on the output of the base classifiers evaluated so far. It has three possibilities in each step: 1) it can decide to continue the classification by evaluating the next classifier, 2) skip a classifier by jumping over it, or 3) quit and use the current combined classifier. The goal of the controller is to achieve a good performance with as few base classifier evaluations as possible. This flexible setup can accommodate any performance evaluation metric and an arbitrary computational cost function. Designing the controller can be naturally cast into a Markov decision process (MDP) framework where the roles are the following: the policy is the controller, the index of the base classifier and the output of classifier constitute the states, the alternatives correspond to the actions, and the rewards are defined based on the target metric and the cost of evaluating the base classifiers.

Our approach has several advantages over cascades. First, we can eliminate stages. Similar to SoftCascade [START_REF] Bourdev | Robust object detection via soft cascade[END_REF], the base classifiers do not have to be organized into a small number of stages before or while learning the cascade. Second, we can easily control the trade-off between the average number of evaluated base classifiers and the quality of the classification by combining these two competing goals into an appropriate reward. The form of the reward can also easily accommodate costsensitivity [START_REF] Saberian | Boosting classifier cascades[END_REF] of the base classifiers although we will not investigate this issue here. The fact that some base classifiers can be skipped has an important consequence: the resulting classifier is sparse, moreover, the number and identities of base classifiers depend on the particular instances. Third, eliminating stages allows each instance to "decide" its own path within the list of base-classifiers. Theoretically, we could have as many different paths as training instances, but, a-posteriori, we observe clustering in the "path-space". Fourth, eliminating stages also greatly simplifies the design. Our algorithm is basically turn-key: it comes with an important design parameter (the trade-off coefficient between accuracy and speed) and a couple of technical hyperparameters of the MDP algorithm that can be kept constant across the benchmark problems we use. Finally, the multi-class extension of the technique is quite straightforward.

Allowing skipping is an important feature of the algorithm. The result of this design choice is that the structure of the learned classifier is not a cascade, but a more general directed acyclic graph or a decision DAG. In fact, the main reason for sticking to the cascade design is that it is easy to control with semi-manual heuristics. Once the construction is automatic, keeping the cascade architecture is no longer a necessary constraint. Allowing skipping is also a crucial difference compared to the approach of [START_REF] Póczos | Learning when to stop thinking and do something![END_REF] who also proposed to learn a cascade in an MDP setup. While their policy simply designs optimal thresholds in stages of a classical cascade, MDDAG outputs a classifier with a different structure. Our method can also be related to the sequential classifier design of [START_REF] Dulac-Arnold | Datum-wise classification: A sequential approach to sparsity[END_REF]. In their approach the action space is much larger: at any state the controler can decide to jump to any of the base classifiers, and so the action space grows with the number of base learners. Whereas this design choice makes feature selection more flexible, it also generates a harder learning problem for the MDP.

The paper is organized as follows. In Section 2 we describe the algorithm, then in Section 3 we present our experimental results. In Section 4 we discuss the algorithm and its connection with existing methods, and in Section 5 we draw some pertinent conclusions.

The MDDAG algorithm

We will assume that we are given a sequence of N base classifiers H =( h 1 , . . . , h N ). Although in most cases cascades are built for binary classification, we will describe the method for the more general multiclass case, which means that h j : X → R K , where X is the input space and K is the number of classes. The semantics of h is that, given an observation x ∈ X , it votes for class ℓ if its ℓth element h ℓ (x) is positive, and votes against class ℓ if h ℓ (x) is negative. The absolute value |h ℓ (x)| can be interpreted as the confidence of the vote. This assumption is naturally satisfied by the output of AdaBoost.MH [START_REF] Schapire | Improved boosting algorithms using confidence-rated predictions[END_REF], but in principle any algorithm that builds its final classifier as a linear combination of simpler functions can be used to provide H. In the case of AdaBoost.MH or multi-class neural networks, the final (or strong or averaged) classifier defined by the full sequence H is f (x)= N j=1 h j (x), and its prediction for the class index of x is ℓ = arg max ℓ f ℓ (x). In binary detection, f is usually used as a scoring function. The observation x is classified as positive if f 1 (x)=-f 2 (x) > θ and background otherwise. The threshold θ is a free parameter that can be tuned to achieve, for instance, a given false positive rate.

The goal of the MDDAG (Markov decision direct acyclic graph) algorithm is to build a sparse final classifier from H that does not use all the base classifiers, and which selects them in a way depending on the instance x to be classified. For a given observation x, we process the base classifiers in their original order. For each base classifier h j , we choose from among three possible actions: 1) we Evaluate h j and continue, 2) we Skip h j and continue, or 3) we Quit and return the classifier built so far. Let

b j (x) = 1 -I {a j = Skip ∨∃j ′ <j: a j ′ = Quit} (1)
be the indicator that h j is evaluated on x, where a j ∈ {Eval, Skip, Quit} is the action taken at step j and the indicator function I {A} is 1 if its argument A is true and 0 otherwise. Then the final classifier built by the procedure is

f (N ) (x)= N j=1 b j (x)h j (x).
(2)

The decision on action a j will be made based on the index of the base classifier j and the output vector of the classifier

f (j) (x)= j j ′ =1 b j ′ (x)h j ′ (x). (3)
built up to step j. 1 Formally, a j = π (s j (x) , where

s j (x)= f (j-1) 1 (x), . . . , f (j-1) K (x),j -1 ∈ R K × N + (
4) is the state we are in before visiting h j , and π is a policy that determines the action in state s j . The initial state s 1 is the zero vector with K + 1 elements. This setup formally defines a Markov decision process (MDP). An MDP is a 4-tuple M =(S, A, P, R), where S is the (possibly infinite) state space and A is the 1 When using AdaBoost.MH, the base classifiers are binary hj(x)={±αj} K , and we normalize the output (3) by P N j=1 αj, but since this factor is constant, the only reason to do so is to make the range of the state space uniform across experiments. countable set of actions. P : S × S × A → [0, 1] is the transition probability kernel which defines the random transitions s (t+1) ∼ P(•|s (t) ,a (t) ) from a state s (t) applying the action a (t) , and R : R × S × A → [0, 1] defines the distribution R(•|s (t) ,a (t) ) of the immediate reward r (t) for each state-action pair. A deterministic policy π assigns an action to each state π : S → A. We will only use undiscounted and episodic MDPs where the policy π is evaluated using the expected sum of rewards

̺ = E T t=1 r (t)
(5) with a finite horizon T . In the episodic setup we also have an initial state (s 1 in our case) and a terminal state s ∞ which is impossible to leave. In our setup, the state s (t) is equivalent to s j (x)(4) with j = t. The action Quit brings the process to the terminal state s ∞ . Note that in s (T ) only the Quit action is allowed.

The rewards

As our primary goal is to achieve a good performance in terms of the evaluation metric of interest, we will penalize the error of f (t) when the action a (t) = Quit is applied. The setup can handle any loss function.

Here, we will use the multi-class 0-1 loss function

L I (f , (x, ℓ)) = I f ℓ (x) -max ℓ ′ =ℓ f ℓ ′ (x) < 0
and the multi-class exponential loss function

L exp (f , (x, ℓ)) = exp   K ℓ ′ =ℓ f ℓ ′ (x) -f ℓ (x)   ,
where the training observations (x, ℓ) ∈ R d × {1, . . . , K} are drawn from a distribution D. Note that in the binary case, L I and L exp recover the classical binary notions.

With these notations, the reward for the Quit action comes from the distribution R(r|s (t) , Quit)=

P (x,ℓ)∼D -L(f , (x, ℓ))|s (t) =(f (t-1) (x),t-1) . ( 6
)
From now on we will refer to our algorithm as MDDAG.I or MDDAG.EXP when we use 0-1 loss or exponential loss, respectively. In principle, any of the usual convex upper bounds (e.g., logistic, hinge, quadratic) could be used in the MDP framework. The exponential loss function was inspired by the setup of AdaBoost [START_REF] Freund | A decision-theoretic generalization of on-line learning and an application to boosting[END_REF][START_REF] Schapire | Improved boosting algorithms using confidence-rated predictions[END_REF].

To encourage sparsity, we will also penalize each evaluated base classifier h by a uniform fixed negative reward R(r|s, Eval)=δ(-βr),

where δ is the Dirac delta and β is a hyperparameter that represents the accuracy-speed trade-off. Note that, again, this flexible setup can accommodate any cost function penalizing the evaluation of base classifiers. Finally, choosing the Skip action does not incur any reward, so R(r|s, Skip)=δ(0).

The goal of reinforcement learning (RL) in our case is to learn a policy which maximizes the expected sum of rewards (5). Since in our setup, the transition P is deterministic given the observation x, the expectation in ( 5) is taken with respect to the random input point (x, ℓ). This means that the global objective of the MDP is to minimize

E (x,ℓ)∼D    L f , (x, ℓ) + β N j=1 b j (x)    . (8)

Learning the policy

There are several efficient algorithms available for learning the policy π using an iid sample D = (x 1 , ℓ 1 ), . . . , (x n , ℓ n ) drawn from D [START_REF] Sutton | Reinforcement learning: an introduction[END_REF]. When P and R are unknown, model-free methods are commonly used for learning the policy π. These methods directly learn a value function (the expected reward in a state or for a state-action pair) and derive a policy from it. Among model-free RL algorithms, temporal-difference (TD) learning algorithms are the most widely used. They can be divided into two groups: off-policy and on-policy methods. In the case of off-policy methods the policy search method learns about one policy while following another, whereas in the on-policy case the policy search algorithm seeks to improve the current policy by maintaining sufficient exploration. On-policy methods have an appealing practical advantage: they usually converge faster to the optimal policy than off-policy methods.

We shall use the SARSA(λ) algorithm [START_REF] Rummery | On-line Q-learning using connectionist systems[END_REF] with replacing traces to learn the policy π. For more details, we refer the reader to [START_REF] Szepesvári | Algorithms for Reinforcement Learning[END_REF]. SARSA(λ) is an on-policy method, so to make sure that all policies can be visited with nonzero probability, we use an ǫ-greedy exploration strategy. To be precise, we apply SARSA in an episodic setup: we use a random training instance x from D per episode. The instance follows the current policy with probability 1ǫ and chooses a random action with probability ǫ. The instance observes the immediate rewards defined based on some loss function, or (7) after each action. The policy is updated during the episode according to SARSA(λ).

In our experiments we used AdaBoost.MH2 to obtain a pool of weak classifiers H, and the RL Toolbox 2.03 for training the MDDAG. We ran Ad-aBoost.MH for N = 1000 iterations, and then trained SARSA(λ) on the same training set. The hyperparameters of SARSA(λ) were kept constant throughout the experiments. We set λ to 0.95. In principle, the learning rate should decrease to 0, but we found that this setting forced the algorithm to converge too fast to suboptimal solutions. Instead we set the learning rate to a constant 0.2, we evaluated the current policy after every 10000 episodes, and we selected the best policy based on their performance also on the training set (overfitting the MDP was a nonissue). The exploration term ǫ was decreased gradually as 0.3 × 1/⌈ 10000 τ ⌉, where τ is the number of training episodes. We trained SARSA(λ) for 10 6 episodes.

As a final remark, note that maximizing (8) over the data set D is equivalent to minimizing a margin-based loss with an L 0 constraint. If r I (6) is used as a reward, the loss is also non-convex, but minimizing a loss with an L 0 constraint is NP-hard even if the loss is convex [START_REF] Davis | Adaptive greedy approximations[END_REF]. So, what we are aiming at is an MDP-based heuristic to solve an NP-hard problem, something that is not without precedent [START_REF] Ejov | An interior point heuristic for the Hamiltonian cycle problem via Markov Decision Processes[END_REF]. This equivalence implies that even though the algorithm would converge in the ideal case (with a decreasing learning rate), in principle, convergence can be exponentially slow in n. In practice, however, we had no problem finding good policies in reasonable training time.

Experiments

In Section 3.1 we first verify the sparsity and heterogeneity hypotheses on a synthetic toy example. In Section 3.2, we compare MDDAG with state-of-theart cascade detectors on three object detection benchmarks. After, in Section 3.3 we show how the multiclass version of MDDAG performs on a benchmark web page ranking problem.

Synthetic data

The aim of this experiment was to verify whether MDDAG can learn the subset of "useful" base classifiers in a data-dependent way. We created a twodimensional binary dataset with real-valued features where the positive class was composed of two easily separable clusters (see Figure 1(a)). This is a typical case where AdaBoost or a traditional cascade is suboptimal since they both have to use all the base classifiers for all the positive instances [START_REF] Bourdev | Robust object detection via soft cascade[END_REF].

We ran MDDAG.I with β =0.01 on the 1000 decision stumps learned by AdaBoost.MH. In Figure 1(b), we plot the number of base classifiers used for each individual positive instance as a function of the twodimensional instance itself. As expected, the "easier" the instance, the smaller the number of base classifiers are needed for classification. Figure 1(c) confirms our second hypothesis: base classifiers are used selectively, depending on whether the positive instance is in the blue or red cluster.

The lower panel of Figure 1 shows a graphical representation of the MDDAG classifier f acting on a data set D. The nodes of the directed acyclic graph (DAG) are the base classifiers in H. Each observation (x, ℓ) ∈ D determines a set of edges

U x = {(j, j ′ ):b j (x)=b j ′ (x) = 1∧ b j ′′ (x) = 0 for all j < j ′′ <j ′ }.
In other words, we take all the base classifiers that are evaluated on the instance (x, ℓ) and connect the nodes representing these base classifiers with a direct edge. The edge set U x is called the classification path of x which constitutes a directed path by definition. The DAG we plot in Figure 1(d) includes all of the edges U = (x,1)∈D U x generated by the positive instances taken from the training data D. The width of an edge (j, j ′ ) is proportional to its multiplicity #{x :( j, j ′ ) ∈ U x , (x, 1) ∈ D}. The color of an edge (j, j ′ ) represents the proportion of observations taken from the blue and red sub-classes, whose classification path includes (j, j ′ ). Similarly, the size of the node is proportional to #{x : b j (x) = 1, (x, 1) ∈ D}, and the color of the nodes represent sub-class proportions. The structure of the DAG also agrees with our original intuition, namely that the bulk of the two subclasses are separated early and follow different classification paths. It is also worth noting that even though the number of possible classification paths is exponentially large, the number of realized paths is quite small. Some "noisy" points along the main diagonal (border between the subclasses) generate rare subpaths, but the bulk of the data mostly follows two paths.

Binary detection benchmarks

In these experiments we applied MDDAG on three image data sets often used for benchmarking object detection cascades. VJ [START_REF] Viola | Robust real-time face detection[END_REF] and CBCL are face recognition benchmarks, and DPED [START_REF] Munder | An experimental study on pedestrian classification[END_REF]) is a pedestrian recognition data set. We divided the data sets into training and test sets.

We compared MDDAG to three state-of-the-art object detection algorithms (the original Viola-Jones cascade VJCascade [START_REF] Viola | Robust real-time face detection[END_REF], FC-Boost [START_REF] Saberian | Boosting classifier cascades[END_REF], and Soft-Cascade [START_REF] Bourdev | Robust object detection via soft cascade[END_REF]). VJCascade builds the cascade stage-by-stage by running Ad-aBoost in each stage. It stops adding base classifiers to the mth stage when the false positive rate (FPR) falls below p m fpr and true positive rate (TPR) exceeds p m tpr , where p tpr and p ftr are hyperparameters of the algorithm. The total number of stages is also a hyperparameter. FCBoost also adds base classifiers iteratively to the cascade, but the base classifier can be inserted into any of the stages. The goal is to minimize a global criterion which, similarly to (8), is composed of a performance-based term and a complexity-based term. The number of iterations and the parameter η that determines the trade-off between the two competing objectives are hyperparameters of the algorithm. SoftCascade, like MDDAG, builds a cascade on the output of AdaBoost, where each stage consists of exactly one base classifier. The final number of base classifiers is decided beforehand by the hyperparameter N . In each iteration j, the base classifier with the highest balanced edge is selected, and the detection threshold θ j is set to achieve a TPR of 1exp (αj/N -αI {α < 0}), where α is a second hyperparameter of the algorithm. Both the TPR and the number of base classifiers increase with α, so the choice of α influences the speed/accuracy trade-off (although not as explicitly as our β or FCBoost's η).

Comparing test-time-constrained detection algorithms is quite difficult. The usual trade-off between the false positive rate (FPR) and the true positive rate (TPR) can be captured by ROC curves, but here we also have to take into account the computational efficiency of the detector. In [START_REF] Bourdev | Robust object detection via soft cascade[END_REF] this problem is solved by displaying three-dimensional FPR/TPR/number-of-features surfaces. Here, we decided to show two-dimensional slices of these surfaces: we fix the FPR to reasonable values and plot the TPR against the detection time. In each of the algorithms we used Haar features as base classifiers, so the detection time can be uniformly measured in terms of the average number of base classifiers needed for detection. In typical detection problems the number of background (negative) instances is orders of magnitudes higher than the number of signal (positive) instances, so we computed this average only over the negative test set. It turns out that using this measure, vanilla AdaBoost is fairly competitive with tailormade cascade detectors, so we also included it in the comparison.

Computing the TPR versus number-of-features curve at a fixed FPR cannot be done in a generic algorithmindependent way. For AdaBoost, in each iteration j (that is, for each number j of base classifiers) we tune the detection threshold θ to achieve the given test FPR, and plot the achieved test TPR versus In the other three algorithms we have 2-3 hyperparameters that explicitly or implicitly influence the average number of base classifiers and the overall performance. We ran the algorithms using different hyperparameter combinations. In each run we set the detection threshold θ to achieve the given test FPR. With this threshold, each run k determines a TPR/averagenumber-of-features pair (p k ,N k ) on the training set and (p ′ k ,N ′ k ) on the test set. For each N , we find the run k * (N ) = arg max k:N k ≤N p k that achieves the best training p k using at most N base classifiers, and plot the test TPR p ′ k * (N ) versus N . Although overfitting is not an issue here (the complexity of the classifiers is relatively low), this setup is important for a fair comparison. If overfitting were an issue, the optimization could also be carried out on a validation set, independent of both the test and the training sets. Optimizing the TPR on the training set and plotting it on the test set also explains why the curves are non-monotonic.

Figure 2 shows the results we obtained. Although the differences are quite small, MDDAG outperforms the three benchmarks algorithms consistently in the regime of low number base classifiers, and it is competitive with them over the full range. MDDAG.I is slightly better at low complexities, whereas MDDAG.EXP is more effective at a slightly higher number of base classifiers. This is not surprising as in the low complexity regime the 0-1 error is more aggressive and closer to the measured TPR, whereas when most of the instances are classified correctly, without the margin information it is impossible to improve the policy any further.

Ranking with multi-class DAGs

Although object detection is arguably the best-known test-time-constrained problem, it is far from being unique. In web page ranking, the problem is similar: training time can be almost unlimited, but the learned ranker must be fast to execute. State-of-theart techniques often use thousands of trained models in an ensemble setup (Chapelle et al., 2011b), so extracting lean rankers from the full models is an important practical issue. One of the difficulties in this case is that relevance labels may be non-binary, so classical object-detection cascades cannot be applied. At the same time, the principles used to design cascades re-surface also in this domain, although the setup is rather new and the algorithms require a fair amount of manual tuning [START_REF] Cambazoglu | Early exit optimizations for additive machine learned ranking systems[END_REF]. Despite this, MDDAG can be used for this task as is.

To evaluate MDDAG on a multi-class classification/ranking problem, we present results on the MQ2007 and MQ2008 data sets taken from LETOR 4.0. In web page ranking, observations come in the form of query-document pairs, and the performance of the ranker is evaluated using tailor-made loss or gain functions that take as input the ordering of all the documents given a query. To train a ranker, query-document pairs come with manually annotated relevance labels that are usually multi-valued ({0, 1, 2} in our case). One common performance measure is the Normalized Discounted Cumulative Gain (NDCG m ) [START_REF] Järvelin | Cumulated gain-based evaluation of IR techniques[END_REF] which is based on the first m documents in the order output by the ranker. We used the averaged NDCG score ndcg, provided by LETOR 4.0, that takes an average of the query-wise NDCG m values to evaluate the algorithms. In these experiments the base learners were decision trees with eight leaves.

The goal of MDDAG is similar to the binary case, namely to achieve a comparable performance to Ad-aBoost.MH using fewer base learners. To make the comparison fair, we employed the same calibration method to convert the output of the multi-class clas-sifiers to a scoring function and then to a ranking [START_REF] Li | McRank: Learning to rank using multiple classification and gradient boosting[END_REF]. Since the goal this time was not detection, we simply evaluated the average NDCG for each run k to obtain (ndcg k ,N k ) on the training set and (ndcg ′ k ,N ′ k ) on the test set. We then selected k * (N ) = arg max k:N k ≤N ndcg k and plotted the test ndcg ′ k * (N ) against N . Figure 3 tells us that MDDAG performs as well as AdaBoost.MH with roughly twofold savings in the number of base classifiers.

Related works

Besides [START_REF] Póczos | Learning when to stop thinking and do something![END_REF][START_REF] Dulac-Arnold | Datum-wise classification: A sequential approach to sparsity[END_REF], MDDAG has several close relatives in the family of supervised methods. It is obviously related to algorithms taken from the vast array of sparse meth-ods. The main advantage here is that the MDP setup allows one to achieve sparsity in a dynamical datadependent way. This feature relates the technique to unsupervised sparse coding [START_REF] Lee | Efficient sparse coding algorithms[END_REF][START_REF] Ranzato | Efficient learning of sparse representations with an energybased model[END_REF] rather than to sparse classification or regression. On a more abstract level, MDDAG is also similar to [START_REF] Larochelle | Learning to combine foveal glimpses with a third-order Boltzmann machine[END_REF]'s approach to "learn where to look". Their goal is to find a sequence of two-dimensional features for classifying images in a data-dependent way, whereas we do a similar search in a one-dimensional ordered sequence of features.

Conclusions

In this paper, we introduced an MDP-based design of decision DAGs. The output of the algorithm is a data-dependent sparse classifier, which means that every instance "chooses" the base classifiers or features that it needs to predict its class index. The algorithm is competitive with state-of-the-art cascade detectors on object detection benchmarks, and it is also directly applicable to test-time-constrained problems involving multi-class classification, such as web page ranking. However, in our view, the main benefit of the algorithm is not necessarily its performance, but its simplicity and versatility. First, MDDAG is basically a turn-key procedure: it comes with one userprovided hyperparameter with a clear semantics of directly determining the accuracy-speed trade-off. Second, MDDAG can be readily applied to problems different from classification by redefining the rewards on the Quit and Eval actions. For example, one can easily design regression or cost-sensitive classification DAGs by using an appropriate reward in (6), or add a weighting to (7) if the features have different evaluation costs.

  are well-known examples. A more recent application domain with similar requirements is trigger design in Appearing in Proceedings of the 29 th International Conference on Machine Learning, Edinburgh, Scotland, UK, 2012. Copyright 2012 by the author(s)/owner(s).

Figure 1 .

 1 Figure 1. Experiments with synthetic data. (a) The positive class is composed of the blue and red clusters, and the negative class is the green cluster. (b) The number of base classifiers used for each individual positive instance versus the two-dimensional feature coordinates. (c) The number of positive instances from the blue/red clusters on which a given base classifier was applied according to the policy learned by MDDAG.I. Lower panel: the decision DAG for the positive class.

Figure 2 .

 2 Figure 2. The true positive rate (TPR) vs. the average number of base classifiers evaluated on negative test instances. The results are computed for different fixed false positive rates (FPR) shown in the title of panels. Lower panel: one of the DAGs learned for the VJ database.

Figure 3 .

 3 Figure 3. The average NDCG vs. the average number of base classifiers evaluated on test queries.

http://www.multiboost.org[START_REF] Benbouzid | MultiBoost: a multi-purpose boosting package[END_REF].

http://www.igi.tugraz.at/ril-toolbox/general/ overview.html

Acknowledgments

This work was supported by the ANR-2010-COSI-002 grant of the French National Research Agency.