Didier Fass
email: didier.fass@loria.fr

Putting in perspective human-machine system theory and modeling: from theoretical biology to artifacts integrative design and organization

Keywords: human systems integration, human-machine, theoretical biology, systems theory, isomorphic framework, perspective, modeling

Thinking about human systems integration is thinking human, system and human-system for designing and organizing system of systems from human-machine level to socio-technological level. For critical human in-theloop systems there is a strong need of reliability and consistency from modeling, development and life cycle systems. A main epistemic issue rises: does it exist a conceptual framework, both theoretical and experimental, that ensures reliability and consistency of human system integration design and organization? According to the Italian Renaissance painting perspective principles invention, our paper puts in perspective human systems integrations from theoretical biology to systems sciences, and it presents an isomorphic framework for modeling human systems integration especially adapted at the human machine level, for medicine, defense and aerospace.

Introduction

"The field of Human Factors and its many descendants -Cognitive Engineering, Human-Computer Interaction, Cognitive Ergonomics, Human-Systems Integration, ...-has made numerous, wonderful advances in the many decades since the enterprise began. But the discipline still serves many to rescue rather than to create. It is time for a change." Don Norman [START_REF] Roco | Converging technologies for improving human performancenanotechnology, biotechnology, information technology and cognitive science[END_REF] Reliable design and correctness by construction systems are two main issues for human systems integration and organization from human-machine systems to sociotechnical systems especially for safety and life critical systems. With current interactive systems, from smartphone, airplane cockpit devices and bedside monitor in intensive care, to teleoperation systems, boundaries between human and artifact are fading. Within converging technologies (nano-bio-info-cogno or NBIC) [START_REF] Nordmann | Converging technologies -Shaping the future of european societies[END_REF] [3] that dynamics develops. That disappearance of boundaries between a biological and social human and its interactive physical and information processing artifacts challenges engineering methodologies and ergonomics of systems design.

Current and future technical developments for enhancing human skills and capabilities or medical care and implantable devices challenge new scientific and technical knowledge and development methods. Understanding that synthetic hybridization requires an original conceptual and knowledge framework, that allows to think and model "enhanced or augmented human" as an integrated dynamic, structural and functional whole [START_REF] Norman | Why Human Systems Integration Fails (And Why the University Is the Problem)[END_REF].

Human system integration (HIS)

Originally as technical and managerial concept [START_REF] Haskins | Systems Engineering Handbook: a guide for processes and activities[END_REF], human systems integration (HIS) was defined in the middle of the eighties by the US defense department. It is used in acquisition programs requirements definition of total system design and organization. It aims to maximize the overall system performance while ensuring a safe, efficient, and enhanced interaction between the user and the technical system [START_REF]Defense Acquisition Guidebook[END_REF]. Defining a system more broadly than hardware and software refer to human centered design [START_REF] Ehrahart | Handbook of human systems integration, chapter User-centrerd systems engineering framework[END_REF] in contrast with automation and machine centered design [START_REF] Amalberti | Les facteurs humains à l'aube de l'an[END_REF].

That methodology [START_REF]Human-System Integration in the System Development Process: A New Look[END_REF] is concerned with the integration of human capabilities and performances, from individual to social level [START_REF] Rousse | Organizational Simulation[END_REF] into the design of complex humanmachine systems supporting safe, efficient operations; there is also the question of reliability. That issue requires thinking human as an element of the system and translating it qualitatively throughout design, development and testing process [START_REF] Booher | Handbook of human systems integration, Introduction: Human Systems Integration[END_REF].

Human systems integration also involves augmented human design with the objectives of enhancing human capabilities and improving human performance [START_REF] Engelbart | Augmenting human intellect: a conceptual framework[END_REF] using interactive technologies at the level of human-machine system and human machine symbiosis [START_REF] Licklider | Man-Computer Symbiosis[END_REF].

Today HIS refers to systems that require human interactions -human in-the-loop systems, but new automated technologies are emerging more and more integrated on the human body from wearable to implementable. The human automated machine is closer. The concept of human system integration must be revised!

Scientific and technical context

Human machine is currently both a techno-scientific research and development topic and a philosophical and anthropologic theme of discussion. From one side, reductionism postulates reducing the human organism to an intelligent machine and its physical (mechanical) and computational properties. On another side, some one claims for a metaphysical and transcendental humanistic ideal inherited from Italian Renaissance and Vitruvius.

Between Human, with a capital H, as a philosophical ideal and human as an abstract category of a biological system, there is life, multidimensional reality and death. Therefore, how understanding and conceiving human and human-artifact or machine nature and their scientific principles theoretically? That question highlights some scientific and technological interdisciplinary questions:

-What does human systems integration really mean from systems sciences or general systems theory to theoretical biology and integrative physiology applied to human systems engineering? -What is a good epistemic framework for human-machines modeling? Which system and theory of knowledge is relevant? Which ethical reasoning? Which logics? -What is the validated scientific grounding for safety critical automation design and human systems integration? -What is a good and reliable model of automation and integrated human machine "physiology" and behavior? -Which are the formal and experimental method for ensuring modeling, validation and certification of human-machine system design and organization?

Epistemology and modeling

Epistemology and modeling are causally linked. The epistemic framework structures model. They are related to knowing and representing knowledge, not only for understanding the natural or artificial world, but also for designing and organizing technologies. According its internal -logic, and external -experimental, validity that framework ensure consistency and practical validity of the model. Different epistemic frameworks might provide different models of the same object or system with a wide range of robustness and predictability. The most general is the grounding epistemic framework; the most predictable and robust is the model. It is not a metaphysical contingency but a realistic and naturalistic necessity. It is a main issue for safety and sustainability of automation design and human system integration.

Historical perspective

The way we think and conceptualize the world and the relation between its elements within its related level of organization influences our capabilities of representation, modeling, designing and organizing artifacts from human-machine to socio-technical systems. HIS safety and predictive modeling and design need a new insight and an adapted conceptual framework.

We need a shift from an analytical and reductionist framework, based on mechanism and linear causality in witch human machine design is reduced to interactions design as an informational and computational processing to a systemic and organismic conceptual framework based on theoretical biology and general system theory. The general problem of human systems integration is not recent. In 1415 for helping other people being aware of the artificial perspective principles of representation as he was, Filippo Brunelleschi, a self-taught architect and certainly the central perspective inventor, made-up a special device, "la tavoletta", (Fig. 1.). The Tavoletta is the combination by two technical parts: a painted tablet and a lookingglass. The tablet is painted on its intrados with the Duomo Baptistery realistic representation according perspective principles of drawing (central point of view, skylines and converging lines). Holding the tablet and the mirror, the user was looking on the virtual reflected image trough the tablet opening trying to superimpose the virtual image on the real monument. Brunelleschi's Tavoletta is the ancestor of virtual reality and augmented reality.

The HSI founding experiment: "La tavoletta di Brunelleschi"

It summarizes the modern aims of human system integration design and organization. The success of that experience depends on: i. Designer skills for conceiving relevant abstraction of a part of reality and developing an artificial representation using artifice; ii. Formal and experimental representational medium; iii. Device shaping in relation to the required function, its design; iv. The acknowledgement of usage context or operating context; v. Physical ergonomics of the device, its ability to induce and facilitate its handling situation (without injury); vi. The ability of the device to stimulate cognitive, imaginative and action capabilities of an operator (affordance [START_REF] Gibson | The theory of affordance[END_REF])… who must understand and operate the device to realize the experience; vii. Skills and training of the user.

Cybernetics and human machine systems

Cybernetics, defined by Wiener [START_REF] Wiener | [END_REF] as "the science of control and communication in the animal and the machine", had and has a great influence on automation design and human-machine systems concepts and development. It deals with information theory, automatic control theory, algorithm theory, regulation, stability, and homeostasis. Cybernetics is about regulation and control of a mechanical system behavior [START_REF] Parin | Introduction to medical cybernetics, Translation of "Vvedeniye v meditsinskuyu kibernetiku ."Izdatel'stvo "Meditsina[END_REF] and human-machine problem have been viewed as an exchange of information between the operator and the controlled object. It is concerned with the processing by a decision-making algorithm of input information into control signals, a command [START_REF] Rosenblueth | Purpose and Teleology[END_REF], this independently of the nature of the machine (biological, mechanical, electronic...) [START_REF] Ashby | An introduction to cybernetics[END_REF]. In that context, every good regulator of system must be a model of that system or must be isomorphic with the system being regulated [START_REF] Conant | Every good regulator of a system must be a model of that system[END_REF]. Despite this theorem, cybernetics remains behaviorist and computational, i.e., postulating that information processing and computing are fundamental basis of decision-making function or knowledge the same as cognitive. But human as biological system, is not a computational or state machine [START_REF] Ková | Inforamtion and knowledge in biology : time for reappraisal[END_REF].

Theoretical biology and general systems theory

Designing and developing human machines systems using interactive and artificial technologies requires integrating artificial elements and structural design usually by artificial or artifactual functional interactions and its dynamics.

In this scientific framework, the question becomes: how to integrate the technical and human needs and requirements, biological peculiarities, into specifications of a technological system (physical and informational) design able to be used by a human (biological system) or integrated or coupled to the human body? Requiring that design and organization might ensure stability and consistency of the overall system (integrated human machine system) function and behavior in space and time?

Behind this in mind, it is necessary to develop theoretical principles of human systems integration, based on a continuous approach between biology and anthropology [START_REF] Wiener | [END_REF] [16] [START_REF] Rosenblueth | Purpose and Teleology[END_REF], taking into account the isomorphic and proven principles of general systems theory [START_REF] Ashby | An introduction to cybernetics[END_REF], and of theoretical biology and integrative physiology theory [START_REF] Conant | Every good regulator of a system must be a model of that system[END_REF].

Human nature cannot be reduced to a metaphoric "model" of any kind of machine or computation even it is heuristic. Engineered artifacts have their own technical and physical requirement. The question of nature of human-machine systems is an issue of integrative design and organization.

Human system integration and modeling

"Experience without theory is blind, but theory without experience is mere intellectual play." Emmanuel Kant. According that kant's sentence we have developed a Fig. 2 Our approach associates formal and experimental methods for validating humanmachine model consistency. It is first to state an multidisciplinary epistemological framework after analyzing existing multidisciplinary concepts and validate their relevance using model checking and realistic case study; secondly to validate the relevance of this epistemological framework and its ability to generate a safe and integrated modeling method, validating overhang the intrinsic quality of formal models and extrinsic validity by simulation and experimentally by comparison to reality by expert analysis and expert feedback.

HIS needs the production of a new body of knowledge and a general and reliable framework for designing, i.e., theoretical principles proven and validated description or modeling of human machine system. The purpose of the production of this new epistemological apparatus is to provide a scientific and technical framework for predictive integrative and safe modeling of human-machine systems. The challenge is to prefigure or provide a tool for designing and organizing an hybrid system from which nature is to be defined.

A theoretical framework

"The ultimate model of a cat is of course another cat, whether it be born of still another cat or synthetized in laboratory" Arturo Rosenblueth, Norbert Wiener and Julian Bigelow, January 1943. Fig. 3 Challenging human-machine system design and organization is modeling an heterogeneous system of systems (different by nature). That requires a proven and validate epistemic framework fitted to hybrid system, challenging the question of human machine system nature and ensuring human systems integration reliability. Fig. 4 Our isomorphic epistemic framework for human-machine systems integrative design and organization.

Classical epistemic framework

From General systems theory and Cybernetics, some previous works in systems sciences and modeling have demonstrated the relation between system theory, modeling and epistemology. Some attempt to define invariant category conceptual element of general system have done, i.e., Pierre Delattre have done an epistemic analysis showing tree main categories of systems invariance: structure, function and evolution [START_REF] Delattre | Système, structure, fonction, évolution -Essai d'analyse systémique[END_REF]. Previously, according system engineering and classical system epistemology, we have proposed to ground our modeling method of human-machine system on the concepts of structure, function and dynamics. We have defined the relation of three pair of invariant as Architecture{structure, function}; Behavior{Function, Evoution} and Evolution{Structure, Dynamics}. We have considered these three relation as three plane of an Euclidian space [START_REF] Lieber | Human Systems Integration Design: Which Generalized Rationale[END_REF], were each invariant was a structuring axis for a system model. Nevertheless that epistemic framework of invariants was a mistake because structure and architecture are equal and function, as an issue of purpose and teleology, is not realy existing per se, it is related to a structural shape (a Gestalt) and the dynamic of the system. By consequences we are suggestion a new epistemic framework for modeling human-machine systems.

