Keywords: Systèmes embarqués, conception sûre, systèmes adaptatifs, calcul autonomique, synthèse de contrôleurs discrets, programmation synchrone

Contrôle réactif

Context and position statement

Context. Embedded systems are proliferating, in a great variety of environments. Their design involves techniques ranging from application expertise, to software validation, and to System on Chip design.

Embedded systems have to be more and more adaptive: they must perform reconfigurations in reaction to changes in their environment concerning e.g., power supply, communication bandwidth, quality of service, or also typically dependability and fault tolerance for a safe execution. The run-time management of this dynamical adaptivity is the object of research on ways to design and implement adaptation strategies. One approach is in autonomic computing, where functionalities are defined, typically at middleware level, for sensing the state of a system, deciding upon reconfiguration actions, and performing them.

Embedded systems are by nature safety-critical, due to their deep interaction with their embedding environment, machines, goods or people, and also due to their wide-spread use and the cost of maintenance or recall of defect products. They have a special requirement for safe design, which classicaly contradicted dynamical operating system features. Obtaining static predictability is the goal of their specification, validation and verification techniques. The reactive systems approach to this problem exploits finite or bounded models e.g., synchronous, and automated algorithms for verification e.g., by model checking, or synthesis e.g., using discrete controller synthesis (DCS).

Statement. An important concern is then to combine these two different requirements for embedded systems i.e., to be adaptive and predictable. This goal can also be formulated as: a method for the safe design of safe execution systems, a technique for the static guarantee of correct dynamic reconfiguration, a tool for the off-line computation of run-time controllers.

In this position paper, we argue that model-based control of adaptive systems can contribute to this goal, in the following concrete directions:

1. modeling adaptation domains and reconfiguration mechanisms of autonomic systems in terms of their events and states, as discrete event systems;

2. stating the adaptation strategies and safety features in terms of logical properties;

3. obtaining their correct control using the available techniques for specifying, verifying, testing, compiling, and also, more originally, by solving the DCS problem thus defined;

4. obtaining control solutions adapted to each application, exploiting their specificities, thanks to the automation of the method that offers easy modifiability;

5. integrating these formal techniques in a user-aimed tool and method e.g., through the definition of domain-specific languages, with a compilation involving DCS;

6. and, last but not least, integrating an executable form of the resulting controller into the execution platform e.g., at middleware-level.

The scientific interest of the proposal is manifold. Reconfigurable and autonomic systems could benefit from a set of techniques that are formally-based and mechanical, in the sense that automatic tools are already available for use, even if they can still be improved and adapted. Reactive systems models and methods (e.g. DCS) could benefit from being exposed to new demands, notably concerning: at the front-end, expressivity of models in the direction of timed or value-dependent behaviours; at the kernel, efficiency of computations and algorithms implemented in the tools; and also, at the back-end, execution schemes for the synthesized controllers.

The connection of these areas: formal approaches and middleware-level adaptivity, that have developed independently until then, can benefit to the global corpus of design methods for embedded systems. DCS is an opportunity to introduce formal methods in industrial practice in a user-friendly way, notably through the use of domain-specific languages, familiar to experts of application fields, non-experts of formal methods.

Sustaining previous work. We base our statement not only on general considerations arising from a survey of the literature, on the side of autonomic computing [START_REF] Kephart | The vision of autonomic computing[END_REF][START_REF] Krakowiak | Middleware Architecture with Patterns and Frameworks[END_REF] and of discrete event systems and their control [START_REF] Cassandras | Introduction to Discrete Event Systems[END_REF], but we base it also on experience gathered in previous work, which, although not explicitly related to autonomic computing, appears to have been an approach to similar goals.

The focus was on a more specialized application domain, the area of real-time control systems, particularly the programming of robotic systems. The work aimed at contributing techniques for the correct control of multi-task systems, with guaranteed safety of the embedded system, and easy reuseability and modifiability of applications. It resulted on the one hand in a set of modeling patterns for multi-task systems (typically of resources capacities and constraints, activities and services available in the system, and applications making requests). The model patterns can be used as a library to construct a global model of possible behaviors (as a model of the plant in control theory) and a specification of their correctness (as a control objective in regulation techniques). On the other hand, and on these bases, this work resulted in techniques for the automated generation of correct handlers [START_REF] Marchand | Managing multi-mode tasks with time cost and quality levels using optimal discrete control synthesis[END_REF][START_REF] Marchand | Automatic generation of safe handlers for multi-task systems[END_REF] and property-enforcing layers [START_REF] Altisen | Using controller-synthesis techniques to build property-enforcing layers[END_REF], through the use of discrete controller synthesis techniques, implemented in a symbolic computation tool [START_REF] Marchand | Synthesis of discrete-event controllers based on the Signal environment[END_REF], and connected to the synchronous languages and compilers [START_REF] Altisen | Using controller-synthesis techniques to build property-enforcing layers[END_REF].

A further development of our research is the encapsulation of these results into a domainspecific language framework [START_REF] Delaval | A domain-specific language for multi-task systems, applying discrete controller synthesis[END_REF], providing for a tool not requiring the deep formal expertise involved in automata-based models and synthesis algorithms, and wrapping the formal techniques into a compilation-like process. Examples taken from this work are used to illustrate our point in Section 2, and a synthetic account of this work is given below in Section 3.

Organization of the paper. This position paper is organized in order to present material supporting the statement formulated above. It will provide a review of the respective backgrounds: adaptive and reconfigurable systems in Section 2.1, and reactive systems and discrete controller synthesis (DCS) in Section 2.2. It is on these bases that Section 3 for-

INRIA

mulates our proposal for model-based control of adaptive systems, by precising the position in this paper, detailing different aspects of the question, recalling useful preliminary work, and listing some of the opportunities and challenges involved. Section 4 concludes.

Review of the backgrounds

The background of our position lies in each of the two concerned areas of, on the one hand, the middleware-level support of run-time adaptation, reconfiguration and autonomicity, and on the other hand, the formal approach to reactive systems and the techniques of DCS.

Adaptive, reconfigurable and autonomic systems

Systems have to be adaptive, especially embedded and portable devices, because of the dynamicity of their environment, and in order to avoid manual management of reconfiguration [START_REF] Krakowiak | Middleware Architecture with Patterns and Frameworks[END_REF]. They have to be equipped with adaptation mechanisms for sensing and changing configuration, and also for deciding upon the reconfiguration, and controlling the adaptation. Autonomic systems and computing [START_REF] Kephart | The vision of autonomic computing[END_REF] are an approach to the design of such automatic adaptation e.g., in the case of self-configuration or self-optimizing.

An example scenario of adaptation can be illustrated by a cellular phone with a videostreaming application, that enables for visioning of video-on-demand programs, or television broadcast. Such an application can perform in several different modes for fulfilling this functionality, differing in: levels of quality of service (QoS); in a view related to fault-tolerance, they can also be seen as degradation levels, along a degradation axis [START_REF] Segarra | A framework for dynamic adaptation in wireless environments[END_REF].

In the example of display, we can consider:

-modes: high / medium / low resolution, black and white / colour display, compression level.

-quality levels: indeed, an interesting feature is then to have "graceful" degradation, with gracefulness amenable to be defined in different fashions, according to criteria from the application domain. Here, criteria have to decide whether black and white in high resolution is better than colour in medium resolution, or whether it is preferable to avoid abrupt quality change but remain average, or to keep quality at the highest.

resource consumption, that can have quite different characteristics if several algorithms versions of the functionality are available, regarding: computing (in terms of worst-case execution time or CPU load), communication (switching on or off signal compression according to available bandwidth), memory footprint, access time between main and secondary memory, and also energy.

É. Rutten

Adaptation policy is, at a different level, also a point of variability. It has to be defined, how to react to changes in the environment, and what choices to make for a new configuration or mode. The general goal is: Whatever the environment changes, functionality must be fulfilled, at a good level.

In our example, if bandwidth goes down because of signal propagation getting weaker in a badly covered area, then a variety of reactions is possible, including e.g., triggering compression, but then computing time rises, as well as energy consumption. Another reason for reacting can be an incoming message, with an image attachment. If the reception mode involves immediate download, then it could imply degraded video quality in order to free some computing, memory and bandwidth. Or else, reception can be shut off by the user while looking at video uninterrupted and undisturbed, and resumed later. This latter point can illustrate that knowledge of the application state allows for some lookahead in the control.

This example gives an idea of the adaptation criteria, the levels on functionality, the application-specific aspects, the management policies that have to be considered.

Needs for run-time adaptation more generally concern the use of an execution platform by applications, which must be able of variation, as transparently as possible.

In the case of resource management in distributed systems, adaptation can concern available memory, computation capacity, critical sections, communication bandwidth, power supply of portable devices. They can be interrelated, as e.g., processor frequency and voltage, hence power. An example is a component-based approach, with adaptation mechanisms [START_REF] Segarra | A framework for dynamic adaptation in wireless environments[END_REF] e.g., for resources disappearing or re-appearing [START_REF] Buisson | A framework for dynamic adaptation of parallel components[END_REF].