Our isomorphic epistemic framework

For modeling human-machine systems, we have grounded our new epistemic framework on isomorphism. We have found new general categories of system elements that allow the same representation framework for integrating two systems different by nature. Our isomorphic epistemic framework is composed by three main isomorphic categories of interlocked elements: structural element, shape and dynamic.

As previously we were able to define three pair of isomorphic relation: Architecture{structural elements, shape}, Behavior{shape, dynamics} and Evolution{structural elements, dynamics}. Thus architecture is describable by a set of possible geometries, from Euclidian to no-Euclidian and other, behavior is describable by a set of functional analysis and algorithm, and evolution is describable by a set of modal interactions where each interaction might be compose on three modal parameters: physical, logical and physiological or behavioral dimensions according to Chauvet's theoretical integrative physiology [START_REF] Chauvet | Hierarchical functional organization of formal biological systems: a dynamical approach. I, II and III[END_REF]. It has been experimentally validated [START_REF] Fass | Augmented human engineering: a theoretical and experimental approach to human system integration[END_REF].

Conclusion and perspective

Just like the drawing of perspective, where the correctness construction is formally ensure by structuring lines and point of view principles, human-machine system modeling must be ensure by an isomorphic framework of epistemic principal proven and validated experimentally and formally. It will be a necessary condition to the future development of human-machines systems. But it is not sufficient, future development needs also intuition, how-know, expertise and ethics.

Fig. 1 .

 1 Fig. 1. Performed in the early Italian Renaissance (1415) in Florence, Filippo Brunelleschi's Tavoletta experience is the founding experiment for human systems integration and augmented reality. It demonstrated the geometrical framework of perspective conceptualization and representation.


Ilyes Jenhani Larodec
email: ilyes.j@lycos.com

Salem Benferhat
email: benferhat@cril.univ-artois.fr

Zied Elouedi
email: zied.elouedi@gmx.fr

Properties Analysis of Inconsistency-based Possibilistic Similarity Measures

Keywords: Possibility theory, Similarity, Inconsistency

This paper deals with the problem of measuring the similarity degree between two normalized possibility distributions encoding preferences or uncertain knowledge. Many existing denitions of possibilistic similarity indexes aggregate pairwise distances between each situation in possibility distributions. This paper goes one step further, and discusses denitions of possibilistic similarity measures that include inconsistency degrees between possibility distributions. In particular, we propose a postulate-based analysis of similarity indexes which extends the basic ones that have been recently proposed in a literature.

Introduction

Uncertainty and imprecision are often inherent in modeling knowledge for most real-world problems (e.g. military applications, medical diagnosis, risk analysis, group consensus opinion, etc.). Uncertainty about values of given variables (e.g. the type of a detected aerial object, the temperature of a patient, the property_value of a client asking for a loan, etc.) can result from some errors and hence from non-reliability (in the case of experimental measures) or from dierent background knowledge (in the cognitive case of agents: doctors, etc.). As a consequence, it is possible to obtain dierent uncertain pieces of information about a given value from dierent sources. Obviously, comparing these pieces of information could be of a great interest in decision making, in case-based reasoning, in performing clustering from data having some imprecise attribute values, etc.

Comparing pieces of uncertain information given by several sources has attracted a lot of attention for a long time. For instance, we can mention the well-known Euclidean and KL-divergence [START_REF] Kullback | On information and suciency[END_REF] for comparing probability distributions. Another distance has been proposed by Chan et al. [START_REF] Chan | A distance measure for bounding probabilistic belief change[END_REF] for bounding probabilistic belief change. Moving to belief function theory [START_REF] Shafer | A mathematical theory of evidence[END_REF], several distance measures between bodies of evidence deserve to be mentioned. Some distances have been proposed as measures of performance (MOP) of identication algorithms [START_REF] Fixsen | The modied Dempster-Shafer approach to classication[END_REF] [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF]. Another distance was used for the optimization of the parameters of a belief k -nearest neighbor classier [START_REF] Zouhal | An evidence-theoric k-NN rule with paprameter optimization[END_REF]. In [START_REF] Tessem | Approximations for ecient computation in the theory of evidence[END_REF], the authors proposed a distance for the quantication of errors resulting from basic probability assignment approximations.

Many contributions on measures of similarity between two given fuzzy sets have already been made [START_REF] Bouchon-Meunier | Towards general measures of comparison of objects[END_REF] [3] [6] [START_REF] Wang | A comparative study of similarity measures[END_REF]. For instance, in the work by Bouchon-Meunier et al. [START_REF] Bouchon-Meunier | Towards general measures of comparison of objects[END_REF], the authors proposed a similarity measure between fuzzy sets as an extension of Tversky's model on crisp sets [START_REF] Tversky | Features of similarity[END_REF]. The measure was then used to develop an image search engine. In [START_REF] Wang | A comparative study of similarity measures[END_REF], the authors have made a comparison between existing classical similarity measures for fuzzy sets and proposed the sameness degree which is based on fuzzy subsethood and implication operators. Moreover, in [START_REF] Baets | Transitivity preserving fuzzication schemes for cardinality-based similarity measures[END_REF] and [START_REF] Fono | Fuzzy implication operators for dierence operations for fuzzy sets and cardinality-based measures of comparison[END_REF], the authors have proposed many fuzzy distance measures which are fuzzy versions of classical cardinality-based distances. This paper deals with the problem of dening similarity measures between normalized possibility distributions. In [START_REF] Jenhani | Information Anity: a new similarity measure for possibilistic uncertain information[END_REF], a basic set of properties, that any possibilistic similarity measure should satisfy, has been proposed. This set of natural properties is too minimal and is satised by most existing indexes. Moreover, they do not take into account the inconsistency degree between possibility distributions. In this paper, we will mainly focus on revising and extending these properties to highlight the introduction of inconsistency in measuring possibilistic similarity.

In fact, inconsistency should be considered when measuring similarity as shown by this example: Suppose that a conference chair has to select the best paper among three selected best papers (p 1 , p 2 , p 3 ) to give an award to its authors. The conference chair decides to make a second reviewing and asks two referees r 1 and r 2 to give their preferences about the papers which, in fact, will be represented in the form of possibility distributions. Let us consider these two situations: Situation 1: The referee r 1 expresses his full satisfaction for p 3 and fully rejects p 1 and p 2 (i.e. π 1 (p 1 ) = 0, π 1 (p 2 ) = 0, π 1 (p 3 ) = 1) whereas r 2 expresses his full satisfaction for p 2 and fully rejects p 1 and p 3 (i.e. π 2 (p 1 ) = 0, π 2 (p 2 ) =1, π 2 (p 3 ) = 0). Clearly, p 1 will be rejected but the chair cannot make a decision that fully ts referees' preferences.

(p 1 ) = 1, π ′ 2 (p 2 ) = 1, π ′ 2 (p 3 ) = 0).
In this case, the chair can make a decision that satises both reviewers since they agree that p 1 is a good paper.

The above example shows that, in some situ-ations, distance alone is not sucient to make a decision since the expressed preferences in both situations have the same distance. In fact, if we consider the well-known Manhattan distance (M(x,y)=

1 n n i=1 |x i -y i |), we obtain M(π 1 , π 2 )=M(π ′ 1 , π ′
2 )=2/3. Hence, we should consider an additional concept, namely, the inconsistency degree which will play a crucial role in measuring similarity between any given two possibility distributions.

The rest of the paper is organized as follows. Section 2 gives necessary background on possibility theory. Section 3 presents the six proposed basic properties that a similarity measure should satisfy. Section 4 proposes new additional properties that take into account the inconsistency degrees. Section 5 gives some derived propositions from the proposed properties. Section 6 suggests a similarity measure that generalizes the one presented in [START_REF] Jenhani | Information Anity: a new similarity measure for possibilistic uncertain information[END_REF]. Finally, Section 7 concludes the paper.

Possibility Theory

Possibility theory represents a non-classical uncertainty theory, rst introduced by Zadeh [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF] and then developed by several authors (e.g., Dubois and Prade [START_REF] Dubois | Possibility theory: An approach to computerized processing of uncertainty[END_REF]). In this section, we will give a brief recalling on possibility theory.

Possibility distribution

Given a universe of discourse Ω = {ω 1 , ω 2 , ..., ω n }, one of the fundamental concepts of possibility theory is the notion of possibility distribution denoted by π. π corresponds to a function which associates to each element ω i from the universe of discourse Ω a value from a bounded and linearly ordered valuation set (L,<). This value is called a possibility degree: it encodes our knowledge on the real world. Note that, in possibility theory, the scale can be numerical (e.g. L=[0,1]): in this case we have numerical possibility degrees from the interval [0,1] and hence we are dealing with the quantitative setting of the theory. In the qualitative setting, it is the ordering between the dierent possible values that is important. By convention, π(ω i ) = 1 means that it is fully possible that ω i is the real world, π(ω i ) = 0 means that ω i cannot be the real world (is impossible). Flexibility is modeled by allowing to give a possibility degree from ]0,1[. In possibility theory, extreme cases of knowledge are given by:

-Complete knowledge: ∃ω i , π(ω i ) = 1 and ∀ ω j = ω i , π(ω j ) = 0.
-Total ignorance:

∀ ω i ∈ Ω, π(ω i ) = 1 (all values in Ω are possible).

Possibility and Necessity measures

From a possibility distribution, two dual measures can be derived: Possibility and Necessity measures. Given a possibility distribution π on the universe of discourse Ω, the corresponding possibility and necessity measures of any event A ⊆ 2 Ω are, respectively, determined by the formulas: Π(A) = max ω∈A π(ω) and

N (A) = min ω / ∈A (1-π(ω)) = 1-Π(A). Π(A)
evaluates at which level A is consistent with our knowledge represented by π while N (A) evaluates at which level A is certainly implied by our knowledge represented by π.

Normalization

A possibility distribution π is said to be normalized if there exists at least one state ω i ∈ Ω which is totally possible (i.e. max ω∈Ω {π(ω)} = π(ω i )=1). Otherwise, π is considered as sub-normalized and in this case

Inc(π) = 1 -max ω∈Ω {π(ω)} (1)
is called the inconsistency degree of π. It is clear that, for normalized π, max ω∈Ω {π(ω)} = 1, hence Inc(π)=0. The measure Inc is very useful in assessing the degree of conict between two distributions π 1 and π 2 which is given by Inc(π 1 ∧ π 2 ). For sake of simplicity, we take the minimum and product conjunctive (∧) operators. Obviously, when π 1 ∧π 2 gives a sub-normalized possibility distribution, it indicates that there is a conict between π 1 and π 2 (Inc(π 1 ∧ π 2 ) ∈]0, 1]). On the other hand, when π 1 ∧π 2 is normalized, there is no conict and hence Inc(π 1 ∧ π 2 ) = 0.

Non-specicity

Possibility theory is driven by the principle of minimum specicity: A possibility distribution π 1 is said to be more specic than π 2 if and only if for each state of aairs ω i ∈ Ω, π 1 (ω i ) ≤ π 2 (ω i ) [START_REF] Yager | On the specicity of a possibility distribution[END_REF]. Clearly, the more specic π, the more informative it is.

Given a permutation of the degrees of a pos-

sibility distribution π = π (1) , π (2) , ..., π (n) such that π (1) ≥ π (2) ≥ ... ≥ π (n)
, the nonspecicity of a possibility distribution π, socalled U-uncertainty is given by:

U (π) = n i=2 (π (i) -π (i+1) ) log 2 i + (1 -π (1) ) log 2 n.
For the sake of simplicity, for the rest of the paper, a possibility distribution π on a nite set Ω = {ω 1 , ω 2 , ..., ω n } will be denoted by

π[π(ω 1 ), π(ω 2 ), ..., π(ω n )].
3 Basic properties of a possibilistic similarity measure

The issue of comparing possibility distributions has been studied in several works. More recently, a set of basic properties has been proposed in [START_REF] Jenhani | Information Anity: a new similarity measure for possibilistic uncertain information[END_REF]. In this section, we will briey recall and slightly revise these properties. Note that in this paper, we only deal with normalized possibility distributions.

Let π 1 and π 2 be two possibility distributions on the same universe of discourse Ω.

A possibilistic similarity measure, denoted by s(π 1 , π 2 ), should satisfy:

Property 1. Non-negativity s(π 1 , π 2 ) ≥ 0. Property 2. Symmetry s(π 1 , π 2 ) = s(π 2 , π 1 ). Property 3.
Upper bound and Nondegeneracy

∀ π i , s(π i , π i ) = 1.
Namely, identity implies full similarity. This property is weaker than the one presented in [START_REF] Jenhani | Information Anity: a new similarity measure for possibilistic uncertain information[END_REF] which also requires the converse, namely, s(π i , π j )=1 i π i = π j .

Property 4. Lower bound

If ∀ω i ∈ Ω, i) π 1 (ω i ) ∈ {0, 1} and π 2 (ω i ) ∈ {0, 1}, ii) and π 2 (ω i ) = 1 -π 1 (ω i ) then, s(π 1 , π 2 )=0.
Namely, s(π 1 , π 2 ) = 0 should be obtained only when we have to compare maximally contradictory possibility distributions. Item i) means that π 1 and π 2 should be binary and since we deal with normalized possibility distributions, items i) and ii) imply:

iii) ∃ ω q ∈ Ω s.t. π 1 (ω q ) = 1 iv) ∃ ω p ∈ Ω s.t. π 1 (ω p ) = 0
Property 5. Large inclusion (specicity)

If ∀ω i ∈ Ω, π 1 (ω i ) ≤ π 2 (ω i ) and π 2 (ω i ) ≤ π 3 (ω i ),
which by denition means that π 1 is more specic than π 2 which is in turn more specic than π 3 , we obtain: s(π 1 , π 2 )≥s(π 1 , π 3 ).

Property 6. Permutation

Let π 1 , π 2 , π 3 and π 4 be four possibility distributions such that s(π 1 , π 2 )>s(π 3 , π 4 ). Suppose that ∀j = 1..4, and ω p , ω q ∈ Ω, we have π ′ j (ω p ) = π j (ω q ), π ′ j (ω q ) = π j (ω p ) and ∀ω r = ω p , ω q , π ′ j (ω r ) = π j (ω r ). Then,

s(π ′ 1 , π ′ 2 )>s(π ′ 3 , π ′ 4 ).
These six properties can be viewed as basic properties of any possibilistic similarity measure. They are satised by the following similarity measures:

Manhattan Distance:

S M (π 1 , π 2 ) = 1 - n i=1 (|π 1 (ω i )-π 2 (ω i )|) n
Euclidean Distance:

S E (π 1 , π 2 ) = 1 - n i=1 (π 1 (ω i )-π 2 (ω i )) 2 n
Clearly, the above properties do not take into account the amount of conict between possibility distributions. In fact, if we consider again our example of the introduction, where

π 1 =[0 0 1], π 2 =[0 1 0], π ′ 1 =[1 0 1] and π ′ 2 =[1 1 0], then S M (π 1 , π 2 )=S M (π ′ 1 , π ′ 2 )=0.33, S E (π 1 , π 2 )=S E (π ′ 1 , π ′ 2 )=0.18.
To overcome this drawback, we will enrich the proposed properties by some additional ones.

Additional possibilistic similarity properties

The rst extension concerns Property 5, where we consider a particular case of strict similarity in case of strict inclusion: Property 7. Strict inclusion

∀π 1 , π 2 , π 3 s.t. π 1 = π 2 = π 3 , if π 1 ≤ π 2 ≤ π 3 , then s(π 1 , π 2 ) > s(π 1 , π 3 ).
Note that π 1 = π 2 and π 1 ≤ π 2 implies π 1 < π 2 (strict specicity).

Next property says that, giving two possibility distributions π 1 and π 2 , enhancing the degree of a given situation (with the same value) results in an increasing of the similarity between the two distributions. The similarity will be even larger, if the enhancement leads to a decrease of the amount of conict. More precisely:

Property 8. Degree Enhancement

Let π 1 and π 2 be two possibility distributions.

Let

ω i ∈ Ω. Let π ′ 1 and π ′ 2 s.t.: i) ∀j = i, π ′ 1 (ω j ) = π 1 (ω j ) and π ′ 2 (ω j ) = π 2 (ω j ), ii) Let α s.t. α ≤ 1 -max(π 1 (ω i ), π 2 (ω i )). If π ′ 1 (ω i ) = π 1 (ω i )+α and π ′ 2 (ω i ) = π 2 (ω i )+α,
then:

• If Inc(π 1 ∧ π 2 )=Inc(π ′ 1 ∧ π ′ 2 ), then s(π 1 , π 2 ) = s(π ′ 1 , π ′ 2 ). • If Inc(π ′ 1 ∧ π ′ 2 )<Inc(π 1 ∧ π 2 ), then s(π ′ 1 , π ′ 2 ) > s(π 1 , π 2 ).
The intuition behind the two below properties is the following: consider two experts who provide possibility distributions π 1 and π 2 . Assume that there exists a situation ω where they disagree. Now, assume that the second expert changes its mind and sets π 2 (ω) to be equal to π 1 (ω). Then the new similarity between π 1 and π 2 increases. This is the aim of Property 9. Property 10, goes one step further and concerns the situation when the new degree of π 2 (ω) becomes closer to π 1 (ω).

Property 9. Mutual convergence

Let π 1 and π 2 be two possibility distributions s.t. for some ω i , we have

π 1 (ω i ) = π 2 (ω i ). Let π ′ 2 s.t.: i) π ′ 2 (ω i ) = π 1 (ω i ), ii) and ∀j = i, π ′ 2 (ω j ) = π 2 (ω j )
Hence, we obtain:

s(π 1 , π ′ 2 ) > s(π 1 , π 2 ).

Property 10. Generalized mutual convergence

Let π 1 and π 2 be two possibility distributions s.t. for some ω i , we have

π 1 (ω i ) > π 2 (ω i ). Let π ′ 2 s.t.: i) π ′ 2 (ω i ) ∈]π 2 (ω i ), π 1 (ω i )], 176 Proceedings of IPMU'08 ii) and ∀j = i, π ′ 2 (ω j ) = π 2 (ω j )
Hence, we obtain:

s(π 1 , π ′ 2 ) > s(π 1 , π 2 ).
Property 11 means that if one starts with a possibility distribution π 1 , and modify it by decreasing (resp. increasing) only one situation ω i (leading to π 2 ), or starts with a same distribution π 1 and only modify, identically, another situation ω k (leading to π 3 ), then the similarity degree between π 1 and π 2 is the same as between π 1 and π 3 .

Property 11. Indierence preserving

Let π 1 be a possibility distribution and α a positive number. Let

π 2 s.t. π 2 (ω i ) = π 1 (ω i )- α (resp. π 2 (ω i ) = π 1 (ω i ) + α ) and ∀j = i, π 2 (ω j ) = π 1 (ω j ). Let π 3 s.t. for k = i, π 3 (ω k ) = π 1 (ω k ) -α (resp. π 3 (ω k ) = π 1 (ω k ) + α) and ∀j = k, π 3 (ω j ) = π 1 (ω j ), Then: s(π 1 , π 2 )=s(π 1 , π 3 ).
Property 12 says that, if we consider two possibility distributions π 1 and π 2 . If we increase (resp. decrease) one situation ω p of π 1 with a degree α (leading to π ′ 1 ) and, similarly, increase (resp. decrease) one situation ω q but this time of π 2 with the same degree α (leading to π ′ 2 ), then the similarity degree between π 1 and π ′ 1 will be equal to the one between π 2 and π ′ 2 .

Property 12. Maintaining similarity

Let π 1 and π 2 be two possibility distributions.

Let π ′ 1 and π ′ 2 s.t. i) ∀j = p, π ′ 1 (ω j ) = π 1 (ω j ) and π ′ 1 (ω p ) = π 1 (ω p ) + α (resp. π ′ 1 (ω p ) = π 1 (ω p ) -α ). ii) ∀j = q, π ′ 2 (ω j ) = π 2 (ω j ) and π ′ 2 (ω q ) = π 2 (ω q ) + α (resp. π ′ 2 (ω q ) = π 2 (ω q ) -α).
Then: s(π 1 , π ′ 1 )=s(π 2 , π ′ 2 ).

Derived propositions

In what follows, we will derive some propositions from the above dened properties that should characterize any possibilistic similarity measure. A consequence of Property 7 is that only identity between two distributions imply full similarity, namely: Proposition 1 Let s a possibilistic similarity measure s.t. s satises Properties 1-12. Then, ∀π i , π j , s(π i , π j )=1 i π i =π j .

This also means that:

∀π j = π i , s(π i , π i ) > s(π i , π j ).
Besides, only completely contradictory possibility distributions imply a similarity degree equal to 0: Proposition 2 Let s a possibilistic similarity measure s.t. s satises Properties 1-12. Then,

∀π i , π j , s(π i , π j )=0 i ∀ω i ∈ Ω, i) π 1 (ω i ) ∈ {0, 1} and π 2 (ω i ) ∈ {0, 1}, ii) and π 2 (ω i ) = 1 -π 1 (ω i )
As a consequence of Property 8, discounting the possibility degree of a same situation leads to a decrease of similarity: Proposition 3 Let s a possibilistic similarity measure satisfying Properties 1-12. Let π 1 and π 2 be two possibility distributions.

Let ω i ∈ Ω. Let π ′ 1 and π ′ 2 s.t.: i) ∀j = i, π ′ 1 (ω j ) = π 1 (ω j ) and π ′ 2 (ω j ) = π 2 (ω j ), ii) Let β s.t. β ≤ min(π 1 (ω i ), π 2 (ω i )). If π ′ 1 (ω i ) = π 1 (ω i )-β and π ′ 2 (ω i ) = π 2 (ω i )-β.
Then:

If Inc(π 1 ∧ π 2 )=Inc(π ′ 1 ∧ π ′ 2 ), then s(π 1 , π 2 ) = s(π ′ 1 , π ′ 2 ). If Inc(π 1 ∧π 2 )<Inc(π ′ 1 ∧π ′ 2 ), then s(π 1 ∧π 2 ) > s(π ′ 1 ∧ π ′ 2 ).
As a consequence of Property 9 and Property 10, starting from a possibility distribution π 1 , we can dene a set of possibility distributions that, gradually, converge to the most similar possibility distribution to π 1 : Proposition 4 Let s a possibilistic similarity measure satisfying Properties 1-12. Let π 1 and π 2 be two possibility distributions s.t. for some

ω i , π 1 (ω i ) > π 2 (ω i ). Let π k (k=3..n) be a set of n possibility distributions. Each π k is derived in step k from π k-1 as follows: i) π k (ω i ) = π k-1 (ω i ) + α with α ∈]0, π 1 (ω i ) -π k-1 (ω i )] ii) and ∀j = i, π k (ω j ) = π k-1 (ω j ) Hence, we obtain s(π 1 , π 2 ) < s(π 1 , π 3 ) < s(π 1 , π 4 ) < ... < s(π 1 , π n ) ≤ 1.
Proceedings of IPMU'08