Fault tolerance and error recovery also can rely on reconfiguration amongst a redundancy of computation resources e.g., task migration [START_REF] Dumitrescu | Optimal discrete controller synthesis for modeling of fault-tolerant distributed systems[END_REF] , or degraded modes associated with a management policy.

Switching of execution mode at application or deployment level in Systems on Chip (SoC) or massively parallel architectures can exploit the availability of different implementations (software or hardware) encapsulated under the same API. An example is in the Gaspard2 framework [START_REF]The Gaspard2 framework for SoC design[END_REF]: modes differ by their characteristics, as quantified by performance evaluation techniques [START_REF] Ben Atitallah | An MPSoC performance estimation framework using transaction level modeling[END_REF], and control mechanisms are defined at specification-level [START_REF] Labbani | Chapter 10: Uml2 profile for modelling controlled data parallel applications[END_REF][START_REF] Gamatié | Synchronous modeling of data intensive applications[END_REF] to allow for reconfigurations, implemented e.g., on FPGA [START_REF] Beux | A design flow to map parallel applications onto fpgas[END_REF].

At application-level, the application-specific sequencing of functionalities, the interactive launching of different tasks dynamically, result in phases with quite different resource requirements. Some of the adaptations are of a quantitative nature, that can be modeled as a continuously varying system, and controlled by updating parameters [START_REF] Hellerstein | Feedback Control of Computing Systems[END_REF]. Others are closer to reactive systems with discrete states, between witch transitions are switching upon occurrence of significant events.

INRIA

Mechanisms of adaptation must concretely support the automatic reconfiguration, on the basis of the classical systems management functionalities, the goal of which is to maintain a system's ability to deliver its service with a prescribed quality [START_REF] Krakowiak | Middleware Architecture with Patterns and Frameworks[END_REF]. Functions of system management typically include observation and monitoring, configuration and deployment, reconfiguration, resource management, fault tolerance, security. In the framework of the adaptation control loop, the mechanisms of adaptation must be capable of: sensing or monitoring the state of the system i.e., to monitor and detect causes of reconfiguration; this can involve, in the case of reflexive systems, the maintenance of an explicit model of the state of all concerned entities, at the different levels (hardware, middleware, application, and even possibly environment, as in the case e.g., of fault models for fault tolerance);

acting i.e., they must also have functionalities for installing a new configuration, and deinstalling the former one. They can operate at different levels: task allocation and migration mechanisms, processor frequency control, application-level switch between degraded modes;

deciding : finally, and most importantly, they must have a component to reason upon the past sequences of states and compute the next configuration, in order to close the loop of the adaptive control.

This classical loop is illustrated in Figure 1, reminiscent of the autonomic framework [START_REF] Kephart | The vision of autonomic computing[END_REF]. An autonomic element can be characterized [START_REF] Krakowiak | Middleware Architecture with Patterns and Frameworks[END_REF] by the application of a control loop, through the management interface, to a managed element. The definition of this management as a control theory problem is seen as one of the research challenges of autonomic systems [START_REF] Kephart | Research challenges of autonomic computing[END_REF]. The autonomic element can itself be equipped with a management interface, and be reused in the framework of a composite, also regulated in an autonomic way. Autonomy consist of functionalities of self-management: typically self-configuration, self-optimization, self-healing, self-protection [START_REF] Kephart | The vision of autonomic computing[END_REF]. Figure 1 shows how the decision component has to react to incoming events from the platform or environment, taking into account a knowledge on the application and on the platform, and produce actions and reports. We will place our proposal in this framework, in Figure 10.

Approaches to the control of adaptation are explored in different directions, such as rule-based approaches planning, or neural networks. The emphasis on expressivity and dynamicity sometimes leads to systems where the policy defining adaptivity can be changed at run-time. The design of adaptation controllers seems to be often a manual and ad-hoc work, where predictability is not the main issue. However, research progress in architecural definition of adaptive systems have lead to the clear positioning of the closed loop control in the framework of the middleware platforms; it has also begun identifying criteria and objectives for designing the decision component of the control; and it has clarified what are the management actions available for changing the configuration of systems. In this É. Rutten sense, the definition of adaptive systems is mature and ready for reactive and discrete-event systems-based approaches to be considered. Therefore we claim that a model-based approach, for example based on reactive models and tools, can improve the design of adaptive controllers, for the class of systems where reliability and verifyability are important.

The previous description of adaptation suggests that it resembles control in the broader sense of control theory. Applications of continuous control have been explored e.g., for load management of web servers. We claim here that a parallel approach can be taken fruitfully when considering more logical aspects of systems, where spaces of configurations, execution modes, algorithm versions, have a discrete event system (DES) nature, and are amenable to the application of discrete control notions.

Towards model-based control of adaptation. The proliferation of software, especially in embedded systems, combined with its safety-criticality, plead for the use of well-founded design methods and techniques. The complexity of these systems in size and intricacy makes it essential to have powerful automatic tools for specification, evaluation, verification and transformation, for the sake of the productivity of design.

Formal methods, particularly those aimed at reactive systems, do possess these qualities, and some of them are accompanied by mechanical algorithms for verification and transformation, that are favouring their use by engineers who are experts in the systems to be built, rather than experts in formal models.

Amongst these, Discrete Controller Synthesis (DCS) presents the advantage of being constructive, in the sense that it computes a solution to the problem of the correct control of a system. Indeed, the usability of the approach depends on its understandability, and here the formal technique can be encapsulated as a component of a compilation.

Reactive systems and discrete controller synthesis (DCS)

Embedded systems, which are in continuous interaction with their environment, and which have strict safety-criticality constraints, are considered as reactive systems [START_REF] Harel | On the development of reactive systems[END_REF]. The synchronous approach to reactive systems [START_REF] Benveniste | The synchronous languages twelve years later[END_REF][START_REF] Synalp | Synchronous applications, languages, and programs[END_REF] provides programmers with concrete tools for design: programming languages, compilers, code generators, model-checkers and also a DCS tool [START_REF] Marchand | Synthesis of discrete-event controllers based on the Signal environment[END_REF].

The model-based approach to reactive systems relies on the basic formalism of labeled transition systems. The finite-state machines are composed of discrete states, that can abstract significant value domains, and characterize significant dynamical sequences of events. Transitions between states are labeled with conditions and actions.

Figure 2 gives a small example of an automaton modeling a reactive system, consisting of a counter of event occurrences modulo four. The left part of the figure shows the parallel composition of two one-bit counters. The first one starts initially from state 0, and upon reception of input a makes a transition to state 1. from there, upon a second occurrence of a, it makes a transition, emitting b, back to 0. It is composed in parallel (with the dotted line, in a surrounding box) with another similar automaton counting two occurrences of b to emit c. The composition defines b to be a local event, in the little attached box.

The right part of Figure 2 shows the automaton, a two-bit counter modulo four, resulting from the synchronous composition, wit input a and output c. We will adopt this graphical syntax, and the synchronous composition semantics, in the following, without detailing formalities here [START_REF] Altisen | Using controller-synthesis techniques to build property-enforcing layers[END_REF].

Such modeling formalisms have been applied to described the control behavior of multitask systems [START_REF] Marchand | Managing multi-mode tasks with time cost and quality levels using optimal discrete control synthesis[END_REF], as illustrated in Figure 3 where a task T i , initially Idle, receives a request, and depending upon the control signal ok, can go to a waiting state if it is false, or else it can go to the active state Act, which is hierarchical: there it can switch between three modes H, M and L. These multiple modes correspond to different resource management as well as quality of service policies. The switches are labelled with conditions that control the adaptation.

The synchronous languages [START_REF] Benveniste | The synchronous languages twelve years later[END_REF][START_REF] Synalp | Synchronous applications, languages, and programs[END_REF] (Lustre, Esterel, Signal, Lucid Synchrone, or even Statecharts) provide for high-level language support for the structured construction of such models, enabling the consideration of large and complex systems, the resulting composition being computed by the compilers. As an example, Figure 4, taken from the work on domainspecific language [START_REF] Delaval | A domain-specific language for multi-task systems, applying discrete controller synthesis[END_REF], shows the automaton modeling a multi-task application, where grey

M L c1 c2 c1 c0 Stop c0 c1 c2
Idle i i

Act

Req and not Go Wait Req and Go Go

H i i i i i i i i i i i i i i i i i
s 2 ∧ ¬a 3 ∧ ¬a 1 a 1 ∧ ¬a 3 s 2 ∧ a 3 s 1 s 2 ∧ ¬a 3 ∧ a 1 a 3 ∧ ¬s 1 a 3
Err INRIA zones indicated sub-automata which were not detailed here. One can notice control schemes for putting a task in a waiting state, or mode switching management, resembling Figure 3.