6 An example of a similarity measure This section proposes to analyze an extension of the Information Anity measure, recently proposed in [START_REF] Jenhani | Information Anity: a new similarity measure for possibilistic uncertain information[END_REF] and denoted Inf oAf f . Let us recall that Inf oAf f takes into account the Manhattan distance (M(π 1 , π 2 ) =

1 n n i=1 |π 1 (ω i ) -π 2 (ω i )|)
, along with the well known inconsistency measure. By extension, we mean that we do not restrict ourselves to the Manhattan distance, but we can also consider the Euclidean distance (E(π

1 , π 2 ) = n i=1 (π 1 (ω i )-π 2 (ω i )) 2 n
). Moreover, for the Inconsistency measure (Equation( 1)), we can also take either the minimum or the product conjunctive operators.

Denition 1 Let π 1 and π 2 be two possibility distributions on the same universe of discourse Ω. We dene a measure GA(π 1 , π 2 ) as follows:

GAf f (π1, π2) = 1 - κ * d(π1, π2) + λ * Inc(π1 ∧ π2) κ + λ
where κ>0 and λ>0. d represents a (Manhattan or Euclidean) normalized metric distance between π 1 and π 2 . Inc(π 1 ∧ π 2 ) is the inconsistency degree between the two distributions (see Equation ( 1)) where ∧ is taken as the product or min operators.

Proposition 5 The GAf f measure satises all the proposed properties.

Example 1 Let us give an example to explain the proposed properties. For this example, we will take d as the Manhattan distance, ∧ as the minimum conjunctive operator and

κ = λ = 1. Property 7. Strict inclusion Let π 1 [0.3,0.3,1],π 2 [0.6,0.3,1] and π 3 [1,0.3,1]. Clearly π 1 ≤ π 2 ≤ π 3 and π 1 (ω 1 ) < π 2 (ω 1 ) < π 3 (ω 1 ) ⇒ GAf f (π 1 , π 2 ) = 0.95 > GAf f (π 1 , π 3 ) = 0.
=[0 0 1], π 2 =[0 1 0], π ′ 1 =[1 0 1] and π ′ 2 =[1 1 0]. If we ap- ply GA, we obtain: GA(π 1 ,π 2 )=0.16 < GA(π ′ 1 ,π ′ 2 )=0.66 7

Conclusion

This paper revised and extended recently proposed properties [START_REF] Jenhani | Information Anity: a new similarity measure for possibilistic uncertain information[END_REF] that a similarity measure between possibility distributions should satisfy. Although the Manhattan and Euclidean distances satisfy all the six basic properties, they do not satisfy the new extended ones (as shown by the example at the end of Section 3). Moreover, we have proposed a measure, namely, the Generalized Anity function which satises all the axioms. We argue that the proposed measure is useful in many applications where uncertainty is represented by possibility distributions e.g. similaritybased possibilistic decision trees [START_REF] Jenhani | Sim-PDT: a similaritybased possibilistic decision tree approach[END_REF]. We can also mention the possibilistic clustering problem [START_REF] Krishnapuram | A possibilistic approach to clustering[END_REF] which generally uses fuzzy similarity measures.

Appendix A. Proofs

For lack of space, we only provide the proof of One direction is evident since π i =π j ⇒ GA(π i , π j )=1 (Property 3). Now, suppose that GA(π i , π j )=1 and π i = π j . GA(π i , π j )=1 ⇒ d(π i , π j )=0 AND Inc(π i ∧ π j )=0 (since we deal with normalized distributions) ⇒ π i =π j (contradiction with the assumption). Hence, GA(π i , π j )=1 i π i =π j .

Proposition 2:

One direction is evident since π 1 =1-π 2 (with π 1 and π 2 are binary normalized possibility distributions) ⇒ GA(π 1 , π 2 )=0 (Property 4). Now, suppose that: i) GA(π 1 , π 2 )=0 and ii)π 1 = 1π 2 and iii)π 1 and π 2 are not binary. GA(π 1 , π 2 )=0 ⇒ κ * d(π 1 ,π 2 )+λ * Inc(π

1 ∧π 2 ) κ+λ =1 ⇒ κ * d(π 1 , π 2 ) + λ * Inc(π 1 ∧ π 2 ) = κ + λ.
Since, κ>0, λ>0 ⇒ d(π 1 , π 2 ) = 1 AND

Inc(π 1 ∧ π 2 ) = 1 ⇒ ∀ω i , |π 1 (ω i ) -π 2 (ω i )|=1
AND ∀ω i , min(π 1 (ω i ), π 2 (ω i ))=0 ⇒ 1) ∀ i, π 1 (ω i ) ∈ {0,1} and π 2 (ω i ) ∈ {0,1} and 2) ∀ i, π 1 (ω i )=1π 2 (ω i ) (contradiction with ii) and iii) of the above assumption).

Proofs of Property 1, Property 2, Property 5 and Property 6 are immediate since both d and Inc satisfy them as shown in [START_REF] Jenhani | Information Anity: a new similarity measure for possibilistic uncertain information[END_REF]. Let us now prove that GA satises Property 7-Property 12.

Situation 2 :

 2 The referee r 1 expresses his full satisfaction for p 1 and p 3 and fully rejects p 2 (i.e. π ′ whereas r 2 expresses his full satisfaction for p 1 and p 2 and fully rejects p 3 (i.e. π ′

	2

  88 Inc(π 4 ∧ π 5 )=1. If we subtract 0.4 from ω 2 in π 11 or from ω 3 in π 11 ⇒ π 12 [1 0.4 0.4] and π 13 [1 0.8 0]. ⇒ GA(π 11 ,π 12 )=GA(π 11 ,π 13 )=0.93. If we add 0.2 to ω 2 in π 11 or to ω 3 in π 11 ⇒ GA(π 11 ,π ′ 12 )=GA(π 11 ,π ′ 13 )=0.96. Property 12. Maintaining similarity Let π 14 [1 0.7 0], π 15 [1 0.2 0.7]. If we add α = 0.3 to ω 2 in π 14 and to ω 3 in π 15 ⇒ π ′ GA(π 14 ,π ′ 14 )=GA(π 15 ,π ′ 15 )=0.95. If we subtract α = 0.5 to ω 2 in π 14 and to ω 3 in π 15 ⇒ π ′′ 14 [1 0.2 0] and π ′′ 15 [1 0.2 0.2]. ⇒ GA(π 14 ,π ′′ 14 )=GA(π 15 ,π ′′ 15 )=0.91. Example 2 If we reconsider the example of the referees where π 1

	Property 8. Degree enhancement Let π 4 [0,0,1], π ′ 4 [0.6,0,1], π 5 [0,1,0] and π ′ 5 [0.6,1,0] (we added 0.6 to ω 1 ). We have d(π ′ 4 ,π ′ 5 )=d(π 4 ,π 5 )=0.66. But Inc(π ′ 4 ∧ π ′ 5 )=0.4 = ⇒ GA(π ′ 4 ,π ′ 5 )=0.46>GA(π 4 ,π 5 )=0.17 Property 9 and 10. Mutual convergence Let π 6 [0.2,1,0.5] and π ′ 6 [0.2,1,1] (We took π ′ 6 (ω 3 )=π 1 (ω 3 )=1) ⇒ GA(π 1 ,π ′ 6 )=0.86>GA(π 1 ,π 6 )=0.53. Property 11. Indierence preserving Let π 11 [1 0.8 0.4], α = 0.4. π ′ 12 [1 1 0.4] and π ′ 13 [1 0.8 0.6]. 14 [1 1 0] and π ′ 15 [1 0.2 1].

⇒ ⇒

  Proposition 5, only when d=Manhattan distance and ∧=min. We can easily check that d can be replaced by the Euclidean distance and ∧ by the product. Moreover, since GA generalizes InfoA[START_REF] Jenhani | Information Anity: a new similarity measure for possibilistic uncertain information[END_REF], proofs of unchanged properties (Property 1, Property 2, Property 5 and Property 6) are immediate and consequently are not provided. The proof of Proposition 5 shows that our proposed measure satises all the proposed properties.Proof of Proposition 5Let us begin by showing that GA satises the strong Upper and Lower bound properties derived respectively in Proposition 1 and Proposition 2.

	Proposition 1:

(p 1 ) = 1, π ′ 1 (p

) = 0, π ′ 1 (p

) = 1)

Proceedings of IPMU'08

Property 7:

If π 1 is more specic than π 2 which is in turn more specic then π 3 , since ∃ ω 0 s.t. π 1 (ω 0 ) < π 2 (ω 0 ) < π 3 (ω 0 ):

Property 8:

We have d(π ′ 1 , π ′

2 )=d(π 1 , π 2 ) since we added the same value α to the same ω i in π 1 and π 2 . In the other hand, if min(π ′

we certainly obtain:

1) If we add α to π 1 (ω i ) (which leads to π 2 ) or α to π 1 (ω j ) (which leads to

2) The second proof is immediate from 1) if we subtract α.

Property 12:

1) Similarly to the above proof, if we add α to π 1 (ω i ) and keep the other degrees unchanged (which leads to π ′ 1 ) and α to π 2 (ω j ) and keep the other degrees unchanged (which leads to

2 )=0 (since we only deal with normalized distributions) ⇒ GA(π 1 , π ′ 1 )=GA(π 2 , π ′ 2 ). 2) The second proof is immediate from 1) if we subtract α.

Proceedings of IPMU'08


Mostafa Sadeghi
email: m.saadeghii@gmail.com

Massoud Babaie-Zadeh

Christian Jutten
email: christian.jutten@gipsa-lab.grenoble-inp.fr

LEARNING OVERCOMPLETE DICTIONARIES BASED ON PARALLEL ATOM-UPDATING

Keywords: Sparse approximation, compressive sensing, dictionary learning, alternative minimization

In this paper we propose a fast and efficient algorithm for learning overcomplete dictionaries. The proposed algorithm is indeed an alternative to the well-known K-Singular Value Decomposition (K-SVD) algorithm. The main drawback of K-SVD is its high computational burden especially in highdimensional problems. This is due to the fact that in the dictionary update stage of this algorithm an SVD is performed to update each column of the dictionary. Our proposed algorithm avoids performing SVD and instead uses an especial form of alternating minimization. In this way, as our simulations on both synthetic and real data show, our algorithm outperforms K-SVD in both computational burden and the quality of the results.

INTRODUCTION 1.Sparse Approximation

Sparse approximation of signals has received a lot of attention during the last decade [1]. This is due to its capability in various applications such as Compressive Sensing (CS) [START_REF] Donoho | Compressed sensing[END_REF], image processing tasks (e.g. denoising, compression, inpainting, zooming) [START_REF] Elad | On the role of sparse and redundant representations in image processing[END_REF], and linear regression and variable selection [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF]. The sparse approximation problem consists in approximating a given signal as a linear combination of as few as possible basis functions. Each basis function is called an atom and the collection of them is called a dictionary [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF]. This dictionary is overcomplete, i.e. the number of atoms is (much) more than the dimension of each atom. Specifically, let y ∈ R n be the signal whose sparsest approximation is going to be found in D ∈ R n×K , with K > n. This amounts to solve the following problem: P 0 : min x ∥x∥ 0 subject to ∥y -Dx∥ 2 ≤ ϵ, (1) where ∥.∥ 0 stands for the so-called ℓ 0 (pseudo) norm, which counts the number of nonzero elements, and ϵ is a small positive constant. The above problem needs a combinatorial search and is generally NP-hard [START_REF] Donoho | Stable recovery of sparse overcomplete representations in the presence of noise[END_REF]. So, alternative methods are used to solve it [1,[START_REF] Mohimani | A fast approach for overcomplete sparse decomposition based on smoothed ℓ 0 norm[END_REF]. One of the most successful ideas is to replace the non-convex sparsity measure ∥.∥ 0 with its best convex approximation ∥.∥ 1 [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF] which leads to the following convex problem:

P 1 : min x ∥x∥ 1 subject to ∥y -Dx∥ 2 ≤ ϵ. (2)
Many algorithms have been introduced to solve the problem of finding the sparsest approximation of a signal in a given overcomplete dictionary (for a good review see [START_REF] Tropp | Computational methods for sparse solution of linear inverse problems[END_REF]). These algorithms can be classified into two general categories, greedy methods such as Orthogonal Matching Pursuit (OMP) [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF] and Compressive Sampling Matching Pursuit (CoSaMP) [START_REF] Needell | Cosamp: Iterative signal recovery from in-complete and inaccurate samples[END_REF], and relaxation methods, which replace the combinatorial P 0 problem with a tractable one, e.g. P 1 problem. Iterative Shrinkage-Thresholding (IST) [START_REF] Elad | A wide-angle view at iterated shrinkage algorithms[END_REF], Iteratively Re-weighted Least Squares (IRLS) [START_REF] Chartrand | Iteratively reweighted algorithms for compressive sensing[END_REF], and Smoothed ℓ 0 (SL0) [START_REF] Mohimani | A fast approach for overcomplete sparse decomposition based on smoothed ℓ 0 norm[END_REF] are some examples of the second category. Greedy algorithms successively choose the appropriate atoms of the dictionary that result in the greatest improvement in the quality of the approximation. Theses algorithms benefit from high speed, but their accuracy is usually less than that of the second category.

Learning overcomplete dictionaries

For a given class of signals, e.g. class of natural facial images, the dictionary should have the capability of sparsely representing the signals. In some applications there is a predefined and universal dictionary that is known to be wellmatched to the contents of the given class of signals, for example, the overcomplete DCT dictionary for the class of natural images. These non-adaptive dictionaries are appealing because of their simplicity and in some cases their fast computations. However, learning the atoms from some training signals would result in dictionaries with the capability of bet-ter matching the contents of the signals. In this way, the adaptive dictionaries would outperform the non-adaptive ones in many applications such as image denoising [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF], classification tasks [START_REF] Mairal | Task-driven dictionary learning[END_REF], and so on.

Most of the dictionary learning algorithms are indeed a generalization of K-means clustering algorithm [START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF]. While in K-means, each training signal is forced to use only one atom (called centroid), in the sparse approximation case, each signal is allowed to use more than one atom provided that it uses as fewest as possible atoms. The approach of K-means to optimize a set of atoms (called codebook) is to iteratively perform two stages. In the first stage, known as the clustering stage, training signals are assigned to their nearest (usually in the sense of ℓ 2 norm) atoms. The second stage is the update of the atoms in which each atom is updated as the (weighted) average of the signals in its cluster. This procedure is repeated several times. As a generalization of this approach, dictionary learning algorithms iteratively performs the two stages of sparse approximation and dictionary update. In the first stage, which is actually the clustering of signals into a union of subspaces, the sparse approximation of each signal is computed using the current dictionary. The second stage is the update of the dictionary.

In this paper we are going to propose an efficient dictionary learning algorithm, which is indeed a good alternative to K-SVD. As will be seen in the experimental results, our proposed algorithm outperforms K-SVD in both execution time and the quality of the results.

The paper is organized as follows. In the Section 2 we briefly review the general dictionary learning problem together with K-SVD algorithm. Then in Section 3 we detail our proposed algorithm. Section 4 presents some experimental results. Finally, Section 5 concludes the paper.

DICTIONARY LEARNING PROBLEM

Consider a set of L training signals in R n as {y i } L i=1 . Putting these signals as the columns of the matrix Y, the general dictionary learning problem is then to find a sparsifying dictionary, D, by solving the following problem:

min D∈D,X∈X ∥Y -DX∥ 2 F , (3)
where D and X are the admissible sets of the dictionary and the coefficient matrix, respectively. D is usually defined as the set of all dictionaries with unit column-norm. Since we require that each signal has a sparse approximation, X is the set of all matrices X with sparse columns. As stated previously, the general approach to solve (3) is to use alternating minimization over X and D, i.e. by fixing D the objective function is minimized over X, and vice versa. With a fixed D, the minimization of (3) over X is equivalent to sparsely approximating the training signals over D. Among the various sparse coding algorithms, OMP (or its variants) is very appealing. This is due to two reasons. The first reason is the speed of OMP. The second one is its capability to be efficiently implemented in batch mode. In some applications, such as dictionary learning, in which we need to find sparse approximations of a batch of signals in the same dictionary, we can factor some common operations of OMP. This fact along with the use of Cholesky factorization results in the significant acceleration of OMP which leads to Batch-OMP algorithm [START_REF] Rubinstein | Efficient implementation of the K-SVD algorithm using batch orthogonal matching pursuit[END_REF].

K-SVD

In the dictionary update stage of K-SVD, only one atom is updated at a time. Moreover, while updating each atom, the nonzero entries in the associated row vector of X is also updated. In other words, only those signals participate in updating one atom that have used it. This is in accordance with the approach of K-means in which each atom is updated using its own cluster signals. This also prevents each row vector to be filled. In what follows, we define x(ω) as a vector containing those entries of x that are indexed by ω, and E(:, ω) as a matrix containing those columns of E that are indexed by ω. Assume that we want to update d i along with the nonzero entries of x i T , the ith row of X. We define

ω i = { j : x i T (j) ̸ = 0 } as the support of x i T .
Then the problem of updating d i along with x i T (ω i ) amounts to solve the following minimization problem:

min d,xr ∥E r i -dx r ∥ 2 F subject to ∥d i ∥ 2 = 1, (4)
where

E r i = E i (:, ω i ), in which E i = Y - ∑ j̸ =i d j x j
T denotes the approximation error matrix when d i is removed, and x r is a row vector of length |ω i |. The above problem actually finds the closest rank-1 approximation to E r i and can be easily solved via SVD.

PARALLEL ATOM-UPDATING DICTIONARY LEARNING

In this section we introduce our proposed algorithm. This algorithm like K-SVD is based on atom-by-atom updating.

The main drawback of K-SVD is its computational burden especially in high dimensions. This is due to performing SVD for atom updating. An alternative way of solving ( 4) is to use the idea of alternating minimization [START_REF] Rubinstein | Efficient implementation of the K-SVD algorithm using batch orthogonal matching pursuit[END_REF]. In other words, ( 4) is alternatively minimized over d and x r . A few (e.g. 3) alternations give a fast approximation to SVD. The resulting algorithm is known as the Approximate K-SVD (AK-SVD) [START_REF] Rubinstein | Efficient implementation of the K-SVD algorithm using batch orthogonal matching pursuit[END_REF]. Although performing more alternations gives a better approximation, the average performance will not exceed the performance of the exact solution, i.e. via SVD. We describe a different way of performing alternating minimization to update the atoms and their associated row vectors in the coefficient matrix. To this aim, consider the overall error matrix,

E = Y -(A 1 + A 2 + . . . + A K ), ∀i : A i = d i x i T . (5)
In K-SVD (or AK-SVD), in order to update (the nonzero columns of) for example A i , the updated versions of A 1 , . . . , A i-1 are used to compute E i ; while A i+1 , . . . , A K have not been yet updated. Keeping this point in mind, we propose to update the atoms in parallel. In other words, instead of fully updating each A i by performing T alternations between d i and x r , we perform T alternations in such a way that in each alternation all of A i 's are partially updated (using only one alternation).

In this way, in the subsequent alternations all A i 's have been partially updated. As our experimental results in Section 4 suggest, parallel updating of the atoms may result in further accelerating the convergence rate and even the quality of the final result.

To update each A i , we need to compute the error matrix E i . It can be easily seen that this matrix can be updated as follows. The overall error matrix is firstly computed as E = Y -DX using the current dictionary and coefficient matrix. Then E i = E+A i and after updating A i to A (new) i , the error matrix E is updated as

E = E i -A (new) i
. In this way, there is no need to completely re-compute the error matrix for each atom, but instead it is updated in a ranked-1 manner.

Algorithm 1 gives a description of the proposed algorithm, which we have called it Parallel Atom-Updating Dictionary Learning (PAU-DL) algorithm. By OMP(Y, D, τ ) we mean the sparse approximation of Y in D and with threshold τ . Depending on the application at hand, τ may be the threshold on the approximation error (ϵ in (1)) or the maximum allowed number of atoms in the sparse approximation of each training signal.

SIMULATIONS

We evaluate the efficiency of our proposed algorithm and K-SVD1 with three sets of experiments. In the first set we aim to evaluate the capability of the two algorithms in recovery of a known dictionary. The second experiment is on an autoregressive (AR) signal, where there is no underlying dictionary, and we just evaluate the capability of the algorithms in learning a good (i.e. sparsifying) dictionary form the training signals. To further evaluate the advantage of PAU-DL over K-SVD, we consider as the third experiment the problem of image denoising over a learned overcomplete dictionary as in [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF].

Our simulations were performed in MATLAB R2010b environment on a system with 3.8 GHz CPU and 8 GB RAM, under Microsoft Windows 7 operating system. As a rough Algorithm 1 PAU-DL algorithm 1: Task: Learning an overcomplete dictionary to sparsely approximate Y = {y i } L i=1 . 2: Initialization: Set k = 0, D (k) = D 0 . 3: The main loop: Repeat until convergence: 4: Sparse Approximation: X (k) = OMP(Y, D (k) , τ ). 5: Dictionary Update: Set D = D (k) , X = X (k) , E = Y -DX, and repeat the following loop T times (T = 3 works well): 6: for i = 1, . . . , K do 7:

E i = E + d i x i T 8: E r i = E i (:, ω i ) where ω i = { j : x i T (j) ̸ = 0 } 9: x T r = x i T (ω i )
10:

d i = E r i x T r
11:

d i = d i /∥d i ∥ 2
12: measure of complexity, we will mention the run times of the algorithms.

x i T (ω i ) = d T i E r i 13: E = E i -d i x i

Reconstruction of a known dictionary

We generated the underlying dictionary by normalizing a random matrix of size 20 × 50, with zero mean and unit variance independent and identically distributed (i.i.d.) Gaussian entries. A collection of 2000 training signals {y i } 2000 i=1 were produced, each as a linear combination of s different columns of the dictionary, with zero mean and unit variance i.i.d. Gaussian coefficients in random and independent positions. We varied s from 3 to 6. We then added white Gaussian noise with Signal to Noise Ratio (SNR) levels of 10, 20, 30, and 100 dB. We applied all algorithms onto this noisy training signals, and compared the resulting recovered dictionaries to the generating dictionary as follows. Assume that d i is a generating atom and di is the atom in the recovered dictionary that best matches d i among the others. We say that the recovery is successful if |d T i di | is above 0.99 [START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF]. The percentage of the correct recovery was used as the measure of successfully reconstructing the generative dictionary. We performed 100 alternations between sparse approximation and dictionary update stages for both algorithms. The initial dictionary was made by randomly choosing different columns of the training signals followed by a normalization.

The average percentage of successfully recovery of the underlying atoms (APSRA) is shown in Fig. 1. To see the convergence behaviour of the two algorithms, the improvement of APSRA along the alternation number for SNR = 20 dB and s = 4, 5 is shown in Fig. 2. The average execution times of K-SVD and PAU-DL were 27.68 and 5.41 seconds, respectively. With these results in mind, we deduce the following observations:

• PAU-DL has a better APSRA compared to K-SVD in average. This is especially evident at s = 5 and s = 6.

• The convergence rate of PAU-DL is faster than K-SVD.

AR(1) signal

In this experiment, we consider an AR(1) signal (according to [START_REF] Skretting | Recursive least squares dictionary learning algorithm[END_REF]) that is generated as v(k) = 0.95v(k -1) + e(k), where e(k) is Gaussian noise with zero mean and unit variance. A collection of L = 2000 training signals were made by chopping this signal into vectors of length n = 20. Number of atoms was set to m = 40, and s = 5 atoms were used to approximate each training vector. For both algorithms 100 alternations were done. As in [START_REF] Skretting | Recursive least squares dictionary learning algorithm[END_REF], we computed SNR as SNR = 10 log ∥Y∥ 2 F ⧸∥Y -DX∥ 2 F . SNR versus alternation number is plotted in Fig. 3. From this figure we see that PAU-DL has reached a higher SNR value compared to K-SVD. The average execution times of K-SVD and PAU-DL were 15.88 and 2.79 seconds, respectively.

Image denoising over learned dictionaries

We evaluate here the efficiency of PAU-DL relative to K-SVD in an image denoising experiment. We aim to find an estimate of a clean image contaminated with an additive white Gaussian noise with zero mean. The approach of sparse approximation is to firstly divide the noisy image into some small blocks (typically of size 8 × 8), then learn an overcomplete dictionary using these blocks as the training signals, and finally denoise each block over the learned dictionary [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF]. As in [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF], we used Peak Signal to Noise Ratio (PSNR), as the criterion for comparison of the denoising quality. We considered four test images, all of size 256 × 256. To learn a dictionary for each image, we randomly selected 30000 blocks of it as the training signals. We repeated each experiment (corresponding to a certain level of noise) 5 times and averaged the results. The final PSNR values are shown in Table 1. The average execution times of K-SVD and PAU-DL were approximately 90 and 30 seconds, respectively.

These results together with those in the previous experiments all suggest the advantage of PAU-DL compared to K-SVD.

CONCLUSION

We proposed a fast and efficient alternative to K-SVD. Our algorithm is based on updating the atoms of the dictionary in parallel using the idea of alternating minimization. As the simulations results on both synthetic and real data showed, our algorithm outperforms K-SVD in both the average execution time and the quality of the results.

T 14 :

 14 end for 15: Set k = k + 1, D (k) = D, and go back to the sparse approximation stage.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Successful recovery ratios. Each figure corresponds to a certain amount of noise.

Fig. 3 .

 3 Fig. 3. SNR in dB is plotted versus the alternation number during the learning process.

For K-SVD and OMP we have used K-SVD-Box v10 and OMP-Box v10 available at http://www.cs.technion.ac.il/ ˜ronrubin/ software.html

* This work has been partially funded by the Iran National Science Foundation (INSF).


Adrien Dubouloz
email: adrien.dubouloz@u-bourgogne.fr

Lucy Moser-
email: moser@u-bourgogne.fr

Pierre-Marie Poloni
email: pierre-marie.poloni@unibas.ch

AUTOMORPHISM GROUPS OF CERTAIN RATIONAL HYPERSURFACES IN COMPLEX FOUR-SPACE

Keywords: Automorphisms, exotic structures, contractible complex threefolds, extensions of automorphisms, Makar-Limanov invariant. Subject classification: 14L30, 13R20

The Russell cubic is a smooth contractible affine complex threefold which is not isomorphic to affine three-space. In previous articles, we discussed the structure of the automorphism group of this variety. Here we review some consequences of this structure and generalize some results to other hypersurfaces which arise as deformations of Koras-Russell threefolds.

Introduction

In order to prove the linearizability of algebraic actions of C * on affine three-space, [START_REF] Koras | C * -actions on C 3 : the smooth locus of the quotient is not of hyperbolic type[END_REF][START_REF] Kaliman | C * -actions on C 3 are linearizable[END_REF], Koras and Russell studied hyperbolic C * -actions on more general smooth contractible threefolds. This led them to introduce a set of threefolds which are smooth affine and contractible, however not isomorphic to A 3 . These varieties are now known as Koras-Russell threefolds. One of the families of these varieties, called Koras-Russell threefolds of the first kind, is given by hypersurfaces X d,k,ℓ in the affine space A 4 = Spec(C[x, y, z, t]) defined by equations of the form x d y + z k + t ℓ + x = 0 where d ≥ 2 and 2 ≤ k < ℓ with k and ℓ relatively prime. All of these threefolds admit algebraic actions of the complex additive group G a and they were originally proven to be not isomorphic to affine space by means of invariants associated to those actions. These invariants, known as the Derksen and Makar-Limanov invariants, are defined respectively for an affine variety X = Spec(A) admitting non trivial G a -actions as the sub-algebra Dk(X) of A consisting of regular functions invariant under at least one non trivial G a -action on X and its sub-algebra ML(X) consisting of regular functions invariants under all non trivial such actions.

These tools have since become important and useful to study affine algebraic varieties. In particular, one of the central elements in the proofs of many existing results concerning Koras-Russell threefolds of the first kind, and some of the generalizations we consider in this article, is the fact that their Makar-Limanov and Derksen invariants are equal to C[x] and C[x, z, t] respectively (see, for example, [START_REF] Kaliman | On the Russell-Koras contractible threefolds[END_REF], Lemma 8.3 and [8], Example 9.1. for the Koras-Russell threefolds). This property imposes very strong restrictions on the nature of isomorphisms between such varieties which enable sometimes an explicit description of their isomorphism classes and automorphism groups.

Koras-Russell threefolds of the first kind belong to the more general family of hypersurfaces X = X(d, r 0 , g) in A 4 = Spec(C[x, y, z, t]) defined by equations of the form x d y + r 0 (z, t) + xg(x, z, t) = 0 where d ≥ 2, r 0 ∈ C[z, t] and g ∈ C[x, z, t]. All varieties of this type share the property that they come equipped with a flat A 2 -fibration π = pr x : X → A 1 = Spec(C[x]) restricting to a trivial bundle over the complement of the origin and with degenerate fiber π -1 (0) isomorphic to the cylinder C 0 × A 1 over the plane curve C 0 ⊂ Spec(C[z, t]) with equation r 0 = 0. In particular, noting that π -1 (A 1 \ {0}) is factorial, and that π -1 (0) = div(x) is a prime principal divisor if and only if C 0 is reduced and irreducible, we see that a threefold X is factorial whenever the corresponding curve C 0 is reduced and irreducible (see also [START_REF] Nagata | A remark on the unique factorization theorem[END_REF]). A combination of [START_REF] Kaliman | Polynomials with general C 2 -fibers are variables[END_REF] and [START_REF] Sathaye | Polynomial ring in two variables over a D.V.R.: a criterion[END_REF] implies that X is isomorphic to A 3 if and only if π -1 (0) is reduced and isomorphic to A 2 , whence, by virtue of [START_REF] Abhyankar | On the uniqueness of the coefficient ring in a polynomial ring[END_REF] if and only if C 0 is isomorphic to the affine line. Furthermore, identifying the coordinate ring A of X with the sub-algebra C[x, z, t, x -d (r 0 + xg(x, z, t))] of C[x, z, t] x via the canonical localization homomorphism with respect to x gives rise to a description of X as the affine modification σ = pr x,z,t | X : X → A 3 of A 3 = Spec(C[x, z, t]) with center at the closed subscheme Z with defining ideal J = (x d , r 0 (z, t) + xg(x, z, t)) and divisor D = {x d = 0} in the sense of [START_REF] Kaliman | Affine modifications and affine varieties with a very transitive automorphism group[END_REF]. That is, X is isomorphic to the complement of the proper transform of D in the blow-up of A 3 with center at Z. Noting that the closed subscheme Z of A 3 is supported along the curve C 0 ⊂ Spec(C[z, t]), this description implies that a smooth X for which C 0 is irreducible, topologically contractible, but not isomorphic to the affine line, is an exotic A 3 [9, Theorem 3.1]. This holds for instance for smooth deformations of Koras-Russell threefolds of the first kind defined by equations of the form x d y + z k + t ℓ + xg(x, y, z) = 0, with k, ℓ ≥ 2 relatively prime and g(0, 0, 0) = 1, corresponding to the irreducible, singular, topologically contractible plane curves

C 0 = {z k + t ℓ = 0}.
The present article reviews three complementary applications of Derksen and Makar-Limanov invariants to the study of threefolds X(d, r 0 , g) as above. First we summarize several properties of automorphism groups of Koras-Russell threefolds of the first kind which appeared separately in previous articles by the authors, and we complete the picture with a characterization of certain natural subgroups of these automorphism groups. Then we turn to the study of non-necessarily smooth deformations of Koras-Russell threefolds defined by equations of the form x d y + z k + t ℓ + xg(x, y, z) = 0. We explain how to obtain a description of isomorphism classes of these threefolds that is reminiscent of the (mini)-versal deformation of the corresponding singular plane curve C 0 = {z k + t ℓ = 0}. Finally, we illustrate on an example of a threefold X = {x d y + r 0 (z, t) = 0} with non-connected associated plane curve C 0 = {r 0 = 0} a general procedure to construct new types of automorphisms of X which do not admit any extension to automorphisms of the ambient space A 4 .

A preliminary observation

Let d ∈ N and r 0 ∈ C[z, t] be fixed. For any g ∈ C[x, z, t], we denote by

J g = (x d , r 0 + xg)
the ideal of C[x, z, t] generated by x d and r 0 + xg, and by A(g) the coordinate ring of the hypersurface X(g) of A 4 = Spec(C[x, y, z, t]) defined by the equation

x d y + r 0 (z, t) + xg(x, z, t) = 0.
Corresponding to the presentation of X(g) as the affine modification σ : X(g) → A 3 mentioned in the introduction, we have a chain of inclusions

C[x, z, t] ⊂ A(g) ⊂ A(g)[x -1 ] ≃ C[x, x -1 , z, t].
The second inclusion is induced by the localization homomorphism with respect to the regular element x ∈ A(g), identifying y ∈ A(g) with -x -d (r

0 + xg) ∈ C[x, x -1 , z, t].
Given a pair of polynomials f, g ∈ C[x, z, t], the universal property of affine modifications [9, Proposition 2.1] implies that every automorphism ϕ of C[x, z, t] which fixes the ideal (x) and maps J g into J f lifts in a unique way to a morphism φ : A(g) → A(f ) restricting to ϕ on the subring C[x, z, t]. Actually, φ is even an isomorphism. Indeed, by hypothesis, there exist α ∈ C * and a, b ∈ C[x, z, t] such that ϕ(x) = αx and ϕ(r 0 + xg) = ax d + b(r 0 + xf ). The second equation implies that b is congruent modulo x to a non-zero constant whence that its residue class in (x d ) and multiplying the previous equation by it, we conclude that r 0 + xf ∈ ϕ(J g ). Thus ϕ maps J g isomorphically onto J f .

C[x, z, t]/(x d ) is a unit for every d ≥ 1. Choosing b ′ ∈ C[x, z, t] such that bb ′ ≡ 1 mod
The following lemma will be used several times throughout this article.

Lemma 2.1. With the notation above assume further that the Derksen and Makar-Limanov invariants of X(f ) and X(g) are equal to C[x, z, t] and C[x], respectively. Then the previous construction provides a one-to-one correspondance between isomorphisms from A(g) to A(f ) and automorphisms of C[x, z, t] which fix the ideal (x) and map J g into J f .

Proof. Note first that the hypotheses imply that neither X(f ) nor X(g) is isomorphic to A 3 and hence, as a consequence of [START_REF] Sathaye | Polynomial ring in two variables over a D.V.R.: a criterion[END_REF], that the surface . This shows that ϕ fixes the ideal (x). Noting that J g = x d A(g) ∩ C[x, z, t] and similarly for J f , we conclude that ϕ(J g ) = J f , which completes the proof.

C 0 × A 1 = {r 0 = 0} ⊂ Spec(C[x, z, t]) is not isomorphic to A 2 .

Automorphisms of Koras-Russell threefolds of the first kind

In this section, we consider Koras-Russell threefolds of the first kind X = X(d, k, ℓ) corresponding to the cases where d ≥ 2, r 0 = z k + t ℓ , and g = 1. Since Dk(X) = C[x, z, t] and ML(X) = C[x], we deduce from Lemma 2.1 that the projection σ = pr x,z,t | X : X → A 3 gives rise to an isomorphism between the automorphism group of X and the subgroup A of automorphisms of C[x, z, t] which preserve the ideals (x) and (x d , r 0 + x). In particular, C * acts linearly on X. In fact, letting A n , 1 ≤ n ≤ d be the normal subgroup of A consisting of the automorphisms ϕ which fix x and which are congruent to the identity modulo (x n ), it was shown more precisely in [START_REF] Dubouloz | Inequivalent embeddings of the Koras-Russell cubic threefold[END_REF][START_REF] Moser-Jauslin | Automorphism groups of Koras-Russell threefolds of the first kind[END_REF] that

Aut(X) ≃ A 1 ⋊ C * and A n /A n+1 ∼ = (C[z, t], +) for all 1 ≤ n ≤ d -1.
The next proposition summarizes several consequences of this description:

Proposition 3.1. Let X = X d,k,ℓ ⊂ A 4 be
a Koras-Russell threefold of the first kind. Then the following hold:

1) Every automorphism of X extends to an automorphism of A 4 .