¬s 1 ∧ a 2 s 1 req A/D g ∧ req A/end A, D g ∧ ¬req A/end A r ∧ ¬c/D 1 r ∧ c/D 2 A 1 A 2 g 1 ∧ ¬r/e g 2 ∧ ¬r/e g 1 ∧ r ∧ ¬c/e, D 1 g 2 ∧ r ∧ c/e, D 2
g 2 ∧ r ∧ ¬c/e, D 1
g 1 ∧ r ∧ c/e, D 2
This addresses item 1 of our statement (Sect. 1) Such automata can also be viewed under an equational form, as a sequential transition function, like in classical Boolean circuits, which is illustrated in Figure 5.

Logical properties of these automata concern typically reachability of states, or invariance of subsets of the state-space, required or forbidden sequences of transitions.

The resulting transition system formal model is the concrete representation of designs upon which operations are defined, in the form of algorithms for their analysis (e.g., for verification or test-case generation) or transformation (e.g., automated partitioning into distributed communicating processes). They constitute executable formal models in the sense that code can be generated for efficient simulation purposes, or for execution, in a platformdependent way. The underlying models, and their related algorithmic tools, are subject to complexity and combinatorial explosion problems. However, the size of manageable models is such that meaningful systems can take advantage of the offered services of analysis. This is especially true when the models are adequately structured, and the reactive kernel abstracted from the more computational parts of the system.

Expressivity of the models can be augmented with quantitative information (concerning time , but also values of variables that can be handled by static analysis, or even hybrid systems); however, this involves a considerable cost w.r.t. the related algorithms, and the size of manageable systems is therefore limited.

Discrete controller synthesis (DCS) is one of the automated techniques that can be defined to exploit transition system models. It consists of considering on the one hand, the set of possible behaviours of a discrete event system, within which some events are distinguished as being controllable (they can be inhibited), as illustrated in Figure 6.

On the other hand, it requires a specification of a control objective: a property typically concerning reachability or invariance. Examples related to the previous ones are: behaviours should remain within the sub-set of states declared safe, or the termination state of the application should always be reachable (i.e., avoid entering sub-spaces of states from where there is no way to termination). DCS consists of the computation of the necessary constraints on controllable events so that the objective properties are satisfied by the resulting controlled system, for all possible uncontrollable inputs. When DCS is maximally permissive, the constraint on controllables is minimal: the most possible behaviors are kept. This can be formulated:

Whatever the uncontrollable inputs sequences, the controlled behavior satisfies the objectives. This addresses item 3 of our statement (Sect. 1)

Figure 7 shows how the controller i.e., the synthesized function h, automatically derived and computed, is such that, in a given state X, given any uncontrollable input I u , is can give values to controllables I c , so that the resulting behavior satisfies the control objectives.

Figures 8 shows, from left to right, an example in terms of automata, with five states, and two inputs: one controllable c, and one uncontrollable u. The objective is to make this system invariant w.r.t. the sub-set of state E i.e., to avoid state s3. Given the particular transitions, only a smaller sub-set E' can be controlled: it is part of the work of the DCS algorithm to explore the state space in order to find the controllable transition where control has to be enforced. the automaton on the right shows the controlled system, where in state S2 the controllable Boolean c is forbidden to take the value true, and must be false, hence inhibiting the wrong behavior to be avoided.

DCS was originally defined in the framework of language theory [START_REF] Ramadge | Supervisory control of a class of discrete event processes[END_REF], often called supervisory control of discrete event systems, and is related to game theory. It has been formulated

INRIA in terms of labeled transition systems, and involves algorithms that explore the state space in a way resembling that of model-checking verification, symbolically, with complexity issues and capacities of the same order. Within the synchronous approach, DCS has been defined and implemented as a tool integrated with the synchronous languages: Sigali [START_REF] Marchand | Synthesis of discrete-event controllers based on the Signal environment[END_REF]. It handles transition systems with the multi-event labels typical of the synchronous approach, and features weight functions mechanisms to introduce some quantitative information and perform optimal DCS [START_REF] Dumitrescu | Optimal discrete controller synthesis for modeling of fault-tolerant distributed systems[END_REF]. We use a tool set is illustrated in Figure 9: models of behaviours are synchronous programs written with the Mode automata language; its compiler can produce a format (called z3z) acceptable by Sigali, which also takes the objectives, and produces a controller. This latter is combined with an executable form of the mode automaton, for co-simulation.

DCS techniques have been studied quite less than verification and model-checking, possibly because they involve a design approach closer to control theory than to computer programming, with a model of the system and its behaviours separately from its control. Applications of DCS have classically concerned discrete control theory problems in manufacturing systems. Computer science applications are less frequent; variants of controller synthesis have been applied on timed automata for application-specific scheduling of task systems, and job-shop scheduling problems.

Despite being less popular than model-checking, it could disseminate at least as broadly, because it offers features of a different usefulness: it is more constructive, in that instead of diagnosing bugs, it produces a solution, which is correct by construction, and finds it, if it exists, even if it is so intricate that a programmer would not have thought of it. Also, its mechanical nature makes it integrable in tools where final users do not need expertise in formal technicities.

Towards DCS-based control of adaptive systems. DCS techniques are meant for the control of reactive systems. They have reached a point of maturity where they are usable as a foundation for model-based control of adaptive and reconfigurable systems. Their continuing evolution and improvement will make their useability even better. They can be integrated in a design method that provides users with an automated framework in order to design decision components of adaptive systems, and have a dynamically reconfiguring run-time system platform fulfill the application requirements in a transparent way.

Proposals for model-based control

Position. We argue that model-based control of adaptive systems can contribute to the goal of combining adaptivity and predictability in embedded systems, by defining design methods based on models of the dynamical behaviors involved, and applying automated tools to obtain safe controllers for run-time adaptation. In this position paper, we address these questions for a particular class of systems and properties, expressible as reactive systems and finite-state machines, possibly labeled with some quantitative information. Indeed, at the abstraction level of a reactive kernel managing reconfiguration events and spaces, the adaptation strategy can be formulated as a discrete control problem. DCS techniques can then provide for concrete automated production of correct controllers, that can then be integrated in a run-time platform, connecting this decision component with monitoring and execution facilities. What: Generating property-enforcing layers.

We propose to contribute to the design, assisted by an automated generation tool, of a middleware-level component or layer for adaptive task and resource control, enforcing the properties defining dynamic reconfiguration strategy.

The controller layer is adaptive w.r.t. the state of the run-time execution platform. It reacts to events concerning the monitoring of resources and activities or requests from the application. It makes transitions between states of configuration, so that the application can be fulfilled, while aspects like fault tolerance, power supply, or communication bandwidth are managed transparently, in an autonomic way.

Using DCS techniques provides us with an automated generation of these controllers. This feature provides for easy modifiability and re-generation of a controller; it opens the possibility for taking into account information about the application, in the form of another transition system model, and generate application-specific solutions, which can make a more optimal use of the platform. This addresses item 4 of our statement (Sect. 1)

Figure 10 illustrates our point by showing, in the same framework as Figure 1, how the boxed component at the intermediate layer, at middleware level, interacts with the lower operating system and hardware layer, through monitoring and reconfiguration functionalities, to form a control loop in order to adapt to application requests and other environmental events. This component is built upon models of the platform, the available tasks and services, and also a model of the application, as well as properties defining the control objectives, as seen previously. A controller obtained with DCS constrains the behaviours w.r.t. safety-critical properties. It can also produce reporting information towards the application, such as warning messages, for application-level management.

Why: Safely separating platform control from applications.

The motivation for our work is to alleviate application development from platform details, while allowing for adaptivity in a safe, predictable way. Basing the method upon models and associated algorithms and tools ensures the correctness of the computed controller. The automated tool support enables easy modifyability, and opens the possibility of applicationspecific solutions.

The encapsulation of the DCS formal tools corresponds to a motivation of making the method user-friendly for developers. Specific languages can provide users with constructs in terms of their expertise, while the compilation cares for the formal technicalities.

This addresses item 5 of our statement (Sect. 1) How: connecting model-based synchronous tools and reflexive and autonomic middleware. The identification of adaptive middleware mechanisms, and properties to be controlled, lead to the modeling the space of configurations and the operations occurring when making transitions, and of the DCS objectives. The specification of these automata models is made in synchronous languages. The global model can be compiled into a format compatible with the DCS tool, which can be applied with the objectives.

É. Rutten

The integration of the resulting controlled system is done in the context of the run-time executive. Events signaling input reconfiguration needs, or output reconfiguration actions, are linked to concrete functionalities of the middleware libraries. The execution of the controller and the reactions of its transition system have to be encapsulated in a reactive component, iteratively executing the controlled transition function.

This addresses item 6 of our statement (Sect. 1) Preliminary results. Our proposal builds upon previous work, where some of the aspects were partly explored in separate ways. The present position tends towards a generalization, and concretization at middleware-level.