2) The group Aut(X) acts on X with exactly 4 orbits:

-an open orbit {x = 0} ≃ C * × C 2 , -a copy of C * × C given by x = 0 and z = 0, -the line {x = z = t = 0} minus the point (0, 0, 0, 0), -a fixed point (0, 0, 0, 0). 3) Every finite subgroup of Aut(X) is cyclic. 4) Every one-parameter unipotent subgroup of Aut(X) is contained in A d . In particular, the subgroup generated by all G a -actions on X is strictly smaller than A 1 . Remark 3.2. In contrast with Property 2) above, the group of holomorphic automorphisms of X acts with at most three orbits. Indeed, one checks for instance that the holomorphic automorphism Ψ of A 4 defined by Ψ(x, y, z, t) = (x, e x d-1 y -

1 -e x d-1 x d-1 , e x d-1 k z, e x d-1 ℓ t)
maps X onto itself. Hence Ψ induces a holomorphic automorphism ψ of X for which ψ(0, 0, 0, 0) = (0, 1, 0, 0), i.e. (0, 0, 0, 0) is no longer a fixed point for the action of holomorphic automorphisms of X. The exact number of orbits under the action this group is not known. In particular, it is still an open question whether any threefold X d,k,ℓ is biholomorphic to the affine space.

Proof. Properties 1) and 2) were established in [START_REF] Dubouloz | Inequivalent embeddings of the Koras-Russell cubic threefold[END_REF] for the Russell cubic and in [START_REF] Moser-Jauslin | Automorphism groups of Koras-Russell threefolds of the first kind[END_REF] for the general case.

The third property was originally formulated as a question by V. Popov. Since Aut(X) ≃ A 1 ⋊ C * , it is enough to show that A 1 does not contain non-trivial torsion elements. Indeed, if so, the projection to the second factor C * will induce an isomorphism between every finite subgroup of Aut(X) and a subgroup of C * . So suppose that ϕ ∈ A 1 is a nontrivial torsion element, say of order m ≥ 2. By possibly switching z and t, we can further assume that ϕ(z) = z. Choosing N ∈ N minimal with the property that ϕ(z

) ≡ z + f (z, t)x N mod (x N +1 ) for some f ∈ C[z, t] \ {0}, we would have ϕ m (z) ≡ z + mf (z, t)x N ≡ z mod (x N +1 ), a contradiction.
For the last property, it follows from Lemma 2.1 that every additive group action on X is induced by a locally nilpotent derivation D of the coordinate ring of X extending a locally nilpotent C[x]-derivation of C[x, z, t] which maps the ideal J = (x d , z k + t ℓ + x) into itself, the second condition being equivalent to the property that the corresponding exponential automorphisms preserve this ideal. We will show that in fact the image of D is contained in the ideal (x d ), which implies that the corresponding one-parameter unipotent subgroup of Aut(X) is contained in A d . We prove this by induction, assuming that

D ≡ 0 modulo (x k ) with 0 ≤ k < d. Since D(z k + t ℓ + x) = ax d + b(z k + t ℓ + x) where a, b ∈ C[x, z, t]
, the hypothesis implies that x k divides b. On the other hand, D 1 = x -k D is again a locally nilpotent derivation such that D 1 (x) = 0 and for which we have

D 1 (z k + t ℓ + x) = ax d-k + (b/x k )(z k + t ℓ + x). Thus D 1 induces a locally nilpotent derivation D 1 of C[x, z, t]/(x) ∼ = C[z, t]
which maps the ideal generated by z k + t ℓ into itself. So D 1 is necessarily trivial as there is no nontrivial G a -action preserving a singular plane curve. Thus D 1 ≡ 0 modulo (x) and hence D ≡ 0 mod (x k+1 ). Remark 3.3. Recall that we always have an exact sequence of groups

0 → Aut 0 (A 4 , X) → Aut(A 4 , X) ρ → Aut(X)
where Aut(A 4 , X) denotes the subgroup of Aut(A 4 ) consisting of automorphisms which leave X invariant and where Aut 0 (A 4 , X) denotes the kernel of ρ. The surjectivity of ρ was established in Property 1) of the above proposition by constructing explicit lifts of automorphisms of X to automorphisms of A 4 . Nevertheless, this construction was only set-theoretic and it is not clear whether the above sequence splits. Note however that since an element ϕ ∈ A d is the identity modulo (x d ) and preserves the subring C[x, z, t] of the coordinate ring of X, it lifts in a natural way to an automorphism Φ of C[x, y, z, t] by letting simply Φ(y) = y + (ϕ(r 0 + x) -r 0 -x)/x d . This gives rise to group homomorphism A d → Aut(A 4 , X), ϕ → Φ, which, combined with the fact that the action of C * on X comes as the restriction of a linear action on A 4 , extends to a group homomorphism j : A d ⋊ C * → Aut(A 4 , X) such that ρ • j = id. We do not know whether j can be extended to a splitting of the above exact sequence.

Deformations of Koras-Russell threefolds

In this section, we consider hypersurfaces X(g) of A 4 = Spec(C[x, y, z, t]) defined by equations of the form

x d y + r 0 (z, t) + xg(x, z, t) = 0
where r 0 = z k + t ℓ and d ≥ 2 are fixed, and we let the polynomial g ∈ C[x, z, t] vary. The case r 0 = z 2 +t 3 was treated in [START_REF] Dubouloz | Non cancellation for smooth contractible affine threefolds[END_REF], leading to the construction of large families of non-isomorphic smooth affine threefolds that are all biholomorphic to each other and diffeomorphic to the affine space. Here, we show that similar techniques can be applied to find isomorphisms between deformations of hypersurfaces in a more general setting. Theorem 4.2 below relies again in a crucial way on the fact that the Derksen and Makar-Limanov invariant of threefolds X(g) are equal to C[x, z, t] and C[x] respectively. These properties can be checked using the methods developed in [START_REF] Kaliman | AK-invariant of affine domains[END_REF], namely via a careful study of homogeneous locally nilpotent derivations on a well-chosen quasi-homogeneous deformation of X(g). The complete proof is quite long and technical but is essentially straightforward using the aforementioned methods. We shall omit it here, in particular since it involves no new ideas or arguments. Notation 4.1. We will be considering derivations of C[z, t] defined by the Jacobian of a polynomial. If f ∈ C[z, t], we denote by f z the partial derivative ∂f /∂z, and by f t the partial derivative ∂f /∂t. For f, g ∈ C[z, t], the Jacobian Jac(f, g) denotes f z g t -f t g z . Finally, Jac(f, •) denotes the derivation of C[z, t] defined by g → Jac(f, g).

Let B = C[a i,j ] be the polynomial ring in the (k -1)(ℓ-1) indeterminates a i,j , 0 ≤ i ≤ k -2, 0 ≤ j ≤ ℓ -2,
let m 0 ⊂ B be the maximal ideal generated by the a i,j and let

F = r 0 + 0≤i≤k-2, 0≤j≤ℓ-2 a i,j z i t j ∈ B[z, t]. Given a homomorphism α : B → C[x] such that α(m 0 ) ⊂ xC[x], the image of F in C[x]⊗ B B[z, t] ≃ C[x, z, t]
has the form r 0 +xg α for some polynomial g α belonging to the C[x]-submodule of C[x, z, t] generated by the monomials z i t j with 0 ≤ i ≤ k -2 and 0 ≤ j ≤ ℓ -2. Every such homomorphism α thus determines a threefold X α = X(g α ) defined by the equation x d y + r 0 + xg α = 0. Theorem 4.2. With the notation above, the following statements hold:

1) For every g ∈ C[x, z, t], there exists a homomorphism α :

B → C[x] such that X(g) is isomorphic to X α .
2) Two homomorphisms α, β : B → C[x] determine isomorphic threefolds X α and X β if and only if there exist constants λ, µ ∈ C * such that the following diagram commutes

B π d •α / / ζ λ C[x]/(x d ) x →µx B π d •β / / C[x]/(x d ) where π d : C[x] → C[x]/(x d
) denotes the natural projection and where ζ λ : B → B is the linear automorphism defined by a i,j → λ ℓi+kj-kℓ a i,j . Remark 4.3. Noting that the subvariety V of T × A 2 = Spec(B[z, t]) with equation F = 0 is the (mini)-versal deformation of the curve C 0 ⊂ A 2 with equation r 0 = 0 (see e.g. §14.1 in [START_REF] Hartshorne | Deformation Theory[END_REF]), we can re-interpret the above result as the fact that for fixed d ≥ 2, isomorphism classes of hypersurfaces of the form X(g) are in one-to-one correspondence with one-parameter infinitesimal embedded deformations of order d -1 of C 0 , up to the equivalence between such deformations defined in the second assertion of the theorem.

Proof. 1) In view of Lemma 2.1, to prove the first assertion, it is enough to show that, given a polynomial g ∈ C[x, z, t], there exist elements b m , m = 1, . . . , d -1 in the sub-vector space of C[z, t] generated by the monomials

z i t j , 0 ≤ i ≤ k -2, 0 ≤ j ≤ ℓ -2 and a C[x]-automorphism ϕ of C[x][z, t] which maps the ideal (x d , r 0 + xg) into the ideal (x d , r 0 + d-1 m=1 b m x m ). We may write g = m≥1 u m x m-1 = m≥1 (s m + t m )x m-1
where for every m, s m belongs to the sub-vector space of C[z, t] generated by the monomials

z i t j , 0 ≤ i ≤ k -2, 0 ≤ j ≤ ℓ -2, while t m is in the ideal (z k-1 , t ℓ-1 )C[z, t].
Let t 0 = 0 and denote by ν = ν(g) the maximal integer with the property that t m = 0 for every m ≤ ν -1. If ν = d then we are done. Otherwise, we will proceed by induction.

Note that the image of the C-derivation of C[z, t]/(r 0 ) induced by the Jacobian derivation Jac(r 0 , •) of C[z, t] is equal to the ideal of C[z, t]/(r 0 ) generated by the residue classes of z k-1 and t ℓ-1 . Indeed, one checks for example that, given a ≥ k -1 and b ≥ 0, we have Jac(r 0 , λz a-k+1 t b+1 ) = z a t b -λℓ(a -k + 1)z a-k t b r 0 ≡ z a t b mod (r 0 ), where λ = (k(b + 1) + ℓ(a -k + 1)) -1 . This fact guarantees the existence of polynomials h, f ∈ C[z, t] such that Jac(h, r 0 ) = t ν + r 0 f . Let us consider the C[x]/(x ν+1 )-automorphism

ϕ = exp(-x ν Jac(h, •)) of C[x]/(x ν+1 )[z, t].
Since its Jacobian is a nonzero constant, it lifts, by the main theorem in [START_REF] Van Den Essen | The special automorphism group of R[t]/(t m )[x 1 . . . , xn] and coordinates of[END_REF], to a C[x]-automorphism ϕ of C[x][z, t] such that ϕ(x) = x and ϕ(a) ≡ a -x ν Jac(h, a) mod (x ν+1 ) for all a ∈ C[x, z, t]. Then, we have the following congruences modulo (x ν+1 ).

ϕ(r 0 + xg) ≡ r 0 + ν-1 m=1 s m x m + x ν (s ν + t ν ) -x ν Jac(h, r 0 ) mod (x ν+1 ) ≡ r 0 + ν m=1 s m x m -x ν r 0 f mod (x ν+1 ) ≡ (1 -x ν f )(r 0 + ν m=1 s m x m ) mod (x ν+1 ). It follows that there exists a polynomial R ∈ C[x, z, t] such that ϕ(r 0 + xg) ≡ (1 -x ν f )(r 0 + ν m=1 s m x m + x ν+1 R) mod (x d ). Letting g = ν m=1 s m x m-1 + x ν R
, we obtain that ϕ maps the ideal (x d , r 0 + xg) into the ideal (x d , r 0 + x g), and since ν(g) > ν(g) by construction, we are done by induction.