The automatic generation of safe handlers is explored for multi-task systems inspired by robot programming [START_REF] Marchand | Managing multi-mode tasks with time cost and quality levels using optimal discrete control synthesis[END_REF][START_REF] Marchand | Automatic generation of safe handlers for multi-task systems[END_REF], illustrated in Figure 3, in terms of synchronous modeling, featuring notions of resource consumption, and DCS involving some quantitative aspects. This framework is applied to fault tolerance, in the case of fail-silent faults in a multi-processor system [START_REF] Girault | Discrete controller synthesis for fault-tolerant distributed systems[END_REF]. Given a model of the tasks, and a model of the considered faults, a controller automatically migrates tasks, while enforcing essential properties concerning resource usage and the capacity of the processors, as well as functionality fulfillment, whatever the faults occurring. An extension of this works makes usage of optimal DCS in the case of tasks with checkpoints, and the resulting controller optimizes and guarantees adaptivity to the occurrence of fault events, while guaranteeing a predictable response time [START_REF] Dumitrescu | Optimal discrete controller synthesis for modeling of fault-tolerant distributed systems[END_REF].

A more general framework is then proposed for the automatic generation of propertyenforcing layers [START_REF] Altisen | Using controller-synthesis techniques to build property-enforcing layers[END_REF]. The delimitation of the control layer as a relatively small sub-component, at a proper abstraction-level, linked with other, data-oriented code, enables the scalable applicability of DCS. The method offers a separation of concerns between declarative resource constraints and imperative application. It resulted in the tools environment illustrated in Figure 9.

A domain-specific language is proposed upon these bases [START_REF] Delaval | A domain-specific language for multi-task systems, applying discrete controller synthesis[END_REF], where multi-task systems can be defined, with resources declared with their sharing properties and capacities, tasks with their various resources consumptions, and different modes between which they can switch. Applications are imperative sequencings of these tasks, with a special alternative operator, to describe different ways of fulfilling some functionality, leaving the choice to the controller to be synthesized. The compilation of this simple language is illustrated in Figure 11. It involves a translation into transition systems, as illustrated in Figure 4, with weights associated with states, and into synthesis objectives. The DCS phase is encapsulated into the compilation process, and hidden to the final user.

In the perspective of autonomic systems, our results can be seen as exhibiting capabilities of self-configuration, in terms of resource usage and task management, of self-optimization in the sense that control takes into account consumptions and quality aspects, and of selfhealing in the form of fault recovery control.

Ongoing work is taking place in the direction of implementing the automatically synthesized controllers, in the framework of a control systems programming environment, Orccad [START_REF] Borrelly | The orccad architecture[END_REF]. Applications are composed by assembling robot tasks, each equipped by a small activity controller modelled as an automaton; the applications are themselves hierarchically controlling sub-tasks through a reactive automaton, in a way that originally inpired our work in [START_REF] Delaval | A domain-specific language for multi-task systems, applying discrete controller synthesis[END_REF]. we are modifying models of tasks and applications automata in Orccad, in order to identify controllability, and the resulting controller is designed following the discrete controller synthesis method. The result must then be integrated in the real-time runtime generated by the Orccad environment, where one of the threads is in charge of executing the controller transitions upon the arrival of events. Another direction of work is starting in relation with the Fractal framework [START_REF] Team | The Fractal Project[END_REF]. In this component model, components are equipped with controllers, managing typically their life-cycle; composites are themselves components, where the controller manages amongst others the interactions between sub-components. Our goal is to approach the desing of adaptation controllers in this framework by assembling local controllers and adaptation policy properties into a reactive system, and automatically deriving correct controllers.

Opportunities and challenges are examplified by the following research problems and questions raised.

Modeling of adaptation and reconfiguration mechanisms. DCS techniques. The classical DCS algorithms require to have a global view of the system, which is coherent with a number of adaptive systems, but is not in line with the desire for decentralized control; however, there exist works on modular control techniques that should be explored.

The expressivity of models (and related algorithms) can be extended towards quantitative aspects, like time or value-domains of program variables, or also towards more complex behaviours and properties, involving control with its own state space in addition to that of the controlled system; these extensions have to be approached with consideration of the algorithmic cost that goes with them.

Execution of the controller. Embedding the controller produced by DCS amounts to linking a decision component with the middleware layer, typically with the monitoring functions, and with the task and resource management API. The contents of this component can be optimized by transformation of the synthesized logical constraint in a way that minimizes size or evaluation time.

This controller is the most permissive, and not necessarily deterministic; it has to be completed into a function to be executed. This can be seen as a determinization problem, or one can consider that part of the remaining choices can be done at run-time, on potentially much richer information: typically, quantitative aspects that were abstracted away in the discrete model for the off-line work, can be re-coupled here. The question of having a distributed controller could be approached by using the automated distribution techniques for synchronous programs.

Integration in a user-aimed tool and method. The nature of DCS, at once automatic and constructive, makes it possible to consider its encapsulation into a compilation-like process. There, from a description of resources and tasks in presence, and of an imperative application sequence, the fine-grained, low-level control can be synthesized by a tool, with no involvement from the final user in the possibly intricate synchronizations. This suggest the definition of simple, domain-specific languages, which bring user friendliness by proposing expression in terms familiar to experts of the application fields, and allowing them to remain non-experts of formal methods. In that sense, autonomic and reconfigurable systems are a great opportunity for DCS to be applied as a rigorous approach to control. A challenge coming with this opportunity is that, when no solution is found to the DCS problem, some kind of diagnostic information should be produced, for the designer to modify the design to make it controllable.

Conclusion

In this position paper, we argue that model-based control of adaptive systems, seen as reactive or discrete-event systems, can contribute to the goal of improving embedded systems with adaptivity, while maintaining their safety by continuing ensuring predictability. It can do so concretely by performing the off-line, statical, formal computation of run-time, INRIA dynamical, correct controllers. They can handle self-configuration and self-optimization issues of autonomic systems.

It can be done concretely by the modeling of adaption and reconfiguration functionalities at middleware level in terms of reactive systems, the application of discrete controller synthesis (DCS) techniques, taking into account application specificities, the integration of the controller in the run-time executive. The automation of the DCS tools opens the possibility for their encapsulation in a domain-specific language framework, that ensures user-friendliness.

Perspectives are in the modeling of actual concrete middleware platforms, the exploration of more powerful DCS techniques while keeping efficient, the exploration of execution schemes for the generated controllers, and the definition of domain specific languages encapsulating all that.

Figure 1 :

 1 Figure 1: The control of adaptation.

Figure 2 :

 2 Figure 2: A small example of reactive model.

Figure 3 :

 3 Figure 3: A task model with three modes.

Figure 4 :

 4 Figure 4: Automaton model of a multi-task application.

Figure 5 :Figure 7 :

 57 Figure 5: An equational view of a reactive system

Figure 8 :Figure 9 :

 89 Figure 8: An example of DCS, on an automaton.

Figure 10 :

 10 Figure 10: Model-based control of adaptive systems

Figure 11 :

 11 Figure 11: Domain-specific language.

  An important part of the work consists in a modeling activity, where we have to explore what systems do, what we can model properly (i.e., correctly and also efficiently), what we can handle (i.e., what problems we can contribute to). More precisely, an analysis of actual reflexive and adaptive platforms must be made to determine, while having in view the characteristics of the DCS techniques we use, what are the observation and measure points, what are the control and action points, what are the properties and control objectives, and how the functional goals and quantitative/qualitative properties complement each other.

RR n 6604


Luxin Zhang
email: luxin.zhang@worldline.com

Pascal Germain
email: germain.pascal@inria.fr

Yacine Kessaci
email: yacine.kessaci@worldline.com

Christophe Biernacki
email: christophe.biernacki@inria.fr

Target to Source Coordinate-wise Adaptation of Pre-trained Models

Keywords: Domain Adaptation, Optimal Transport, Feature Selection

Domain adaptation aims to alleviate the gap between source and target data drawn from different distributions. Most of the related works seek either for a latent space where source and target data share the same distribution, or for a transformation of the source distribution to match the target one. In this paper, we introduce an original scenario where the former trained source model is directly reused on target data, requiring only finding a transformation from the target domain to the source domain. As a first approach to tackle this problem, we propose a greedy coordinate-wise transformation leveraging on optimal transport. Beyond being fully independent of the model initially learned on the source data, the achieved transformation has the following three assets: scalability, interpretability and feature-type free (continuous and/or categorical). Our procedure is numerically evaluated on various real datasets, including domain adaptation benchmarks and also a challenging fraud detection dataset with very imbalanced classes. Interestingly, we observe that transforming a small subset of the target features leads to accuracies competitive with "classical" domain adaptation methods.

Introduction

Traditional supervised machine learning algorithms assume the estimated model to be used on the data having the same underlying distribution as the training one. However, this assumption is not always valid. For example, a predictive model may have been trained on a dataset of users living in a specific country, and be used afterward on a dataset of users living in another geographical region. A common domain adaptation strategy used to mitigate these differences is to align the training (source) data and the test (target) data. However, most of these methods rely on training a predictor on the transformed source dataset.