2) Let us first rephrase the second assertion. If we let α(a i,j ) = xα i,j (x) and β(a i,j ) = xβ i,j (x) with α i,j , β i,j ∈ C[x] for 0 ≤ i ≤ k -2, 0 ≤ j ≤ ℓ -2, the latter states that the threefolds X α and X β are isomorphic if and only if there exist two constants λ, µ ∈ C * such that

µxα i,j (µx) ≡ λ ℓi+kj-kℓ xβ i,j (x) mod (x d ) for all 0 ≤ i ≤ k -2 and all 0 ≤ j ≤ ℓ -2. If such constants λ, µ ∈ C * exist then the automorphism ϕ of C[x, z, t] defined by ϕ(x) = µx, ϕ(z) = λ -ℓ z, ϕ(t) = λ -k t satisfies that ϕ(r 0 + xg α ) ≡ λ -kℓ (r 0 + xg β ) modulo (x d
). Thus, ϕ maps the ideal (x d , r 0 + xg α ) into the ideal (x d , r 0 + xg β ), and X α and X β are isomorphic by Lemma 2.1.

Conversely, suppose that X α and X β are isomorphic and let ϕ be an automorphism of C[x, z, t] which fixes the ideal (x) and maps the ideal (x d , r 0 + xg α ) into the ideal (x d , r 0 + xg β ). Up to changing X β by its image under an isomorphism coming from an automorphism of C 3 of the type (x, z, t) → (µx, λ -ℓ z, λ -k t) as above, we may further assume that ϕ is a C[x]-automorphism of C[x][z, t] which is the identity modulo (x) and we are thus reduced to the following statement. "Suppose that there exists a C[x]-automorphism ϕ of C[x][z, t] which is congruent to the identity modulo (x) and such that ϕ(r 0 + xg α ) ∈ (x d , r 0 + xg β ). Then g α and g β are congruent modulo (x d-1 )."

Choose ν maximal such that ϕ is congruent to the identity modulo (x ν ). If ν ≥ d then we are done. So, suppose that ν ≤ d -1. Writing down that the Jacobian of ϕ is constant equal to 1, we remark that there exists a polynomial h ∈ C[z, t] such that ϕ(z) and ϕ(t) are congruent modulo (x ν+1 ) to z + x ν h t and to t -x ν h z , respectively. Consequently, we have ϕ(r 0 + xg α ) ≡ r 0 + xg α + x ν Jac(r 0 , h) modulo (x ν+1 ). On the other hand, since ϕ(r 0 + xg α ) ∈ (x d , r 0 + xg β ) and since, by definition, g α and g β contain no monomials of the form cx i1 z i2 t i3 with i 2 ≥ k -1 or i 3 ≥ ℓ -1, there exists a polynomial a ∈ C[z, t] such that ϕ(r 0 + xg α ) ≡ r 0 + xg β + x ν ar 0 modulo (x ν+1 ).

Writing xg α = m≥1 s α,m x m and xg β = m≥1 s β,m x m as before, we have thus

r 0 + ν-1 m=1 s α,m x m + x ν (s α,ν + Jac(r 0 , h)) ≡ r 0 + ν-1 m=1 s β,m x m + x ν (s β,ν + ar 0 ) modulo (x ν+1
). Since Jac(r 0 , h) and r 0 both belong to the ideal (z k-1 , t ℓ-1 ) of C[z, t], we conclude that s α,m = s β,m for every m = 1, . . . , ν and that Jac(r 0 , h) ∈ r . Since θ has Jacobian determinant equal to 1 (see [START_REF] Moser-Jauslin | Automorphism groups of Koras-Russell threefolds of the first kind[END_REF]), we deduce again from [START_REF] Van Den Essen | The special automorphism group of R[t]/(t m )[x 1 . . . , xn] and coordinates of[END_REF] that it lifts to a C[x]automorphism θ of C[x][z, t]. By construction θ ≡ ϕ modulo x ν+1 and since r 0 + xg α divides δ(r 0 + xg α ) = x ν (r 0 + xg α )Jac(r 0 + xg α , γ), it maps the ideal (x d , r 0 + xg α ) into itself. Thus

ϕ 1 = ϕ • θ -1 is a C[x]-automorphism of C[x]
[z, t] congruent to identity modulo x ν+1 which maps (x d , r 0 + xg α ) into (x d , r 0 + xg β ) and we can conclude the proof by induction.

An example of a non-extendible automorphism

Most of the algebraic results of the previous two sections can be generalized to the situation where r 0 ∈ C[z, t] defines a connected and reduced plane curve, provided that the Makar-Limanov and Derksen invariants of the corresponding threefolds are equal to C[x] and C[x, z, t] respectively. Here we illustrate a new phenomenon in a particular case where the zero set of r 0 is not connected.

For this section, we fix d = 2, r 0 = z(zt 2 + 1) and we let X be the smooth hypersurface in A 4 = Spec(C[x, y, z, t]) defined by the equation

P = x 2 y + z(zt 2 + 1) = 0.
Note that X is neither factorial nor topologically contractible. It is straightforward to check using the methods in [START_REF] Kaliman | AK-invariant of affine domains[END_REF] that Dk(X) = C[x, z, t] and ML(X) = C[x]. We will use the fact that the plane curve C 0 with equation r 0 = z(zt 2 + 1) = 0 has two connected components to construct a particular automorphism φ of X which cannot extend to the ambient space A 4 .

Starting from the polynomial h = zt 2 ∈ C[z, t], we first construct in a similar way as in [START_REF] Moser-Jauslin | Automorphism groups of Koras-Russell threefolds of the first kind[END_REF] an automorphism ϕ of C[x, z, t] as follows: Noting that the C[x]/(x 2 )-automorphism ϕ = exp(xJac(h, •)) of C[x]/(x 2 )[z, t] has Jacobian equal to 1, we deduce again from [START_REF] Van Den Essen | The special automorphism group of R[t]/(t m )[x 1 . . . , xn] and coordinates of[END_REF], that it lifts to a C[x]automorphism ϕ of C[x, z, t]. In other words, there exists an automorphism ϕ of C[x, z, t] with ϕ(x) = x and such that ϕ ≡ ϕ mod (x 2 ). One checks further using the explicit formulas that ϕ(z) = (1 -2tx)z, ϕ(t) = (1 + tx)t and that ϕ(r 0 ) = (1 -2xt)r 0 . So ϕ preserves the ideals (x) and J = (x 2 , z(zt 2 + 1)) and hence lifts to a C[x]-automorphism φ of the coordinate ring C[X] of X.

Proposition 5.1. The automorphism of X ⊂ A 4 determined by φ cannot extend to an automorphism of the ambient space.

Proof. Suppose by contradiction that there exists an automorphism Φ of C[x, y, z, t] which extends φ. Then there exists a constant λ ∈ C * such that Φ(P ) = λP and so we obtain a commutative diagram

C[x, y, z, t] Φ / / C[x, y, z, t] C[u] O O u →λu / / C[u] O O where C[u] → C[x, y, z, t] maps u onto P = x 2 y + z(zt 2 + 1) ∈ C[x, y, z, t].
Passing to the field of fractions of C[u], we see that Φ induces an isomorphism between the C(u)-algebras

A = C(u)[x, y, z, t]/(P -u) and A λ = C(u)[x, y, z, t]/(P -λ -1 u).
Now the key observation is that the Makar-Limanov and Derksen invariants of A and A λ are equal to C(u)[x] and C(u)[x, z, t] respectively (this follows from an application of Theorem 9.1 of [START_REF] Kaliman | AK-invariant of affine domains[END_REF] which in fact only requires that the base field has characteristic 0, we do not give the details here). Now since Φ induces an isomorphism between the Makar-Limanov invariants of A and A λ , it follows that Φ(x) = µx + ν for some µ ∈ C(u) * and ν ∈ C(u). From the fact that the ideal (x, P ) of C[x, y, z, t] is not prime, whereas the ideals (x + c, P ) are prime for all c ∈ C * , we can conclude that ν = 0 and since φ(x) = x, we eventually deduce that µ = 1. Thus Φ(x) = x. Next, noting that Φ induces an automorphism Φ of C[x, y, z, t]/(x) ∼ = C[y, z, t] with Φ(z(zt 2 + 1)) = λz(zt 2 + 1), we deduce that there exists α ∈ C * such that Φ(z) = αz. By comparing with φ(z), we find that α = 1. Thus Φ(zt 2 + 1) = zΦ(t) 2 + 1 = λ(zt 2 + 1) and by considering the constant terms in the last equality, we conclude that in fact λ = 1. Also, since ϕ(t) ≡ t mod (x), we have that Φ(t) ≡ t mod (x). Thus, Φ is congruent to the identity modulo (x). So Φ actually induces a C(u)[x]-automorphism of A and the observation made on the Makar-Limanov and Derksen invariants of A implies that the induced automorphism preserves the subring C(u)[x, z, t] of A and fixes the ideal (x 2 , r 0 -u). This implies that there exists H ∈ C[u][z, t] such that Φ(f ) ≡ f + xJac(H, f ) mod x 2 for every f ∈ C(u)[z, t]. Furthermore, since Φ is an extension of φ, the residue class of H in C[u][z, t]/(u) ≃ C[z, t] coincides with h + c for some c ∈ C. But on the other hand, one has Jac(H, r 0 -u) ∈ (r 0 -u) as the restriction of Φ fixes the ideal (x 2 , r 0 -u). Since r 0 -u is irreducible, this implies that H is, up to the addition of a polynomial in C[u], an element of the ideal (r 0 -u)C[u][z, t] and so its image in C[u][z, t]/(u) ≃ C[z, t] is a regular function on A 2 whose restriction to the curve C 0 = {r 0 = 0} is constant. This is absurd since by construction h + c = zt 2 + c is locally constant but not constant on C 0 . Remark 5.2. Note that there are many examples of non-extendible automorphisms of hypersurfaces. In this setting, for example, we showed in [START_REF] Dubouloz | Inequivalent embeddings of the Koras-Russell cubic threefold[END_REF] that the hypersurface in A 4 given by the equation

x 2 y + z 2 + t 3 + x(1 + x + z 2 + t 3 ) = 0, which is in fact isomorphic to the Russell cubic as a variety, admits automorphisms that do not extend to the ambient space. However, none of these non-extendible automorphisms fixes x. The present example exhibits a new phenomenon coming from the fact that the curve defined by r 0 = 0 is not connected. Note also that viewing X as a subvariety of A 1 × A 3 = Spec(C[x][y, z, t]) the restriction of the automorphism determined by φ to every fiber X s , s ∈ A 1 of the first projection pr x : X → A 1 actually extend to an automorphism of A 3 s : indeed, φ restricts to the identity modulo x and therefore the restriction of the corresponding automorphism to X 0 extends. On the other hand, the argument used in the proof of Lemma 2.1 shows immediately that the induced automorphism of X | A 1 \{0} extends to an automorphism of A 1 \ {0} × A 3 .

  Since an isomorphism between A(g) and A(f ) preserves the Makar-Limanov and the Derksen invariants, it restricts to an automorphism ϕ of C[x, z, t] and an automorphism of C[x]. That is, ϕ(x) is of the form ax + b where a ∈ C * and b ∈ C. Actually, b = 0 since by the previous remark the zero set of ax + b in X(f ) and X(g) is non isomorphic to A 2 if and only if b = 0

  0 C[z, t]. This implies in turn that h = γr 0 + c for some γ ∈ C[z, t] and c ∈ C. Now consider the C[x]/(x d )-automorphism θ = exp(δ) of C[x]/(x d )[z, t] associated with the derivation δ = x ν Jac(•, γ(r 0 + xg α ))

This research was supported in part by the ANR Grant BirPol ANR-11-JS01-004-01.