Related Works. To mitigate the gap between source and target domains, former "classical" domain adaptation methods seek to minimize a discrepancy term between the source and target distributions. The minimization of Kullback-Leibler Divergence [START_REF] Sugiyama | Direct importance estimation with model selection and its application to covariate shift adaptation[END_REF] and Maximum Mean Discrepancy [START_REF] Pan | Domain adaptation via transfer component analysis[END_REF] are among the most widely used techniques. The former re-weights source samples in the target domain, while the latter aligns source and target distributions in a latent space. Besides, a recently proposed correlation alignment method [START_REF] Sun | Correlation alignment for unsupervised domain adaptation[END_REF] aims to align the source domain and target domain second-order statistics. Nevertheless, one still needs to re-estimate a model on the transformed source data.

Deep learning approaches have also been proposed to tackle the domain adaptation problem. Methods like Deep Adaptation Networks [START_REF] Long | Learning transferable features with deep adaptation networks[END_REF] and Domain Adversarial Neural Networks [START_REF] Ganin | Domain-adversarial training of neural networks[END_REF] have achieved state-of-the-art results in computer vision tasks. However, it is known that these methods are not interpretable and requires careful tuning of hyperparameters.

Finally, prior works that leverage on optimal transport [START_REF] Courty | Optimal transport for domain adaptation[END_REF][START_REF] Courty | Joint distribution optimal transportation for domain adaptation[END_REF] focus mainly on the source to target transformation and are not scalable to a huge dataset. Hence, to the best of our knowledge, we are the first to tackle the target to source adaptation problem that is scalable and requires no retraining.

Contributions. In this paper, we propose a new domain adaptation perspective by transforming the target data into the source one, and applying directly the pre-trained model on the adapted data. We argue that this strategy is more suited to some real-life scenarios. Indeed, in an industrial context, a prediction system might have been developed and trained by employees or contractors that are no more available. This system being used as a "black box" predictor, it cannot be retrained on a new dataset. However, it is often mandatory to adapt such a system to different contexts, given that the industry wants to expand their business, or just because the data distribution naturally "drift" as time goes.

Therefore, we introduce an original scenario where the former trained model is directly reused on target data, requiring only finding a transformation from the target domain to the source domain. As a first approach to tackle this problem, we propose a greedy coordinate-wise transformation leveraging on optimal transport. Beyond being fully independent of the model initially learned on the source data, we design our approach with the following three characteristics in mind, as we want our method to be appealing for users in an industrial context.

1. Scalability: We want our transformation to be computable even on very large datasets. 2. Interpretability: We want to provide the user some information that can help him to interpret the nature of the target to source transformation. 3. Feature-type free: We want our transformation to apply to a variety of data types. In this paper, we address specifically the case where the data is a mix of numerical and categorical attributes.

Our domain adaptation method is applicable without any label, but we show that one can use few target labels to select the features to adapt. We show empirically that this feature selection scheme leads to competitive results with state-of-the-art domain adaptation methods that necessitate a training phase. Our experiments are performed on three real-life datasets.

Domain Adaptation and Optimal Transport

The Studied Domain Adaptation Framework

Let denote (x, y) ∈ X × Y a data point, where X and Y refer respectively to the input space and the output space. In this paper, X encompasses vectors of categorical and numerical types, possibly mixed together. Moreover, we focus on classification problems, with binary labels Y = {0, 1}, but our method naturally extends to multilabel classification. In the supervised learning framework, one observes a training dataset {(x i , y i )} m i=1 , and each observed training sample (x i , y i ) is viewed as a realization of a random variable pair (X, Y ) obeying a joint probability P (X, Y ). Thus, to learn a classifier, a supervised learning algorithm aims to model P (Y |X) from the training dataset.

The domain adaptation framework differs from the standard supervised learning one by the fact that two distinct joint probabilities over the input-output space X ×Y are considered, referred to as the source domain probability P (X s , Y s ) and the target domain probability P (X t , Y t ). The domain adaptation classification problem is to infer the target predictive model P (Y t |X t ) in the situation where most observed learning data are instances of (X s , Y s ). More precisely, we stand hereafter in the semi-supervised domain adaptation setting where no target label is provided to the learner. We denote the source training points as X s = {x s 1 , . . . , x s i , . . . , x s m } ∈ X m , Y s = {y s 1 , . . . , y s i , . . . , y s m } ∈ Y m , and the target training points as X t = {x t 1 , . . . , x t j , . . . , x t n } ∈ X n . Of course, the challenging task of learning P (Y t |X t ) without target labels4 is only achievable under the assumption that, despite P (X s , Y s ) = P (X t , Y t ), both joint probabilities are "similar" to each other. Any rigorous domain adaptation study must characterize the underlying source-target similarity assumptions. In the domain literature, one common assumption is the so-called covariate shift setting [START_REF] Shimodaira | Improving predictive inference under covariate shift by weighting the log-likelihood function[END_REF], which describes the case where the source domain and target domain output conditional distributions coincide, that is P (Y s |X s ) = P (Y t |X t ) whereas the input marginal distributions P (X s ) and P (X t ) differ. Alternatively, Courty et al. [START_REF] Courty | Optimal transport for domain adaptation[END_REF] assume that there exists a mapping function T : X → X that models the domain drift from the source to the target, such that P (Y s |T (X s )) = P (Y t |X t ). Our work builds on a sibling assumption, that is the existence of a mapping function G : X → X that models the domain drift from the target to the source:

P (Y s |X s ) = P (Y t |G(X t )) .
One could also look for a bijective mapping function such that G -1 = T , but this is not required by our analysis. Inspired by Courty et al. [START_REF] Courty | Optimal transport for domain adaptation[END_REF], we choose to leverage on optimal transport methods to empirically estimate G from the training dataset. Nonetheless, the source to target method of Courty et al. [START_REF] Courty | Optimal transport for domain adaptation[END_REF] requires computing the transportation map from X s to X t , and training a learning model on the training dataset {(T (x s i ), y s i )} m i=1 afterward, while our method is based on the idea of using a pre-trained source model.

Optimal Transport for Domain Adaptation

The optimal transport problem was first introduced by Monge in the 18th century [START_REF] Monge | Mémoire sur la théorie des déblais et des remblais[END_REF] and further developed by Kantorovich in the mid-20th [START_REF] Kantorovich | On the translocation of masses[END_REF]. Intuitively, the original Monge-Kantorovich problem looks for minimal effort to move masses of dirt to fill a given collection of pits. Optimal transport has been revisited over the past years to solve a variety of computational problems [START_REF] Peyré | Computational optimal transport[END_REF], including many machine learning ones [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF]. It is naturally suited for domain adaptation problems [START_REF] Courty | Optimal transport for domain adaptation[END_REF], and it offers a principled method to transform a source distribution into a target one.

Let us now present the important optimal transport notions we rely upon. Even if we tailor the nomenclature to the context of our domain adaptation problem (e.g. we invoke "target" and "source" densities), the remaining part of this section is shared by the general optimal transport literature.

The training sets X s and X t provide discrete estimations of the input domain densities P (X s ) and P (X t ). Classically, we consider the empirical distributions as additions of Dirac functions. Denoting by δ x the Dirac measure on x ∈ X , we define the empirical estimation of the source domain distribution and the target domain distribution as

P (X s ) = m i=1 w s i δ x s i ,
w s i = n j=1 w t j = 1 ; w s i , w t j ≥ 0 .
For simplicity, we assume that every x s i appears only once in X s , respectively x t j in X t . We then write P (X s =x s i ) = w s i and P (X t =x t j ) = w t j . Central to optimal transport methods is the notion of a cost function between a source point and a target point, denoted by

c : X × X → R . (1)
Moreover, C ∈ R m×n denotes the cost matrix between source and target training points such that C i,j = c(x s i , x t j ) corresponds to the cost of moving weight from x t j ∈ X t to x s i ∈ X s . Based on these concepts, we present below the Kantorovich [START_REF] Kantorovich | On the translocation of masses[END_REF] formulation of the optimal transport problem in the discrete case.

Definition 1 (Kantorovich's discrete optimal transport problem). The relationship between source and target examples is encoded as a joint probability coupling matrix γ ∈ R m×n + , where γ i,j corresponds to the weight to be moved from x t j ∈ X t to x s i ∈ X s . The set of admissible coupling matrices is given by

Γ =    γ ∈ R m×n + w s i = n j=1 γ i ,j and w t j = m i=1 γ i,j    .
Then, the optimal coupling matrix γ * is obtained by solving

γ * = argmin γ∈Γ C, γ = argmin γ∈Γ m i=1 n j=1 C i,j γ i,j . (2)
In turns the transformation function G is given by

G(x t j ) = argmin x∈X m i=1 γ * i,j c(x, x t j ) . (3)
The solution x ∈ X of Equation (3) minimization problem is commonly referred to as the barycenter in the optimal transport literature.

Equation ( 2) is a linear optimization problem, and algorithms such as the network simplex or dual ascent methods can be used to compute the solution [START_REF] Peyré | Computational optimal transport[END_REF]. The obtained joint probability γ * reveals the allocation of mass from one domain to the other.

However, the computational complexity of this linear optimization problem is expensive; In the case where the number of target or source training points are equal (m = n), the computation time is O(n 3 ). By adding a regularization term H(γ) = i,j γ i,j log(γ i,j ) to Equation (2), Cuturi [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF] achieve to reduce the computation complexity. The regularized optimization problem is expressed as

γ * η = argmin γ∈Γ C, γ + ηH(γ) , (4)
where η > 0 is a hyperparameter to be fixed. Altschuler et al. [START_REF] Altschuler | Near-linear time approximation algorithms for optimal transport via sinkhorn iteration[END_REF] show that, using the Sinkhorn iteration method [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF], solving the regularized optimal transport of Equation ( 4) requires about O(n 2 log(n)) operations. This is still too expensive to apply to large learning problems. 5 Also, as mentioned before, such domain adaptation methods imply training a new model from the transformed source dataset.

To overcome these limitations of existing domain adaptation methods, we propose in the following section a coordinate-wise target to source domain adaptation method.

Target to Source Coordinate-wise Domain Adaptation

In this section, we formalize our target to source domain adaptation problem and propose our adaptation method.

Formalization of Target to Source Transformation

The originality of our domain adaptation approach is to rely solely on a target to source transformation. That is, we consider that we have access to a source training dataset X s , a target dataset X t , and a pre-trained source predictor

h s : X → Y . (5)
This predictor h s might have been trained on the available source training dataset X s , but it could also originate from another dataset that is no more available. Also, no assumption is made on the nature of the predictor. For instance, it could be a neural network, a support vector machine, a decision tree, etc. Hence, we consider h s as a "black box" predictor, and the goal is to predict the label of the samples in X t . We consider that h s has been trained to minimize a loss function l: Y×Y→IR + . The loss on the source distribution is R l s (h s ) = E l h s (X s ), Y s . In the absence of labeled data, we cannot assess the quality of this estimation. Nonetheless, we want to be able to provide a similar performance on the target distribution, according to the same metric. That is, we would like to find a target to source mapping G : X → X such that h s minimizes the loss on the transformed samples from the target distribution:

R l t (h s •G) = E l h s (G(X t )), Y t .
The following proposition states sufficient conditions (Equations 6 and 7) for which our goal (Equation 8) is achieved. Proposition 1. Under the assumption that

P (Y s ) = P (Y t ) , (6)
if we can find a transformation G : X → X such that ∀x ∈ X ; ∀y ∈ Y :

P (X s = x|Y s = y) = P (X t = G(x)|Y t = y) , (7)
then for any h s : X → Y, we have

R l t (h s • G) = R l s (h s ) . (8)
Proof. The proof is straightforward by noticing that Equations ( 6) and ( 7) imply

∀x ∈ X ; ∀y ∈ Y : P (X s = x, Y s = y) = P (X t = G(x), Y t = y) .
Since the G-mapped target joint probability equals the source joint probability, P (G(X t ), Y t ) = P (X s , Y s ), Equation ( 8) is obtained by a change of variable.

Albeit simple, this training-free target to source perspective on domain adaptation is-up to our knowledge-an unexplored problem. The landscape of possible methods to address this problem is certainly vast. In the remaining part of the paper, we propose and evaluate a variant of optimal transport methods.

Marginal Coordinate-wise Optimal Transport

The target to source transformation explored in the current paper assumes that the output marginal distributions are equivalent, as stated by Equation ( 6) of Proposition 1, and is motivated by the goal to find a mapping G complying Equation [START_REF] Jones | A statistical interpretation of term specificity and its application in retrieval[END_REF]. However, due to the lack of labeled data, it is not possible to directly estimate G; we cannot properly estimate the conditional of the inputs (X s or X t ) given the outputs (Y s or Y t ). In these conditions, we relax the requirement of Equation ( 7), and we seek for a function G belonging to the family of transformations that aligns the input marginal distributions:

P (X s = x) = P (X t = G(x)) . (9)
Inspired by the previous works on optimal transport for domain adaptation introduced in Section 2.2, we choose G to minimize a transportation cost. Although it would be possible to define a cost function (see Equation 1) between every x s i ∈ X s and x t j ∈ X t in order to find the Kantorovich discrete optimal transport problem (Definition 1), it would cause some issues that we aim to overcome:

-Solving Kantorovich's optimization problem (Equation 2), or even its regularized version (Equation 4), is computationally expensive on large datasets; -In the case where the input space X contains mixed attributes, such a mix of numerical and categorical values, defining a cost function might be difficult; -Even in the case where the input space contains exclusively numerical attributes (e.g. X ⊆ R d ), multidimensional distance metrics like Euclidean distance is not able to deal properly with the different scaling of each coordinate. -As performing multidimensional optimal transport addresses the dependence across attributes, the solution is a large variance estimator of the optimal transformation in the case where the available data is not sufficiently abundant.

The proposed domain adaptation method is then performed by solving a sequence of one-dimensional optimal transport method. Doing so, we decompose the transformation G by feature-wise transformations G k :

G = [G 1 , ..., G k , ..., G d ] , (10)
where d is less or equal to the number of features of the input space X . Each elementary transformation G k solves the Kantorovich optimization problem (Equation 2) on one feature only, thus the total computation is generally less expensive compared than the relaxed optimal transport problem (Equation 4). 6The distance measure can also be easily defined for each specific feature, especially when each of them has a different significance. Note that this feature by feature transformation is also robust to variation of scaling.

We denote by d the number of transformations of numerical features. Without loss of generality, we refer the one-dimensional transformations of numerical features as G 1 ...G d , and to the transformations of categorical features as G d +1 ...G d . The next two subsections detail how we process the numerical and the categorical features.

One-Dimensional Mapping of Numerical Features

The 1-D optimal transport on the real line has a closed-form solution [START_REF] Peyré | Computational optimal transport[END_REF] provided that the cost of moving one point to another is defined with respect to an p norm:

∀x s , x t ∈ R , c p num (x s , x t ) = |x s -x t | p .
Different from the resolution of multidimensional optimal transport, in our 1-D scenario, we first need to sort the numerical features values in ascending order. We denote the obtained real-valued vector as

∀k ∈ {1, . . . , d } , X s k = x s k,1 , . . . , x s k,i , . . . , x s k,m ∈ R m , ∀k ∈ {1, . . . , d } , X t k = x t k,1 , . . . , x t k,j , . . . , x t k,n ∈ R n ,
where x s k,i is the k-th feature of a training point in X s , ranked at position i according to the sorted order: x s k,i ≤ x s k,i+1 for all i ∈ {1, . . . , m-1}. Then, the transformation function G k is obtained by the following formula:

G k (x t k,j ) = (F -1 s • F t )(x t k,j ) , (11)
where F t (x t k,j ) is the cumulative distribution function of P (X t ), obtained by counting the elements of vector X t k with values lesser or equal to x t k,j . This solution is also known as increasing arrangement. Note that the transformation G k is a mapping that "moves" the target smallest value to the source smallest value (G k (x t k,1 ) = x s k,1 ), and the target largest value to the source largest value (G k (x t k,n ) = x s k,m ). For the intermediate target points (1 < k < m), the mapping is given by a barycenter in the source domain, according to Equation (3) applied with the choice of the cost function c p .

Recall that sorting a vector of n elements requires O(n log n) steps. For a specific attribute k, once vectors X s k and X t k are sorted, computing G(x t k,j ) for every x t k,j ∈ X t k requires a single pass over both vectors that is O(n) steps (provided n ≥ m). Given that the number of numerical features to process is typically small compared to the number of instances (d n), the required O(d n log n) computational time of our method is favorably compared to the typical O(n 2 log n) time of regularized optimal transport. As for numerical features, we propose to rely on Kantorovich's optimal transport to transform the target features into the source feature, but we cannot rely on a p norm cost function as in Section 3.3. Instead, we need to define a cost function between the categorical values. One could tailor this cost metric to the specificity of the learning problem at hand. In our experiments, we use a generic strategy that can be applied to any categorical features, by defining the cost in terms of the occurrence frequency [START_REF] Jones | A statistical interpretation of term specificity and its application in retrieval[END_REF]:

One-Dimensional Mapping of Categorical Features

Let D k = {e k 1 , . . . ,
∀e k l , e k r ∈ D k , c cate (e k l , e k r ) = C k l,r =      1 if e k l = e k r , 1 1 + log( 1 v k l ) log( 1 v k r )
otherwise, [START_REF] Peyré | Computational optimal transport[END_REF] where v k l ∈ (0, 1] is the frequency of occurrences of the value e k l for the k-th feature in X s k ∪ X t k (respectively v k r ∈ (0, 1] is the frequency of the value e k r ). In Equation ( 12), we write C k l,r for the entry of the cost matrix C k ∈ R n k ×n k . Then, we state our optimal transport problem on a categorical feature in terms of the following coupling matrix γ k ∈ R n k ×n k + in place of Equation ( 2):

γ k = argmin γ∈Γ k C k , γ = argmin γ∈Γ k n k l=1 n k r=1 C k l,r γ l,r , (13)
with

Γ k =    γ ∈ R n k ×n k + {i | x s k,i =e k l } m = n k j=1 γ l,j and {j | x t k,j =e k r } n = n k i=1 γ i,r    .
That is, we perform the optimal transport on the n k categorical values instead of on the n source (and m target examples). Typically, n k n, and the computation is thus less expensive than the original problem. However, unlike numerical features where we can compute a barycenter thanks to Equation (3), the barycenter for categorical features is difficult to define. We distinguish two strategies.

Numerical embedding. In some case, a categorical feature has a numerical representation φ k : D k → R d k (for example, a real vector embedding like the common "Word2Vec" representation). In such cases, we use the barycenter of numerical representations as the adapted value:

G k (e k r ) = argmin x∈R d k n k l=1 γ k l,r c p num (x , φ k (e k r )) . ( 14
)
Stochastic mapping. More generally, we can define a stochastic transformation of categorical features. The probability of transforming one point x t k,j to x s k,i is

P (G k (e k r ) = e k l ) = γ k l,r n k i=1 γ k i,r . ( 15
)
Based on this method, to predict on a target example x t j ∈ X t k with the source predictor h s (Equation 5), we perform a Monte Carlo estimation by sampling the value of every categorical feature thanks to Equation [START_REF] Sun | Correlation alignment for unsupervised domain adaptation[END_REF], and performing an average of the outputs predicted by h s on these stochastic transformations.

Weakly Supervised Feature Selection

We have noticed in various experiments on different domain adaptation tasks that some features contribute more to domain adaptation than others. Instead of adapting all the features, the adaptation of well-selected features has better performance. In the scenario where few labeled target data are available, we propose to use them in order to select the features for which a transformation is beneficial.

The proposed feature selection scheme is a greedy algorithm. At initialization, no feature is adapted. Then, at each step of the process, we transform one feature of the target set. The selected feature is the one allowing the greatest accuracy increase on the small set of labeled target samples. The process is stopped when the accuracy improvement is no more significant according to the following criteria: we perform bootstrap sampling on the target label set, and we stop if more than one half of improvements are negative. Therefore, the remaining unselected features are unchanged when the target to source mapping is applied.

Experiments

In this section, we evaluate our methods on three datasets. The first one is the well-known sentiment classification task on Amazon review datasets. The second one is a fraud detection dataset that we collect from a Kaggle competition. The third one is the real-life industrial fraud detection dataset collected from a company which is one of the leaders of payment systems. Note that the methods that we have compared to are CORAL [START_REF] Sun | Correlation alignment for unsupervised domain adaptation[END_REF] which aligns the correlation matrices between domains, Deep Adaptation Networks (DAN) [START_REF] Long | Learning transferable features with deep adaptation networks[END_REF] which projects the source domain into a latent space and Domain Adversarial Neural Networks (DANN) [START_REF] Ganin | Domain-adversarial training of neural networks[END_REF] which generates the features that are both discriminating and invariant to the change of domains. Extended details concerning the experimental framework, additional results and related works are provided as supplementary material. 7

Datasets

Amazon Reviews. This dataset contains reviews across different product categories from Amazon. Every review is a short text with associated score. According to the scores, reviews are labeled as positive or negative. Using supervised learning, one can build a sentiment classification model to estimate the different points of view of buyers. However, the model trained on one category does not generalize perfectly to another category. Some words appear frequently in reviews of one category but not the others.

The dataset we use here is the same as [START_REF] Chen | Marginalized denoising autoencoders for domain adaptation[END_REF] and [START_REF] Ganin | Domain-adversarial training of neural networks[END_REF]. It is a class-balanced small dataset with 4 domains: Books (B), DVDs (D), Electronics (E) and Kitchen appliances (K). Each domain has 2000 training examples and around 4000 test examples, and features are bags-of-words. We generate a new feature representation using the mSDA unsupervised auto-encoder [START_REF] Chen | Marginalized denoising autoencoders for domain adaptation[END_REF]. We generate two mSDA representations, one with all 5000 words dimensions, and another with only the most frequent 400 words dimensions. Similar to Chen et al. [START_REF] Chen | Marginalized denoising autoencoders for domain adaptation[END_REF] we use a mSDA transformation with 5 layers. However, instead of stacking all hidden representations, we take only the hidden representation of the last layer.

Kaggle Fraud Detection. This is a public dataset from Kaggle IEEE-CIS Fraud Detection competition. 8 The objective is to predict the probability that an online transaction is fraudulent. The dataset contains transactions issued from different devices. We consider the mobile device as the source domain and the desktop device as the target domain. The dimension of the raw dataset is over 400 and contains missing values. Since the paper does not focus on the transformation of features with missing values, we remove all dimensions with more than 1% missing values and all transactions with missing values. The dimension of the dataset after preprocessing is 120 and the proportion of fraud is around 8%. We train the source models in a 4-folds cross-validation way and name the models from Model1 to Model4.

Real Fraud Detection. This real-life fraud detection dataset consists of two domains: Belgian dataset and German dataset. The two datasets are real anonymous clients' transactions in production environments. They have the same mixture types of features, the number of categorical features is 8 and the number of numerical features is 23, numerical features are nearly all generated manually and are normalized between 0 and 1. We use 3 months of data, from July 2018 to October 2018. There are 180 million transactions for Belgian dataset and 90 million for German dataset.

Results

Amazon Reviews. 9 We first test our method on SVM model and compare our proposed method with two other methods that can be easily applied to a target to source adaptation problem. CORAL [START_REF] Sun | Correlation alignment for unsupervised domain adaptation[END_REF] aligns the correlations between domains and OT [START_REF] Courty | Optimal transport for domain adaptation[END_REF] is the optimal transport method in multidimensional space without any regularization. Here we use Euclidean distance as the cost metric.

As shown in Table 1 (the left arrow shows the target to source direction of adaptation), our proposed 1D optimal transport outperforms the two others for this sentiment analysis task. Furthermore, we notice that the multidimensional optimal transport and CORAL consistently perform negative transfer. The potential reason is that the dataset size is not sufficiently large to accurately capture the multidimensional relations between attributes. Table 2 reports experimental results using a neural network predictor. Our method is compared with CORAL, OT and with two deep adaptation methods DAN [START_REF] Long | Learning transferable features with deep adaptation networks[END_REF] and DANN [START_REF] Ganin | Domain-adversarial training of neural networks[END_REF]. For a given dataset, the adaptation of CORAL and OT are deterministic, so no standard deviation is reported. The DANN and DAN models are trained with 30 different random states, and we report the average accuracy and associated standard deviation. On this 5000 dimensional dataset, the 1D optimal transport gets overall results comparable to the best adaptation method, while CORAL and OT still perform negative transfer.

Kaggle Fraud Detection. 10 As shown in Table 3, we evaluate our coordinatewise domain adaptation method by transforming all features (1D OT), only numerical features (1D OT NUM) and only categorical features (1D OT CATE) in an unsupervised setting. We also compare the weakly supervised adaptation method by selecting significant features using few labeled target data to the retraining supervised (marked by ws) model. The column named "%n" shows the percentage of labeled target data that are available. The column "d" shows the number of adapted features on average. The reported metric is the area under the precision-recall curve (PR-AUC). Similar to experiment settings of Amazon reviews task, we repeat 30 times for no deterministic experiments (DANN and DAN) and report their standard deviations. Table 3 first presents results using Gradient Boosting Decision Tree (GBDT) models. The coordinate-wise adaptation method on categorical features achieve the best performance among all unsupervised adaptation methods without retraining. The CORAL has a significant negative transfer on this dataset. Both weakly supervised methods (marked by ws) have improved the performance compared to the adaptation of all features. However, in the situation where 10% of target labels are available, retraining a GBDT model gets the best performance. Compared to weakly supervised methods with 10% of labels, the method using only 1% target labels has comparable performance and less adapted features.

Regarding the neural networks source models, the coordinate-wise adaptation method on all features has the best performance among all unsupervised adaptation methods. In the case where few labeled target examples are available, the weakly supervised adaptation methods have selected the most significant features for domain adaptation and improved the prediction performance. Interestingly, the value of the standard deviation of selected features is smaller in the case of 1% of target labels in most of the experiments. This may due to the fact that selected features is far less than the ones in the case of 10% of target labels.

Fig. 1 reveals the progression of the accuracy metric of our coordinate-wise domain adaptation method using a greedy search feature selection approach. These graphs are obtained using all target labels, in order to show that in an ideal case few feature transformations are required to achieve a good adaptation, and that adapting all features might hurt.

Real Fraud Detection. Similar performance can be observed on the real-life fraud detection adaptation task from Table 4. The models are evaluated in 3 different periods. Notice that in all adaptation tasks except the month of September, at least one of our proposed adaptation methods outperforms the source model.

The weakly supervised adaptation methods in GBDT and neural networks show that with only 1% of label information, the feature selection can achieve comparable performance as the one with 10% of label information and transform fewer features. Both weakly supervised adaptation methods improve the performance than the adaptation of all features. As expected, the standard deviation of adaptation performance with 1% of target labels slightly larger than that with 10% of target labels. Although, in the neural networks, the adaptation method like DAN and DANN have the best performance, they require the retraining of the model and the adaptation is performed in a latent space which is difficult to interpret. Moreover, these two methods are only for neural networks and our proposed methods are totally model independent.

Conclusion and Future Works

This article introduced a new target to source perspective for domain adaptation tasks. An unsupervised and a weakly supervised coordinate-wise transformation are proposed and achieve comparable results to the state-of-the-art methods. In addition, the proposed method is parameter-free and can be easily applied to various families of pre-trained models such as neural networks and decision trees. Although we have shown experimentally that transforming a small subset of target features leads to better predictions. As for future research, we aim to reveal the further relevance between these selected features and domain adaptation tasks.

Fig. 1 .

 1 Fig. 1. Feature selection greedy algorithm with neural networks source model on Kaggle fraud detection task (idealized scenario involving all target labels).

  e k n k } be the (non-ordered) set of values taken by a categorical feature, where k ∈ {d +1, . . . , d} is the feature index, and n k is the number of unique values in D k . We denote the set of source and target values for categorical features by

	∀k ∈ {d +1, . . . , d} , X s k = (x s k,1 , . . . , x s k,i , . . . , x s k,m ) ∈ D m k ,
	∀k ∈ {d +1, . . . , d} , X t k = (x t k,1 , . . . , x t k,j , . . . , x t k,n ) ∈ D n k .

Table 1 .

 1 Amazon reviews results (prediction accuracy) using SVM on 5000 dimensions.

				No Retrain
	Domains	Source	CORAL	OT	1D OT
	B ← D	.8407	.8229	.7420	.8438
	B ← E	.7692	.7283	.6856	.8010
	B ← K	.8445	.7527	.7098	.8403
	D ← B	.8358	.8132	.7433	.8351
	D ← E	.8002	.7511	.7150	.8355
	D ← K	.8704	.7806	.7248	.8639
	E ← B	.7695	.7162	.6864	.7854
	E ← D	.8084	.7406	.6979	.8109
	E ← K	.8889	.8724	.7900	.8970
	K ← B	.7870	.7357	.7025	.8002
	K ← D	.8042	.7501	.7180	.8145
	K ← E	.8794	.8560	.7863	.8785

Table 2 .

 2 Amazon reviews results (prediction accuracy) using neural networks on 5000 dimensions.

			Retrain		No Retrain
	Domains Source	DANN	DAN	CORAL OT 1D OT
	B ← D	.8276 .8382 ±.0041 .8421 ±.0019 .8179 .7200 .8374
	B ← E	.7410 .7845 ±.0194 .8256 ±.0020 .7319 .6912 .8033
	B ← K	.8267 .8361 ±.0049 .8546 ±.0027 .7589 .7222 .8412
	D ← B	.8221 .8353 ±.0021 .8320 ±.0041	.7867 .7381 .8181
	D ← E	.7919 .8073 ±.0119 .8468 ±.0012 .7268 .7081 .8185
	D ← K	.8501 .8666 ±.0057 .8691 ±.0016 .7513 .7169 .8433
	E ← B	.7711 .7743 ±.0078 .8091 ±.0050 .7146 .6860 .7905
	E ← D	.8095 .7987 ±.0050 .8148 ±.0052 .7322 .6943 .8064
	E ← K	.8904 .8853 ±.0057 .8911 ±.0012	.8723 .7991 .8925
	K ← B	.7899 .8022 ±.0019 .7995 ±.0033	.7357 .7034 .7957
	K ← D .8095 .8213 ±.0018 .8259 ±.0016 .7481 .7052 .8139
	K ← E	.8748 .8745 ±.0013 .8749 ±.0010 .8563 .7882 .8744

Table 3 .

 3 PR-AUC scores for domain adaptation models and non adaptative models (annotated by a † mark) on Kaggle Fraud Detection dataset.

			GBDT model
	Retrain	Method	%n	Model1	d	Model2	d
	YES	Train on target † 1 .5604 ±.0316 Train on target † 10 .7332 ±.0191	--	.5646 ±.0361 .7299 ±.0185	--
		Source model † 0	.6712	-	.6625	-
		CORAL NUM 0	.6041	112	.5660	112
		1D OT NUM 0	.6497	112	.6615	112
	NO	1D OT CATE 0	.6986	8	.7011	8
		1D OT	0	.6748	120	.6898	120
		1D OT (ws) 1 .6848 ±.0064 9 ±3 .7075 ±.0089 13 ±4
		1D OT (ws) 10 .7061 ±.0024 36 ±4 .7159 ±.0017 42 ±6
			Neural Network model
	Retrain	Method	%n	Model1	d	Model2	d
		Train on target † 1 .3660 ±.0745	-	.3960 ±.0584	-
	YES	Train on target † 10 .5893 ±.0595 DAN 0 .6489	-120	.5941 ±.0501 .6372	-120
		DANN	0	.6398	120	.6079	120
		Source model † 0	.5912	-	.5990	-
		CORAL	0	.5490	120	.5840	120
		1D OT NUM 0	.5872	112	.6008	112
	NO	1D OT CATE 0	.6218	8	.6288	8
		1D OT	0	.6314	120	.6329	120
		1D OT (

ws) 1 .6232 ±.0178 16 ±6 .6202 ±.0218 15 ±5 1D OT (ws) 10 .6561 ±.0100 40 ±8 .6548 ±.0101 36 ±10

Table 4 .

 4 PR-AUC scores for domain adaptation models and non adaptative models (annotated by a † mark) on the Real Fraud Detection dataset. ws) 1 .2630 ±.0071 8 ±5 .2097 ±.0235 9 ±4 .3830 ±.0107 10 ±5 1D OT (ws) 10 .2697 ±.0043 14 ±2 .2515 ±.0165 14 ±3 .3837 ±.0112 15 ±1 ws) 1 .2511 ±.0163 11 ±4 .2009 ±.0154 10 ±4 .2554 ±.0127 9 ±4 1D OT (ws) 10 .2599 ±.0160 14 ±3 .2100 ±.0181 14 ±3 .2591 ±.0153 14 ±3

				GBDT model
	Retrain	Method	%n	July	d	August	d	September	d
	YES	Train on target † 1 .0441 ±.0348 Train on target † 10 .2554 ±.0683	--	.0170 ±.0126 .0870 ±.0592	--	.0698 ±.0395 .2923 ±.0854	--
		Source model † 0	.2595	-	.1546	-	.3840	-
		CORAL NUM 0	.2296	23	.1709	23	.3245	23
		1D OT NUM 0	.2323	23	.2357	23	.3684	23
	NO	1D OT CATE 0	.2705	8	.1738	8	.3886	8
		1D OT	0	.2383	31	.2199	31	.3695	31
		1D OT (Neural Network model
	Retrain	Method	%n	July	d	August	d	September	d
		Train on target † 1 .0412 ±.0380	-	.0171 ±.0163	-	.0486 ±.0417	-
	YES	Train on target † 10 .2325 ±.0679 DAN 0 .3073	-31	.0918 ±.0456 .2010	-31	.2637 ±.0626 .2881	-31
		DANN	0	.2849	31	.1966	31	.2945	31
		Source model † 0	.2351	-	.1852	-	.2607	-
		CORAL	0	.1548	31	.1796	31	.1039	31
		1D OT NUM 0	.2341	23	.1985	23	.2552	23
	NO	1D OT CATE 0	.2459	8	.1718	8	.2247	8
		1D OT	0	.2392	31	.1965	31	.2371	31
		1D OT (

In the experiment section, we consider few target labels in order to perform model selection.

The number of transactions in fraud detection datasets as the ones used in the experiments of Section 4 is around ten million.

See Sections 3.3 and 3.4 for details.

The supplementary material, the code and data for the first two tasks are available on Github: https://github.com/marrvolo/CDA. Due to confidential reasons, the reallife fraud dataset is not shared.

https://www.kaggle.com/c/ieee-fraud-detection

See supplementary material for the results in the 400 dimensional dataset.

Acknowledgements. This work was partially supported by the Canada CIFAR AI Chair Program.