Fabien Labernia
email: fabien.labernia@lamsade.dauphine.fr

Bruno Zanuttini
email: bruno.zanuttini@unicaen.fr

Brice Mayag
email: brice.mayag@lamsade.dauphine.fr

Florian Yger
email: florian.yger@lamsade.dauphine.fr

Jamal Atif
email: jamal.atif@lamsade.dauphine.fr

Online learning of acyclic conditional preference networks from noisy data

We deal with online learning of acyclic Conditional Preference networks (CP-nets) from data streams, possibly corrupted with noise. We introduce a new, efficient algorithm relying on (i) information-theoretic measures defined over the induced preference rules, which allow us to deal with corrupted data in a principled way, and on (ii) the Hoeffding bound to define an asymptotically optimal decision criterion for selecting the best conditioned variable to update the learned network. This is the first algorithm dealing with online learning of CP-nets in the presence of noise. We provide a thorough theoretical analysis of the algorithm, and demonstrate its effectiveness through an empirical evaluation on synthetic and on real datasets.

I. INTRODUCTION

Preference representation, reasoning (e.g. [START_REF] Sandholm | Expressive commerce and its application to sourcing: How we conducted $35 billion of generalized auctions[END_REF]- [START_REF] Walsh | Representing and reasoning with preferences[END_REF]), and learning (e.g. [START_REF] Chevaleyre | Learning ordinal preferences on multiattribute domains: The case of cp-nets[END_REF], [START_REF]Preference Learning[END_REF], [START_REF] Koriche | Learning conditional preference networks[END_REF]), are receiving increasing attention in the literature, in particular within the context of recommender systems. In this paper, we address the problem of learning combinatorial preferences, and more precisely, learning acyclic conditional preference networks (CPnets) [START_REF] Boutilier | Cp-nets: A for representing and reasoning with conditional ceteris paribus preference statements[END_REF].

CP-nets constitute a preference representation language based on ceteris paribus ("all other things being equal") comparisons, that is, comparisons of objects which differ over only one attribute. Such comparisons are arguably cognitively simpler than general ones, and CP-nets leverage this principle for factorizing the preferences over each attribute (or variable), leading to compact graphical representations.

Learning CP-nets, even by adding acyclicity constraints, is an NP-Complete problem [START_REF] Chevaleyre | Learning ordinal preferences on multiattribute domains: The case of cp-nets[END_REF]. Some works try to solve this problem by considering consistent preferences 1 , e.g. regression-based learning [START_REF] Eckhardt | How to learn fuzzy user preferences with variable objectives[END_REF], [START_REF] Eckhardt | Learning user preferences for 2cp-regression for a recommender system[END_REF], [START_REF] Liu | Representing conditional preference by boosted regression trees for recommendation[END_REF], learning by reduction to 2-SAT [START_REF] Dimopoulos | Ceteris paribus preference elicitation with predictive guarantees[END_REF], [START_REF] Michael | An empirical investigation of ceteris paribus learnability[END_REF] and learning using user queries [START_REF] Chevaleyre | Learning ordinal preferences on multiattribute domains: The case of cp-nets[END_REF], [START_REF] Guerin | Learning cp-net preferences online from user queries[END_REF], [START_REF] Koriche | Learning conditional preference networks[END_REF]. Recently, [START_REF] Liu | Learning conditional preference networks from inconsistent examples[END_REF], [START_REF] Liu | Learning conditional preference network from noisy samples using hypothesis testing[END_REF] considered the problem of learning CP-nets from noisy data. We call noise (also called incoherence or inconsistency in other papers) an observed preference opposite to the real one, that is, observing "the user prefers a to b" whereas her true preference is "I prefer b to a". Noise can be caused by many factors: distracted user, corrupted data, unobserved variables, etc. 1 i.e. the opposite preference is never observed (in the binary case).

In addition to noise, we consider an online setting, where observations (data) arrive as a stream and cannot be memoized, as in recommender systems where they could be generated by user clicks. In that sense, our approach differs from most of the literature: we consider the target CP-net to reflect the global preferences of a set of users, with variations among different users' preferences seen as noise w.r.t. this global relation.

Noise and onlineness of course make the problem more complex, and call for an algorithm that can maintain a best hypothesis about the target CP-net, given the observations received so far. The only online algorithm we know for solving this problem is a query-based algorithm [START_REF] Guerin | Learning cp-net preferences online from user queries[END_REF]. We give experimental results comparing our approach to this one. To summarize, we propose a new, efficient, and robust to noise online algorithm for learning acyclic CP-nets on binary variables, as illustrated in Fig. 1. Our aim is to come up with a learning procedure that can be used in a recommender system. The algorithm observes a stream of pairwise preferences between two ceteris paribus objects, and learns an acyclic CPnet which maximizes the agreement with the observations. We support our claim by theoretical guarantees and experimental results on synthetic and real data.

II. CONDITIONAL PREFERENCE NETWORKS (CP-NETS)

Let V be a set of binary variables, with each V ∈ V associated with a domain Dom(V ) = {v, v }. For V ⊆ V, we write Dom(V ) = V ∈V Dom(V ), and call state an element v of Dom(V ). Complete states, that is, elements o of Dom(V), are called outcomes, and constitute the objects over which preferences are expressed.

For states v ∈ Dom(V ), v ∈ Dom(V ) with V ∩V = ∅, we write v v ∈ Dom(V ∪ V ) for their concatenation. We also use the notation v v for the extension of state v ∈ Dom(V ) by the value v ∈ Dom(V ) (where V ∈ V, and V ⊆ V \ {V }). Finally, o[V ] denotes the projection of the outcome o onto the variables in V .

A (strict) preference relation is a partial order on Dom(V). o o should be read "outcome o is strictly preferred to outcome o ". We call ceteris paribus pair (CPpair), denoted by (o, o ) V , a pair of outcomes which differ only over

V (in formulas, o[V \ {V }] = o [V \ {V }]).

Let

be a strict preference relation on Dom(V) and X, Y ∈ V. Variable X is said to be a parent of variable Y if there is a context in which X alone changes the preference over the values of Y ; precisely, if there is a state z ∈ Dom(V \ {X, Y }) satisfying zxy zxy and zx y zx y (or zxy zxy and zx y zx y ). CP-nets are built on this notion. A CP-rule for variable

V with domain Dom(V ) = {x, x } is a rule of the form r = (u : v v ), or r = (u : v v), with u ∈ Dom(U) for some U ⊆ V. The semantics of r is that o o must hold for all CP pairs (o, o ) V such that o[U] = o [U] = u and o[V ] = x, o [V ] = x ;
the semantics of r is the opposite. A CP-table for V is a collection of CP-rules for V , all sharing the same parent set U, with at most one rule r u or ru per state u ∈ Dom(U). The set U is also written P a(V ), as it indeed corresponds to (a redundant superset of) the set of parent variables of V in the induced relation. Finally, given two opposite rules r u and ru , we define the notation of a global rule as follow.

Definition 1 (Rule schema). Let r u and ru be two opposite rules on V ∈ V. R = (u : V ) denotes the common rule schema of r u and ru , where the preference over the assignment of V is not specified.

Definition 2 (Conditional preference network

). A condi- tional preference network (CP-net) is a triple N = (V, A, CP T (V ) V ∈V ), where (V, A) is a directed graph on the set of variables V, and for all V , CP T (V ) is a CP-table for V with P a(V ) = {X ∈ V, (X, V ) ∈ A}.
The preference relation N induced by a CP-net N is the transitive closure of the relation induced by all rules in the CP-tables of N . It is known that if the digraph (V, A) associated with N is acyclic, then the relation N is consistent (irreflexive). We focus on such acyclic CP-nets in this work.

We say that a binary CP-net is

complete if ∀V ∈ V, |CP T (V )| = 2 |P a(V )|
. Otherwise, we say that the CP-net is incomplete.

Fig. 2 depicts an example of a CP-net, which contains four variables A, B, C, D with three sets of independent variables {A, D}, {B, D}, {C, D}, and one variable B conditioned by A and C. We have, for example, a b cd a bcd (bottommost rule) and a bcd abcd (top left rule), and hence a b cd abcd (by transitivity).

A B C a ′ ≻ a a ′ c : b ′ ≻ b ac : b ≻ b ′ c ≻ c ′ ac ′ : b ≻ b ′ a ′ c ′ : b ′ ≻ b D d ≻ d ′

III. THE LEARNING PROBLEM

We consider the problem of learning a CP-net from observations of the form o o , where (o, o) V forms a CP pair. Such preferences are natural since they correspond to statements like, e.g., "I would prefer this car in blue color than in red color". We consider a stream Ω of observations, and our aim is to learn, at all times t (i.e., after receiving t observations), an acyclic learned CP-net N t L maximizing an accuracy measure L w.r.t. Ω t (the stream restricted to its first t observations).

We choose the following, natural agreement measure, which is also used in [START_REF] Liu | Learning conditional preference network from noisy samples using hypothesis testing[END_REF]:

L(Ω t , N t L ) = |{(o o ) ∈ Ω t | o N t L o }| t . (1)
In words, we seek to maximize the number of comparisons in the stream which the learned CP-net correctly predicts.

Since Ω may contain some noise, i.e. observations o o and o o for the same CP pair (o, o ) V , we cannot hope to achieve perfect accuracy (Eq. ( 1)) in general. This would only fit the noise and result in an inconsistent (reflexive) learned preference relation. Furthermore, the problem of testing the consistency of a cyclic CP-net is known to be PSPACEhard [START_REF] Koriche | Learning conditional preference networks[END_REF]. For these reasons, we require acyclicity, and hence consistency, for the learned CP-net, which can be seen as a regularization bias. Fig. 3 gives a formal definition of our problem.

Input:

a data stream Ω of ceteris paribus pairwise comparisons Ouput:

an acyclic CP-net N L Measure: maximize Eq. (1) (under acyclicity)

IV. PROPOSED ALGORITHM FOR LEARNING A CP-NET

To cope with noise and maximize agreement with the observed data, the algorithm chooses, for each rule schema R = (u : V ), the rule r u or the rule ru to be the one which corresponds to the greatest number of observations received so far. Hence our algorithm relies on identifying good rule schemas and for each one, on maintaining estimates of the number of received observations in favor of r u and ru . For the latter objective, we use estimated counters which are maintained online.

The high-level procedure is shown in Algorithm 1 (the learned CP-net N L is a global variable that is not included as a parameter). This procedure processes the observed CPcomparisons online: for each new one, it generates a CP-rule (which always exists) by using the received swap (from which we deduce the preference), and the parents of the current variable in the CP-net (the conditioned part of the CP-rule). Then, it updates all counters with respect to the comparison and decides whether it is necessary to add a new parent variable or not (Line 5). Algorithm 1 also needs to set the maximum number of parents for each conditioned variable. If so, it finds the best new parent variable, and updates all the counters (Line 6). We describe all these steps in details in the rest of this section.

Algorithm 1: learningCPNet()

Data: A data flow Ω, a parent bound k, and a trust probability δ. Result: A learned CP-net N L . 1 Initialize N L and all counts to 0;

2 for (o, o ) V ∈ Ω do 3 Let r = (u : o[V ] o [V ]
) be the CP-rule induced by (o, o ) V with u ∈ Dom(P a(V )) and R its associated rule schema; For the sake of clarity, we use the following notation. For a rule schema R = (u : V ), a new parent variable P ∈ V \ ({V } ∪ P a(V )) and a value p ∈ Dom(P ), we write R p for the "extended" rule schema (up : V ). Similarly, given a CP-rule r = (u : v v ) (resp. r = (u : v v)), we write r p for the rule (up : v v ) (resp. rp for (up : v v)). Finally, we denote the set of all nonparent variables of a variable V by P a(V ) (i.e., P a(V ) = V \ (P a(V ) ∪ {V })).

A. Counters

Definition 3 (Rule counter). Let V ∈ V be a variable and R ∈ CP T (V ) a rule schema. We call rule counter the number of observed swaps that support the CP-rule r (resp r), which is denoted by c(r) (resp. c(r)).

Definition 4 (Nonparent counter). Let V ∈ V be a variable, R ∈ CP T (V ) a rule schema, and X ∈ P a(V ). We call nonparent counter the number of observed swaps

(o, o ) V that support the CP-rule r with o[X] = x (resp o[X] = x ),
which is denoted by c(x r ) (resp. c(x r )). We define in the same way the nonparent counter for the opposite rule r, with c(x r ) (resp. c(x r )).

In an online setting, we cannot memorize each received observation, not even a counter for each of them since the data stream can be infinite. Hence we use rule counters (Definition 3) and nonparent counters (Definition 4) that are maintained online. Precisely, for each rule schema R = (u : V ) in the current learned CP-net N L , it maintains an estimate c(r) (resp. c(r)) of the number of observed CP-comparisons that support the rule r = (u :

v v ) (resp. r = (u : v v)), where o o supports (u : v v ) if (o, o ) V is a CP-pair and o[P a(V )] = u, o[V ] = v, o [V ] = v hold.
Moreover, for each nonparent variable X ∈ P a(V ) with domain {x, x }, the algorithm maintains estimates c(x r ), c(x r ), c(x r ), and c(x r )). For instance, the counter c(x r ) estimates the number of observed comparisons o o that support r and satisfy o

[X] = o [X] = x.
Observe that we only need m(4n + 2) counters for a CP-net N L containing m rules over n variables. The estimation of the updated counters is described in the sequel.

B. Parent decision phase

The parent decision phase consists in deciding whether a variable needs a new parent (for maximizing the agreement), and draws inspiration from the stochastic multi-armed bandit problem [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF].

To each variable V we associate a value of "information gain", representing to what extent it would be worth adding a new parent to V . Intuitively, V needs a new parent when there are many states u ∈ Dom(P a(V )) such that there are the same number of observations supporting the CP-rule u : v v and the rule u : v v. More precisely, for each rule schema R for V (over its current set of parents P a(V )) with associated CP-rules r, r, we call R impure if both c(r) and c(r) are nonzero and equal (otherwise, the rule schema is pure when just one of the counters is equal to zero. Then the current set P a(V ) is clearly sufficient). We then measure a degree of impurity using Shannon's entropy [START_REF] Cover | Elements of information theory[END_REF]. Let f (r) = c(r) c(r)+c(r) and f (r) = c(r) c(r)+c(r) measure the relative (estimated) frequencies of observations supporting r and r. Then we define

E(R) = 0, if c(r) = 0 or c(r) = 0, -f (r) log(f (r)) -f (r) log(f (r)), otherwise.
(2) To aggregate impurity of all rules for a given variable V together, we simply define the "information gain" of V to be:

G(V ) = R∈CP T (V ) f R E(R), (3)
with f R = c(r)+c(r) R ∈CP T (V) c(r ) + c(r )
the estimated frequency of the rule schema R among all rule schemas of N (computed from the counters).

Obviously, in an online and noisy setting, we do not want to add one parent at each step, since the algorithm would overfit noise. Intuitively, the decision needs to be supported by sufficiently many observations, and for this we use Hoeffding's bound (also called "additive Chernoff's bound") [START_REF] Domingos | Mining high-speed data streams[END_REF], [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF], [START_REF] Maron | Hoeffding races: Accelerating model selection search for classification and function approximation[END_REF]. Let |Y | be the range of a (real-valued) random variable Y , assume that we have observed m realizations of Y 's observations, and write

= |Y | 2 ln 1 δ 2m . (4)
Then, Hoeffding's bound states that the mean of the observations is in [ỹ -, ỹ + ] with a probability 1δ, where ỹ is the true mean of the values in Y . Back to our algorithm, we consider the mean of the information gains of a variable V as computed after seeing each of m comparisons on V :

Gm V (V ) = 1 m V m V i=1 G i (V ), (5)
with m V the number of times we have observed comparisons on V (i.e., CP-pairs (o, o ) V ), and G i (V ) the information gain computed for V after seeing the i th comparison on V (we can see this mean as a way to give more importance to the current gain). Following Hoeffding's bound, if V is a variable such that it has the highest observed Gm V (V ) after seeing m V comparisons, we decide to select V as a conditioned variable if and only if

Gm V (V ) > m V (6)
holds, with |Y | = log(2), m = m V and δ ∈]0, 1] a hyperparameter (i.e. a parameter which is fixed by the user) in Eq. 4. That is, if observations are drawn i.i.d. and up to the estimation induced by the counters, variable V is indeed the best choice with a probability of 1δ. The intuition behind Eq. 4 is to look for a conditioned variable which has a sufficient entropy while enough swaps have been seen. For more details, the reader can refer to [7, Section 2].

Algorithm 2: update CPTable(V, R, r, o) Data: A variable V , a CP-rule r with its associated rule schema R, and an outcome o. Result: Update each corresponding counter.

1 c(r) ← c(r) + 1; 2 for X ∈ P a(V ) do 3 if o[X] = x then c(x r ) ← c(x r ) + 1; 4 else c(x r ) ← c(x r ) + 1;
5 Update the nonparent variable relevance Eq. ( 7);

6 if c(r) > c(r) and r ∈ CP T (V ) then 7 CP T (V ) ← (CP T (V ) \ {r}) ∪ {r}; 8 if c(r) < c(r) and r ∈ CP T (V ) then 9 CP T (V ) ← (CP T (V ) \ {r}) ∪ {r}; C. Parent search phase
Once the algorithm has decided to add a parent to a variable V with domain {v, v }, the parent search phase consists of finding the best new parent. By definition, a parent variable P of V is characterized by having, in at least one context u, value p when v is preferred to v , and the other value p when v is preferred. Hence for r = (u : v v ) and Dom(P ) = {p, p } we should observe either (i) many comparisons supporting r p = (pu : v v ) and many supporting rp = (p u : v v), or (ii) many supporting r p and many supporting rp . Then, using the counters, we define the relevance of each nonparent variable X of V :

rel(X, V ) = 1 |CP T (V )| R∈CP T (V ) max(C, C) c(r) + c(r) , (7)
where C = c(x r ) + c(x r ) and C = c(x r ) + c(x r ), with c(r) + c(r) a normalization value. This relevance can be gradually updated without browsing all CP-rules (Line 5 of Algorithm 2). We can see that 1 2 ≤ rel(P, V ) ≤ 1. However, the worst case for a parent candidate P is, for each of these assignments and each type of a CP-rule, to observe the same counters, i.e. rel(P, V ) = 1 2 . Then, the algorithm only accepts variables that have rel(P, V ) > 1 2 . Finally, the best parent variable for V is defined by

argmax P ∈Acy(P a(V )) rel(P, V ), s.t. rel(P, V ) > 1 2 , (8)
(breaking ties arbitrarily), where Acy restricts the candidate to those whose addition induces no cycle in the digraph of N L (which can be computed in time linear in the size of the digraph).

D. Updating rules and counters

When no parent is added, updating the counters simply consists of incrementing by 1 those supported by the just received observation, and for each rule schema R in N L we only need to check which of c(r) and c(r) is highest.

Contrastingly, when P is chosen as a new parent of V , we need to update all rule schemas in CP T (V ) and their corresponding counters. Let R = (u : V ) be a schema with rules r, r, and let P be a new parent variable for V . By definition of c(p r ), we can compute the new counter for r p by c(r p ) = c(p r ),

and similarly for rp , r p , rp . We however also need

These bounds bring us to obtain c -(b r p ) ≤ c * (b r p ) ≤ c + (b r p ). We conservatively choose the lower bound c -(.) (Equation ( 10)), which is the estimated new counter on the overlap between the counter for the nonparent variable B as associated to R, and the new parent P as associated to R (and similarly for value b of B and rules r p , rp , rp ). This estimation is the price to pay for the online setting. However, all counters are used after seeing m V swaps (Eq. ( 4)) for the variable V , then the error made by this conservative bound is statistically corrected with a sufficient probability (see Section V). Moreover, this is the only place where an estimation occurs, and we show in our experiments that this works well in practice. Algorithm 3 summarizes the whole procedure.

Algorithm 3: addParent(CP T (V )) Data: The CP-table CP T (V ).
Result: Update, if it is possible, the parents of V . 1 Choose P by applying Eq. ( 8);

2 if P exists then 3 P a(V ) ← P a(V ) ∪ {P }; 4 for R ∈ CP T (V ) do 5
Replace R by R p and R p ; 6 Update all new CP-rules (Eq. ( 9)) and nonparent variables (Eq. ( 10)) counts; 6) is False, so no parent is added. Then we handle a bc a bc. Let r = (∅ : c c ) and r = (∅ : c c). We have the best information gain with variable C, with G2 (C) ≈ 0.15 > ≈ 0.13. Hence we add a parent to C so as to split the CP-rule into two distinct ones. We have rel(A, C) = 1 and rel(B, C) = 1 2 , hence we choose A and update the counters of all new CP-rules using Eq. ( 9) and Eq. [START_REF]Preference Learning[END_REF]. The learned CP-net N L now contains two CPrules: {a : c c , a : c c}. We finally handle a b c a b c and update all counters. Ineq. ( 6) is False and the algorithm stops. We obtain a CP-net which contains two CP-rules, which (in this small example) perfectly fit the observations.

7 CP T (V ) ← CP T (V ) \ {r, r}; 8 if c(r p ) > c(r p ) then 9 CP T (V ) ← CP T (V ) ∪ {r p }; 10 if c(r p ) < c(r p ) then 11 CP T (V ) ← CP T (V ) ∪ {r p }; 12 if c(r p ) > c(r p ) then 13 CP T (V ) ← CP T (V ) ∪ {r p }; 14 if c(r p ) < c(r p ) then 15 CP T (V ) ← CP T (V ) ∪ {r p }; 16 rel(V, V ) ← 0, ∀V ∈ P a(V );

V. THEORETICAL RESULTS

We remind that we denote by Ω the dataset which contains a set of swaps. This section begins by a proof of the soundness and the completeness of our algorithm.

Proposition 1 (Soundness). Algorithm 1 always returns an acyclic CP-net (which is possibly incomplete) for any dataset Ω.

Proof. By construction: each arc added between two variables corresponds to a parent link (Line 3 of Algorithm 3) with a duplication of all CP-rules of the current variable w.r.t. the values of the new parent (Line 5 of Algorithm 3). Furthermore, the acyclic property is verified once Algorithm 3 adds a parent (Eq. ( 8)). Finally, the only objects that are added to the CPtables are CP-rules (Line 6 of Algorithm 3), which verify the definition of an acyclic CP-net, and prove the soundness of Algorithm 1.

Definition 5 (Restriction of a CP-net). Let (<, V 2 ) be an order on the arcs in the digraph of a CP-net N . For a current arc (P 0 , V 0 ), we denote by N (P0,V0) the restriction of N for the relation (P, V ) < (P 0 , V 0 ), i.e. N contains only the arcs that have a lower position in (<, V 2 ) (including (P 0 , V 0 )), where the restriction is defined by:

(i) ∀V ∈ V, if P a (P0,V0) (V ) = P a(V ), then CP T (P0,V0) (V ) = CP T (V ); (ii) if P a (P0,V0) (V ) ⊂ P a(V ), then (u : v v ) ∈ CP T (P0,V0) (V )
if and only if the majority of rules in N has the form (uw : v v ), where u ∈ P a (P0,V0) (V ), and w ∈ P a(V ), w ∈ P a (P0,V0) (V ). Definition 6 (Exact counter). We call exact counter for a CPnet N and a set of swaps Ω the actual number of times each rule and nonparent counter has been observed on Ω so far. Definition 7 (Information gain consistency). Let (<, V 2 ) be an arc ordering on V, and a set of swaps Ω. (<, V 2 ) is information gain consistent w.r.t. Ω if, by using the exact rule counters of N (P0,V0) and Ω:

(i) (P, V ) is the successor of (P 0 , V ) in (<, V 2 ), where V is the variable that maximizes the information gain among all variables that have missing parents; (ii) ∀(P, V ) in the digraph of N , (P, V ) < (P , V ) in (< , V 2 ), where P ∈ P a(V ) in N ;

(iii) let (P last , V last ) be the last arc in (<, V 2 ) to complete the digraph of N , then ∀V ∈ V, G(V ) = 0 for N (P last ,V last ) .

Lemma 1. There always exists an order (<, V 2 ) which is information gain consistent for acyclic CP-nets.

Proof. We construct an order (<, V 2 ) such that ∀(P, V ) with P ∈ P a(V ) and ∀(P , V ) with P ∈ P a(V ), (P, V ) < (P , V ).

The point (i) of Definition 7 is verified by ordering and adding in a decreasing way following the values of information gain of all the arcs (P, V ). The arcs (P , V ) are considered only after the arcs (P, V ): it means that all variables in V already have their parents, so their information gains are equal to 0, which verify the point (iii). Finally, the point (ii) is verified by the construction of (<, V 2 ).

Intuitively, Lemma 1 says that the order (<, V 2 ) corresponds to the order where the algorithm has the highest probability to learn the relations.

The Hoeffding bound gives us a trust probability (1δ) which bounds all of the counters and information gains. Then, Algorithm 1 chooses the new parent variables following (< , V 2 ) with the trust probability (1δ). Finally, the algorithm will learn the appropriate structure since it will not add any parent after the arc (P last , V last ) (point (iii) of Definition 7), which exactly corresponds to the set of parents of N * (point (ii) of Definition 7).

Definition 8 (relevant consistency). Let (<, V 2 ) be an order on arcs in the digraph of a CP-net N and a set of swaps Ω. (<, V 2 ) is relevant consistent w.r.t. Ω if, by using the exact nonparents counters into N (P0,V0) , (P, V ) is the successor of (P 0 , V 0 ) in (<, V 2 ), ∀(P 0 , V 0 ) < (P last , V last ), where P is the parent that maximizes the value of rel(P, V ). Lemma 2. There always exists an order (<, V 2 ) which is information gain and relevance consistent w.r.t. a set of swaps Ω.

Proof. Consider the order constructed in the proof of Lemma 1. We extend this order:

(P 1 , V 1 ) < (P 2 , V 1 ) < . . . < (P k1 , V 1 ) < . . . < (P 0 , V 0 ) < . . . < (P last , V last ) < (P , V ), ∀(P , V ) s.t. P ∈ P a(V ), where k 1 is the k th parent of V 1 ,
and ∀i, j, l s.t. i < j, rel(P i , V l ) > rel(P j , V k ). This extension verifies by construction the Definition 8, and is still compatible with Lemma 1 due to the independence of P in the information gain of V . Lemma 3. Let an unnoised set of swaps Ω be a dataset which induces the optimal batch CP-net N * . If the counters used in Algorithm 1 are exact, then it learns all arcs (P, V ) of N * for an information gain and relevance consistent order (<, V 2 ).

Proof. Let N L the CP-net learned by Algorithm 1. We denote by (P, V ) ∈ N * the arcs that are in the digraph of N * . Suppose by induction that Algorithm 1 had already learned all arcs before (P, V ) following (<, V 2 ), and the next arc is (P 0 , V 0 ) (the initialization trivially works if we set |V| = 1). Two cases occur:

• V 0 needs no parent, so G(V 0 ) = 0. Furthermore, Algorithm 1 selects the variable which maximizes Eq. ( 3), then ∀V ∈ V \ {V 0 } and ∀P ∈ P a(V ), (P 0 , V 0 ) < (P , V ) and G(V ) = 0;

• V 0 needs the parent P 0 . Then, rel(P 0 , V 0 ) > 1 2 , and Algorithm 1 chooses the variable P which maximizes, after choosing V 0 the value of rel(P, V 0 ) (Eq. ( 7)). Then, for P = P 0 and ∀P ∈ P a(V 0 ) \ {P 0 }, rel(P 0 , V 0 ) > rel(P , V 0 ). The arc (P 0 , V 0 ) corresponds to the successor of (P, V ) in the order (<, V 2 ), which proves the lemma.

A direct consequence of Lemma 3 is that for an unnoised dataset Ω, Algorithm 1 can learn the corresponding target CPnet N * following the agreement measure defined in Eq. [START_REF] Alanazi | The complexity of learning acyclic cp-nets[END_REF]. It also proves the completeness of Algorithm 1. Another corollary of Lemma 3 is that the corresponding batch algorithm which receives all swaps between each adding parent phase can also learn the target CP-net N * , even for a noisy dataset Ω (with a noise probability lower than 1 2 ). Definition 9 (Arc disagreement). Let N and N be two CPnets respectively associated to two different learning algorithms A and A . We define the arc disagreement, denoted by d a (N (P,V ) , N (P ,V ) ) as the probability that d a (N (P,V ) , N (P ,V ) ) = P(V = V )P(P = P )P(c = c ), where (P, V ) and (P , V ) respectively denote the new arc of N learned by A, and the new arc of N learned by A , and c, c denote the disagreement between the counters of both CP-nets after adding the corresponding arc.

Intuitively, Definition 9 expresses the probability of having, when the Hoeffding bound is used to find a new parent variable, a difference between two CP-nets: the conditioned variable, the parent variable, and/or the counters can differ. It is then easy, from this probability and the fact that an algorithm can only learn nk different parents ( n(n-1) 2 with acyclicity constraint), to deduce the whole disagreement which is made by two different learning algorithms on two different CP-nets.

Definition 10 (CP-net disagreement). The CP-net disagreement between two CP-nets N and N , denoted by d c (N , N ), corresponds to the sum of arcs disagreement for all possible arcs, i.e.

d c (N , N ) = nk i=1 P((P, V ) = (P , V )),
where n is the number of variables in the CP-nets and k the maximum number of parents per variable (modulo the acyclicity constraint).

Roughly speaking, these two previous definitions express the probability of an algorithm to learn the optimal structure and preferences compared to the optimal learning algorithm. In our case, the batch algorithm is considered as the optimal one, which allows us to deduce the following learning bound. Theorem 1. Let A be the batch algorithm of Algorithm 1, N * its learned CP-net, and N the learned CP-net of Algorithm 1.

Let Ω be an infinite noisy dataset (set of swaps) with p < 1 2 the associated noise probability.

Algorithm 1 has a CP-net disagreement equal to d c (N , N ) ≤ pnk(4n-2)δ3 2 k+1 m , with n the number of variables, k the maximum number of parents per variable, δ the Hoeffding probability, and m the necessary number of swaps before the adding parent phase (we suppose here that m V = m, ∀V ∈ V).

Proof. Let ( P , V ) and (P * , V * ) be, respectively, the arc added in N by Algorithm 1, and the arc adding in N * by the batch algorithm A.

We firstly compute the probability of the arc disagreement between N( P , V ) and N * (P * ,V * ) : • by the Hoeffding bound and the Lemma 3, we have P( V = V * ) ≤ δ; • in the same manner, we have P( P = P * ) ≤ δ;

• the counters are estimated by the Łukaciewicz norm, but can be refined by the Hoeffding bound: after m observed examples, the mean of seeing each form of CP-rule is m 2 k+1 multiply by (i) the number of counters in one rule schema (4n -2) and (ii) by the original Hoeffding probability δ. Then we obtain P(ĉ = c * ) ≤ (4n-2) 2 k+1 δ m . We can deduce the probability of the arc distance:

d a ( N( P , V ) , N * (P * ,V * ) ) = P( V = V * )P( P = P * )P(ĉ = c * ) ≤ δ 2 (4n -2) 2 k+1 δ m = (4n -2)δ 3 2 k+1 m .
Then, by using the union bound, we find the whole disagreement for all of the arcs that can be added during the learning phase:

d c ( N , N * ) = nk i=1 P(( P , V ) = (P * , V * )) = nk i=1 P( V = V * )P( P = P * )P(ĉ = c * ) ≤ nk i=1 δ 2 (4n -2) 2 k+1 δ m = nk(4n -2)δ 3 2 k+1 m .
Finally, we apply the noise probability p of the dataset Ω to obtain the result which proves the theorem:

d c ( N , N * ) ≤ pnk(4n -2)δ 3 2 k+1 m .
Theorem 1 shows that the disagreement polynomially increases following the number of variables n and the maximum number of parents per variable k.

Moreover, it is easy to see that the time complexity of the whole procedure after an observation has been received is in O(mn), where m is the number of rules in the current learned CP-net N L (the size of N L is in O(mn)). Since it is easy, and reasonable, to further impose that the learned CP-net has a digraph with a small degree k (see the experiments), and hence that m is in O(n k ), we finally get an efficient learning algorithm for acyclic CP-nets in an online and noisy setting (for more details about the complexity of learning acyclic CPnets, we refer the reader to [START_REF] Alanazi | The complexity of learning acyclic cp-nets[END_REF]).

VI. EXPERIMENTAL RESULTS

To evaluate the efficiency of our algorithm, three experimental protocols have been designed: the first one aimed at testing the accuracy with presence of noise, the computational time and the experimental convergence of our procedure. The second one consists in testing our algorithm on real datasets. Finally, the last one concerns the comparison between our algorithm and the online procedure proposed by [START_REF] Guerin | Learning cp-net preferences online from user queries[END_REF].

We made these experiments on a laptop with an Intel core i7-4600U, 16Go of RAM and Python language 2 .

In all of the graphics in the sequel, each point corresponds to a simple averaged value according to 30 runs, with a report of the standard deviation as an error bar on these points. We use Eq. ( 1) as accuracy measure.

A. Learning from synthetic noisy datasets

We consider an uniform random noise (it is appropriate to use the Hoeffding bound) represented by a probability p ∈ [0, 1]. 3 This amounts, for each pairwise comparison, to reverse at random the true preference with a probability p in order to represent the corrupted preferences. To generate our synthetic dataset Ω , we proceed as follow:

1) compute a random acyclic CP-net N T with n variables following Algorithm 3 in [START_REF] Guerin | Learning cp-net preferences online from user queries[END_REF] (we firstly generate random links between variables, then we generate random preferences for each CP- The first experiment is designed to assess the robustness of the algorithm w.r.t. noise. Fig. 4 depicts the algorithm's accuracy as a function of the amount of noise affecting the dataset. The algorithm shows that the accuracy varies following the given noise rate. We can also observe an overfitting of our structure when the number of parents is too high, with a decreasing accuracy. Fig. 5 is obtained by learning a CP-net N L from a noiseless dataset Ω and computing the error rate 1-L(N L , Ω) (Eq. ( 1)). We corrupt Ω with various noise levels (denoted by Ω ), and learn a new CP-net N L from it. We compute the error rate using the original dataset, i.e., 1 -L(N L , Ω). Finally, the error rate from noiseless and the one from noisy dataset are subtracted to obtain the points in Fig. 5. The obtained error rate does not reflect the true one, and induces a bias in the graphic lines because we cannot perfectly learn the CP-net. Again, the algorithm demonstrates a quite good robustness to noise, depending on the hyperparameter value δ. Fig. 6 reveals a lack of efficiency for values of δ less or equal to 0.8. For higher values, the algorithm allows for adding more new parent variables, which amounts to increase the accuracy scores. Fig. 7 shows the convergence of our algorithm. Note that we compute here the error rate after each iteration of Line 2 in Algorithm 1. One can observe that this error decreases drastically at the first steps, and continue decreasing smoothly as soon as new pairwise comparisons are acquired.

Finally, the computation time is given by Fig.

B. Learning from a real dataset

We consider in this section the TripAdvisor4 dataset [START_REF] Wang | Latent aspect rating analysis on review text data: a rating regression approach[END_REF], [START_REF] Wang | Latent aspect rating analysis without aspect keyword supervision[END_REF], which contains about 81, 000 hotel reviews (from 1, 850 different hotels) represented by seven ratings (value aspect, rooms aspect, location aspect, cleanliness aspect, check in/front desk aspect, service aspect and business service aspect) plus one overall rating (which represents the preference relation). To be able to learn a binary CP-net, we compute, for each hotel, its median review, and we rescale it with the median values in order to obtain the median binary review for each hotel (for more details, see the procedure described in [START_REF] Liu | Learning conditional preference network from noisy samples using hypothesis testing[END_REF]Subsection 5.1]).

One of the limits of CP-nets is that cycles of size 2 between two ceteris paribus outcomes cannot be represented (even for cyclic CP-nets). However, such a cycle can occur in real life, and deteriorates the algorithm's learning accuracy. Hence, we do not use these 2-cycles in this experiment. We can observe from Fig. 9 that without 2-cycles, we can learn the whole structure with about 99% of accuracy (the remaining 1% may correspond to the noisy part of the comparisons). Moreover, we can see that there are not many conditional preferences in this dataset (we have less than 1% of accuracy difference between the unconditional network and the complete CP-net). We also can observe that the size of the TripAdvisor dataset does not affect the accuracy.

C. Comparison with Guerin et al.

In order to reproduce the experiments in [START_REF] Guerin | Learning cp-net preferences online from user queries[END_REF], we fix the maximum number of parents to 5 and the density of N T , denoted by λ = #arcs n , which is a ratio of arcs per node. Furthermore, we consider the indecision case, meaning that one cannot decide whether o o or o o, and we use Eq (1) as accuracy measure 5 .

Table I shows better results for our algorithm due to the absence of indecision. However, in some cases, the algorithm proposed in [START_REF] Guerin | Learning cp-net preferences online from user queries[END_REF] has a better disagreement. When the number of variables is small, we can observe close agreement results between both algorithms, when the indecision case does not appear.

VII. CONCLUSION

We have proposed in this paper a new online learning algorithm of acyclic CP-nets from noisy datasets. This procedure improves the results presented in [START_REF] Guerin | Learning cp-net preferences online from user queries[END_REF] and provides an asymptotically optimal decision for the choice of conditioned variables. The theoretical and experimental results show the efficiency of its robustness to noise, and a fast convergence during the first iterations.

Future work will concern the management of parent variables in the learned CP-net, when, at some point, these variables become useless and could be deleted. We are also interested about agnostic PAC-learning properties that may guarantee stronger theoretical properties of our algorithm.

Fig. 1 .

 1 Fig. 1. Global scheme of a learning procedure for CP-nets.

Fig. 2 .

 2 Fig. 2. A complete CP-net with four variables.

Fig. 3 .

 3 Fig. 3. The learning problem.

4 update 5 if

 45 CPTable(V, R, r, o); Eq. (6) and |P a(V )| < k then 6 addParent(CP T (V ));

  to compute counters c(b r p ), c(b r p ), c(b r p ), . . . for all remaining nonparent variables B of V (with domain {b, b }) and all newly introduced rules. Due to the loss of information in online methods, it is obviously difficult to find the exact new counter for the remaining nonparent variables. The problem of estimating the new counters can be viewed as follows: consider a known set of objects E and a known size of two subsets E 1 ⊆ E and E 2 ⊆ E. How can we estimate the size of the intersection |E 1 ∩ E 2 |? Such an intersection can be bound between the Łukasiewicz t-norm (lower bound), denoted here by c -(.), and the Nilpotent minimum (upper bound), denoted here by c + (.). Then, we obtain for an assignment b ∈ Dom(B) and a new rule r p : c -(b r p ) = max (c(b r )c(r) + c(p r ), 0) , (10) c + (b r p ) = min (c(b r ), c(p r )) .

  a) Example: Let A, B, C be three variables and Ω be the following database: We fix our hyperparameter δ to 0.7. We first handle abc abc . After updating all counters, N L contains only the CPrule {∅ : c c } and Ineq. (

Fig. 4 .Fig. 5 .

 45 Fig.[START_REF] Chevaleyre | Learning ordinal preferences on multiattribute domains: The case of cp-nets[END_REF]. Learning accuracy according to the maximum number of parents per variable. Dataset is randomly generated (20, 000 comparisons, 12 variables, and δ = 0.95) with a varied noise probability (one per graphic line).

Fig. 9 .

 9 Fig.9. Learning accuracy according to the maximum number of parent per variable from real datasets. For each dataset, we select two different number of pairwise comparisons.

  table); 2) generate a random pairwise comparison (o, o ) V and deduce the preference from N T , i.e. o N T o or o N T o; 3) let o N T o be the current preference. Generate a random number x ∈ [0, 1]. If x > p, then Ω ← Ω∪{o o }. Ω ← Ω ∪ {o o} otherwise;

  [START_REF] Eckhardt | How to learn fuzzy user preferences with variable objectives[END_REF]. One can observe a linear growth of the computation time w.r.t. the number of parents. Moreover, this time, and its extreme values, also grow linearly w.r.t. the size of Ω.

		0%	10%	20%	40%
	accuracy rate (%)	50 60 70 80 90
		0.5 0.6 0.7 0.8 0.9 1
		hyperparameter δ
	Fig. 6. Learning accuracy according to the hyperparameter δ. Dataset is randomly generated (20, 000 comparisons, 15 variables) with a varied noise probability (one per graphic line).
			0%	20%
	error rate (%)	10 20 30 40 50 60 70 80 100 90
		0 200 400 600 800 1,000
			iterations
	Fig. 7. Experimental convergence of our algorithms. One iteration correspond to a consideration of one pairwise comparison. Dataset is randomly generated (1, 000 comparisons, 8 variables, and δ = 0.95) with a varied noise probability (one per graphic line).
		10 000	50 000	100 000
		18
	time (seconds)	3 6 9 12 15
		0 2 4 6 8 10 12 14
		max number of parents
	Fig. 8. Learning time according to the maximum number of parents per variable. Dataset is randomly generated (15 variables, δ = 0.95) with varied number of comparisons (one per graphic line).

TABLE I COMPARISON

 I RESULTS BETWEEN OUR ALGORITHM (GRAY CELLS) AND ALGORITHM OF GUERIN et al. (WHITE CELLS), WITH 20, 000 COMPARISONS, AND δ = 0.95. THE BEST RESULT IS WRITTEN IN BOLD.

	n	Accuracy (%) Error (%) Indecision (%)
			λ = 1
	4	100 100	0 0	0 0
	8	72 100	3 0	25 0
	12	70 98	1 2	29 0
			λ = 3
	4	98 97	2 3	0 0
	8	51 91	1 9	48 0
	12	40 89	2 11	58 0

The code is available here: https://services.lamsade.dauphine.fr/owncloud/ s/SW5UtCRk5BBYHHb.

However, when p > 1 2 , Algorithm 1 will clearly learn the noisy preferences because they will be in majority.

http://times.cs.uiuc.edu/ ∼ wang296/Data/, "text" folder.

disagreement = 1 -(agreement + indecision).


Milena Klasing Chen

Patrice Aknin

Lilly-Rose Lagadec

Dominique Laousse

Pascal Le Masson

Benoît Weil

ICED17 DESIGNING THE MISSING LINK BETWEEN SCIENCE AND INDUSTRY: ORGANIZING PARTNERSHIP BASED ON DUAL GENERATIVITY

Industry-academic research partnerships are mostly considered interesting to increase industrial innovativeness, and its benefits have been discussed in the flourishing open innovation literature. However, how to create mutually beneficial partnerships seems to be a question that has not been sufficiently studied. Through this article, we discuss the goals of these partnerships by modelling different types of collaboration. We defend that their real value has to be evaluated not only by looking at the knowledge created, but also at the increase of generativity we observe, due to interactions between academia and industry. Furthermore, we propose a model based on C-K theory that can be used to design a research collaboration that increases generativity, going beyond problem solving and knowledge transfer logics. We illustrate it through a case study, which shows that value creation in an industry-research partnership is increased by a model of co-generation, instead of considering these relations as a one-way transfer. Furthermore, we show that conflicts in a partnership can be solved through a C-K based tool.

HOW CAN WE CREATE MUTUALLY BENEFICIAL INDUSTRY-UNIVERSITY COLLABORATIONS? IDENTIFYING A GAP IN COLLABORATIONS DESIGN

It has been shown by several authors that university research, and public research in general, plays a very important part in industry innovativeness (e.g. [START_REF] Cohen | Links and impacts: the influence of public research on industrial R&D[END_REF]. Collaborating with academia has long been an important subject both for industrials trying to improve their products or propose innovations, and to draft public policies. Industries have increasingly engaged in "open innovation" [START_REF] Chesbrough | Open innovation: The new imperative for creating and profiting from technology[END_REF], engaging with academia not only through intellectual property transfer, but also through a variety of other research partnerships. If the value of collaborations is not always easy to assess, policy makers and industrials agree that there is much to be gained for industrials in them.

On the other hand, the profit of these collaborations for universities seems to have been the object of still fewer studies [START_REF] Perkmann | The two faces of collaboration: impacts of university-industry relations on public research[END_REF]. More, for some, it could be challenged that scholars could benefit of these collaborations. Some authors argue that too much industrial involvement can lead to a shift from basic research towards more applied topics or reduce the open-accessibility of science [START_REF] Nelson | The market economy, and the scientific commons[END_REF], while others state that it is undeniable that both funding and usecases coming from industrial partnerships are important inputs for academic research [START_REF] Davies | Industry-university collaborations: a necessity for the future[END_REF].

As discussed by [START_REF] Cohen | Links and impacts: the influence of public research on industrial R&D[END_REF], it has long been shown that it is an oversimplification to consider relations between academia and industry as a linear process where scholars give research knowledge to industry, which manages innovation as a R&D process. Perkman and Walsh (2007) show that the simple transfer model, where knowledge from one of the domains is plugged into the other one, does not work most of the time. The collaborations between industry and academia are much more complex and can take a great number of forms. They differ not only in the types of interactions, but also on their level of formalisation and financing principles [START_REF] Heraud | University-Industry Relationships and Regional Innovation Systems: Analysis of the French Procedure Cifre[END_REF].

According to [START_REF] Perkmann | The two faces of collaboration: impacts of university-industry relations on public research[END_REF], these collaborations constitute a two-way exchange, from which both academia and industry can benefit under certain conditions. This means reciprocity is far more developed than some text would lead to assume. They believe academics are able to benefit from industry collaboration especially when (i) they are in disciplines associated with the "sciences of the artificial", like engineering; (ii) collaboration is highly research driven and (iii) the researchers collaborate with industry through several different mechanisms.

ICED17

Despite the great variety of studies evaluating the impact of industry-university collaborations, Perkman and Walsh (2007, p259) draw attention to the fact that there is a lack of studies on the "search and match processes between universities and firms, and the organization and management of collaborative relationships". The great variety of studies showing that industry-academia collaborations can be beneficial for both academia and industry does not sufficiently study the design of these collaborations. We therefore identify that a gap exists, on how to create mutually beneficial collaborations between the industry and academia. To tackle this gap, we will propose a model for how these collaborations could be designed based on design theories.

HOW DESIGN THEORIES CAN HELP US CLOSING THE GAP ON COLLABORATIVE DESIGN

Collaborations between industry and academia have been studied as one of the aspects of open innovation, where a company relies on researchers outside its boundaries to achieve results. Open innovation is a flourishing subject and has been the object of numerous publications and studies, but as stated by van [START_REF] Enkel | Open R&D and open innovation: exploring the phenomenon[END_REF], divide the open innovation processes of firms into three groups: the outside-in process, the inside-out process and the coupled process. In the outside-in process companies integrate external knowledge to innovate. This is a problem-solving approach, where external knowledge is identified to solve an internal problem. In the inside-out process, companies look for a buyer or a market for a technology they developed. In this case we have a search for applications for an already acquired knowledge. And finally, the coupled process consists of combining the inside-out and the outside-in processes. In an industry-academia partnership, these open innovation processes translate to science application, when researchers try to find an industrial with an interest in application, and into problem-solving contests, where companies try to find external knowledge for an identified need. In both processes the required knowledge has been identified, so these approaches are not appropriated for when the required knowledge is unknown.

The value associated to these types of collaborations has largely been discussed in literature, but despite all the advantages associated to them they have one downside: the design effort is independent or sequential. In all these cases knowledge is created by one actor, and then adapted by another one to solve a problem. We believe that industry-academia collaborations should go beyond that, not only adapting existing knowledge, but also pursuing new designs and fostering each other's creativity. This belief is supported by the innovation management literature, which shows that innovation inside a firm does not emerge only from knowledge, but also from the firm's generativity, "the capacity to model creative reasoning and to relate to innovative engineering in all its aspects" (Agogué et Kazakci., 2014). Both the generativity on which knowledge to develop and on what desirable unknown to explore are key to innovation emergence. [START_REF] Kokshagina | Portfolio Management in Double Unknown Situations: Technological Platforms and the Role of Cross-Application Managers[END_REF]. In the design of a partnership, the knowledge to be identified or the action logics can be unknown, and current open innovation models do not allow us to handle the unknown. Design theories therefore supply the kind of framework needed to design a research partnership between academia and industry that tries to go beyond knowledge transfer logic.

2.1 A first model to collaborate beyond knowledge transfer: creating common knowledge As we have discussed previously, different collaborations between industry and academia exist. To increase the generativity of a research partnership, it is interesting to go beyond knowledge transfer through knowledge co-construction. In these kinds of innovation research partnerships, industrials and academics work together on creating common knowledge. The goal is defined jointly by both partners, who have different responsibilities in the partnership. Common knowledge creation is often done by industrial PhDs, like the CIFRE 1 PhD in France [START_REF] Heraud | University-Industry Relationships and Regional Innovation Systems: Analysis of the French Procedure Cifre[END_REF]. The CIFRE aims to improve the collaboration between industrial and academic research, by allowing a PhD student to spend time both in a research institute and in a firm. Beyond the joint research goal of collaboration, a CIFRE also aims to create competencies for the PhD student. Due to the student's involvement with both the scientific and the industrial communities, he facilitates the creation and transfer of knowledge between science and industry. One of the particularities of this type of collaboration is that the PhD student personifies the research collaboration. The collaboration is furthermore limited to 3 years, due to the contract between the involved actors. Table 1 recapitulates this first model's characteristics (M1). The goal in these collaborations is not to find existing knowledge and apply it, but rather to build on the existing and new knowledge to reach a desirable unknown [START_REF] Hatchuel | Deconstructing meaning: Industrial design as Adornment and Wit[END_REF]. The common purpose is often formalized between the two partners when the research proposition is drafted, allowing improved generativity and the joint knowledge creation. However, the outcomes of such a partnership are not always satisfying for all parties involved; difficulties to organise and manage these partnerships still exist. Furthermore, some of these collaborations still tend to maximise sequential design efforts, applying both science application and problem solving logics. These are logics that are easy to integrate by both partners, since they are often used in partnerships. We believe the value of these collaborations for both partners can be increased by better designing the research collaborations and increasing their generativity. Applying a design model should therefore greatly contribute to better understand industry-academia collaboration beyond technology transfer or knowledge-brokering (Hargadon & Sutton, 2000).

Proposing a model for industry-academia collaboration through design theories

Having shown the need for a design model for industry-academia partnerships that maximise value for both partners by increasing both generativity and knowledge creation, we will try to answer the following research question: Can design theories help us to improve the global performance of industry-academia collaboration? To answer our research question, we will build a theoretical model based on design theories, which we will refer to as innovation design partnership (M2). Its characteristics are described in Table 1.

Combined

In the study of innovation partnerships, design theories, and more specifically C-K theory, have been mobilized to better understand them and to show how they can be build [START_REF] Gillier | Portfolio management of innovation fields: applying CK design theory in cross industry exploratory partnership[END_REF]. The C-K theory is a design theory proposed by [START_REF] Hatchuel | CK design theory: an advanced formulation[END_REF] that has largely been used in industrial context to develop tools and methods, allowing to better understand the innovation process and to coordinate innovation efforts. It is based on the interplay between two distinct, but interdependent, spaces: the concept space (C), containing undecidable propositions, from which we cannot say if they are true or not; and the knowledge space (K), containing only propositions that are true or false. According to the authors, C-K theory is a rigorous and unified formal framework for Design. The main difference between C-K theory and other frameworks proposed in literature is its ability to describe the generation of new objects and of new knowledge. C-K based tools have proved to be helpful in an industrial context, and also in cross-industry partnerships. [START_REF] Gillier | The generation of common purpose in innovation partnerships: a design perspective[END_REF] show how building C-K profiles and applying a method they call "matching/ building" can be a way in innovative partnerships to create a common purpose, and orient cross-industry exploratory partnerships. Despite its numerous applications in industry, to our knowledge C-K theory has not been widely applied in the academic research contexts. Although the theory has been discussed in other academic fields than design, and Agogué and Kazakci (2014) listed 44 peer-reviewed publications on the subject, to our knowledge no specific method or tool based on C-K theory has been created for the academic research context, or for the collaboration between academic and industrial research. Being a theory on the design reasoning, the C-K theory is nevertheless well-positioned to be applied in this context, allowing to explicit the reasoning behind a research program. It furthermore allows, through its structuration of the knowledge and the concept space, to show both where new knowledge has been created (in the K space) and generativity has been increased (in the C space).

In designing an academia-industry partnership, we observe the same difficulties as identified by [START_REF] Gillier | Portfolio management of innovation fields: applying CK design theory in cross industry exploratory partnership[END_REF] in cross-industry partnerships: (1) the difference of strategies and goals between partners;

(2) the difference of needs and competencies and (3) the fact that great differences can exist in the knowledge and concepts of two partners. We can furthermore add one more topic to that list in an academic-industry partnership: (4) the different evaluation criteria of success between the partners [START_REF] Dulaurans | CIFRE: parcours de compétences d'une thèse annoncée[END_REF]. As stated by [START_REF] Nooteboom | Inter-firm collaboration, learning and networks: an integrated approach[END_REF], each partner will have his or her own goal and agenda. This has to be taken into account in the construction of the partnership, to make sure both parties can identify the benefits of the collaboration.

We therefore propose a method we will call "C-K co-generation" to allow all involved parties to jointly design a research program that is mutually beneficial, allowing both a knowledge expansion and an increased generativity, which means the exploration of new desirable unknowns for both partners. We start from the hypothesis that the goal of the academia-industry partnership is to collaborate in joint research: The partners agree that they want to go beyond transferring knowledge.

They also have dedicated resources to work during a limited time on their common goal.

The "C-K co-generation" method we propose consists of two main steps, illustrated in Figure 1: 1. Creating a first partnership intention leads to build distinct academia and industry C-K maps, based on the action logic of each actor: The academia's map describes the scientific program of the research institution; The industrial's C-K map figures the firm entity's R&D topics according to its activity. 2. Jointly building the C-K map that should dynamically guide the R&D partnership and the daily working agenda of the dedicated resources. The two C-K maps evolve through the discussion on the joint research program and through confrontation. This method tackles the difficulties we had previously identified in academia-industry partnership:

(1) and ( 2) The difference of strategies, needs and competencies between partners can be discussed once each one of the partners has formalized its own C-K map with help of independent C-K experts.

(3) The fact that great differences can exist in the knowledge and concepts of two partners even if they work on the same topic. Once more, formalization of concepts helps identify common knowledge and concepts. And the work done around building the C-K map to position the PhD allows finding common ground for the partners on the concepts and knowledge they wish to work on together. (4) The different evaluation criteria of success between the partners can be discussed and integrated in step 3, when building the C-K map of the research partnership. The clear positioning of the research partnership through the C-K maps not only helps to design the partnership's scope, but it also gives a clear vision of both industrial and academic issues that are outside the partnership's scope. This makes it easier to justify why these issues should be tackled otherwise.

Figure 1. The two steps of C-K co-generation, showing that both academia and industry had their concepts and knowledge, which were extended by the work done and the partnership combined them and created new concepts and knowledge

Finally, using C-K maps gives us a common language to mediate interactions between scholars and industrial in the research program design. Creating a common language is essential in cross-sector partnerships, allowing a common understanding of topics. It is one of the particularities of C-K theory [START_REF] Hatchuel | CK design theory: an advanced formulation[END_REF] and helps the co-generative process by identifying common challenges.

We expect an increased generativity to be a result of a partnership designed using our design model, as well as increased knowledge creation. Several metrics have been proposed to evaluate research partnerships, and many of them are based on economic impact. Limits of economic impact evaluations have been discussed by several authors (e.g. [START_REF] Hall | From measuring impact to learning institutional lessons: an innovation systems perspective on improving the management of international agricultural research[END_REF], and as defended by [START_REF] Rejeb | Measuring innovation best practices: Improvement of an innovation index integrating threshold and synergy effects[END_REF], evaluations combining both management processes as well as the learning process and cognitive ICED17 aspects help overcome these limitations. We will therefore evaluate knowledge creation by the new knowledge explored and generativity using the criteria of value, originality and producibility, as proposed by [START_REF] Magnusson | Managing user involvement in service innovation experiments with innovating end users[END_REF] when evaluating the quality of created ideas. C-K maps facilitate this evaluation by its structure, knowledge creation being a consequence of desirable concepts. And for each concept, value, originality and producibility are part of the associated knowledge. By comparing the C-K maps produced by each of the partners to the partnership C-K map, we should find in the partnership new concepts and new knowledge that were not found in either of the previous maps. This would indicate generativity in C and knowledge creation in K. Furthermore, comparing the first and final C-K maps for the industry and academia after the C-K co-generation, we should find evolutions both in the C and K spaces for both partners, showing their learning from the process. These evolutions might not be addressed through the partnership, but through other projects defined by the concerned actors. This theoretical model was built based on the knowledge we had on the difficulties of industryacademia collaborations using C-K theory expertise delivered by scholars from the Mines ParisTech Design Theory and Methods for Innovation (DTMI). We illustrate the use of our theoretical model though one empirical case, which we will discuss in the following item.

APPLICATION TO A CIFRE PHD, EXAMPLE OF A COLLABORATION ON THE SCIENTIFIC FIELD OF HYDROLOGY BETWEEN IRSTEA AND SNCF

We will discuss one application of our theoretical model in this part, through a reconstruction of an industrial PhD following a CIFRE contract, which was done after having identified difficulties and the need for method by the involved parties concerning the research program definition. The subject of the studied collaboration is "Evaluation and development of the IRIP method for intense storm runoff mapping: Application to the railway context." According to the first collaboration proposition drafted when the PhD was decided between the two organizations (2014), the PhD student was expected to develop the IRIP method, a multi-scale, cartographic runoff water indicator, comparing the results to those of other models and verifying its validity at different cartography scales.

After the model validation and calibration under railway specific conditions, the PhD student was supposed to adapt the model to SNCF's available data to assess its potential to prevent water overflow risks for the railway network. To do so, the PhD CIFRE contract provides shared time for the student between institutions (academic and industrial units). Six months after the PhD's beginning, the two research teams and the PhD student started identifying some difficulties in how to articulate the joint research program in a way that should be beneficial for all. Mainly, they had a divergence about the focus of the research: applied science (i.e. transfer logic from science to industry) or problem-solving (i.e. R&D). The PhD student was therefore torn between two different strategies. After seeing a presentation of the C-K theory's potential for managing PhD portfolios and designing the PhD strategy, the industrial tutor and the student believed this could be a way to discuss the research partnership. They therefore agreed to deepen the research partnership and, eventually, redefine its goal and activities using the C-K co-generation method to position research and industrial issues. The proposed device involved three actors: the industrial partner (SNCF Réseau's team), the academic partner (IRSTEA's research unit) and a third party on innovation methods (Mines ParisTech Chair DTMI and SNCF Innovation & Research Scientific direction). The third party was an essential part of the device, since PhD redesign needed a structured and guided method following C-K theory principles and this third party was in charge of structuring and guiding discussions. Innovation intermediates as these we introduce here have been increasingly studied, and their value in improving the innovation capabilities of other stakeholders has been shown [START_REF] Agogué | Managing innovative design within the health ecosystem: the living lab as an architect of the unknown[END_REF]. Our research was done following an intervention research method (Radaelli et al, 2012). The authors actively participated in building the research programs and the C-K maps. They were positioned as methodological experts during the entire process, which lasted around 6 months. In this time there was both work done in meetings and individually by the participants.

To start discussions on the collaboration, two plenary meetings were held, where a presentation of the PhD and of the state of the art on research on the PhD's subject was made to all partners. The purpose of these meetings was also to present the C-K co-generation method, and the benefits expected from applying it. These meetings also provided first elements for the C-K maps. The main outcome was an agreement of all the involved partners to apply the method, and a strategy to build the C-K maps with each partner (IRSTEA, SNCF Réseau).

The second step consisted of building the C-K maps. These were built with strong guidance of the methods team. The PhD student had separate meetings with both teams to build each partner's C-K map. We were able through the different sessions to observe an evolution of the C-K map of each of the partners and to observe how the research collaboration C-K could be built.

A further plenary meeting was organized to build the PhD's C-K map to guide the collaboration. It was furthermore the occasion to confront the academia and industry C-K maps. The PhD student was encouraged to build his C-K map as a coherent research program, and not as a consequence of the industry and academia C-K maps built previously.

At the end of the process we had three C-K maps, one for the industrial's team, one for the academic research team and one for the PhD research collaboration that had been discussed and agreed upon to guide the research partnership. At that stage, it could be seen that a science-industry transfer model is not relevant to understand how the research partnership was built, and that there was an increase in generativity. Debates during working sessions showed that both research and industry could leverage each other through co-generation. We will discuss these results in the following session.

MAIN RESULTS

Our main result is showing that academia -industry partnerships can profit from a design process, by increasing generativity instead of searching for a common goal. We therefore propose a method that can allow the design of a partnership that is beneficial for industry and academia, giving elements to help overcoming the research gap of how to design these partnerships. The proposed model not only allowed designing a mutually beneficial partnership, it also allowed solving a conflict between the involved partners. We confirmed our hypothesis thanks to the constructed C-K maps and showed that the value of research partnerships is linked to increasing generativity for both partners. Due to its specific structure, the C-K maps clearly separated the existing knowledge and concepts in each of the two structures. This allowed us to clearly map interactions. Knowledge transfer existed and led to new applications and small value creations, but allowed little evolutions in the partner's generativity, The most important value creation came from new concepts, proposed thanks to several interactions between partners and to the specific mechanisms used when building a C-K map. The highest originality was also achieved in this way.

Our case study allowed us to validate the value of using a method based on C-K theory in a specific kind of collaboration, a CIFRE PhD. Both the firm and university participants agreed that use of C-K tools, based on C-K theory, allowed to evaluate the PhD's relevance according to research and industry issues, improving their understanding of partner's needs and expectations. More, applying C-K to a CIFRE PhD revealed a generative power to redesign the research's relevance; opening new questions for industry and research.

Another important result was showing that, despite the fact that literature often speaks of concepts coming from the industry (as industrial applications) and knowledge coming from science, both industry and academia have complete C-K maps with concepts and knowledge. However, the concepts for academia are on new research strategies, and not on industrial problem solving. We furthermore observed that building a C-K map of a research field had a reflexive effect on both partners. The process we observe during the different meetings is more subtle than only a coconstruction: Each one of the actors evolves thanks to the work done together. Both the firm's as well as the university's research team stated that drafting their C-K map led them to ask themselves why they did or did not include some concepts or knowledge. Formalization in a C-K map and discussion among team members allowed generating new concepts and making implicit knowledge explicit.

Our case study also allowed highlighting how co-generation was done through the design of a research partnership. Before the effort of building the two C-K maps was done, there was little intersection ICED17 between the fields in which the two actors declared they were working in. Both partners worked in the same field but with very different points of view. The research team's focus was on a method to produce storm runoff mapping (IRIP method), based on a new Production-Transfer-Accumulation (PTA) concept of pluvial flooding representation. Industry's focus was on risk management against flooding in specific conditions (railway infrastructures resiliency facing critical situations) that drive to integrate, for example, civil engineering infrastructures as evolving obstacles to run-off. Despite the fact that both partners had a clear interest in developing the academic model IRIP, how to do so was unclear. The PhD had been launched to bridge the gap between the scientific existing knowledge and the application field, but the involved parties did not agree on a methodology. Building a common C-K map for the CIFRE PhD allowed mapping the way between the existing knowledge and the desired concept, clearly drafting which actions were to be taken and which not. It also allowed mapping out the possible alternatives if the chosen path turned out to be a dead end. The construction of the common research program demanded a discussion of the existing knowledge between both parties, and their appropriation in the partnership C-K. It furthermore demanded the creation of a series of concepts and activities around knowledge creation that did not exist in either of the two maps. This can be exemplified by one of the concepts in the CIFRE C-K, which was "To create new approaches for risk management using a new IRIP model". This concept led to the analysis of the actual water related risk management process within SNCF and the identification of elementary tasks where the actual IRIP model can bring direct contribution to the process and where both the IRIP model must be adapted and the actual process must evolve [START_REF] Lagadec | Using maps of surface runoff susceptibility for optimizing risk diagnoses on railways[END_REF]. To achieve this work, knowledge coming from IRSTEA on the IRIP model was needed, as well as knowledge on the railway network and the types of risks coming from SNCF. Building C-K maps greatly helped to allow a dialog on co-generation, since it gave participants a common language basis and allowed going beyond traditional research programs. By confronting their C-K maps, the two partners were able to add relevant knowledge and concepts to their own C-K map.

And the discussions between the actors led to explicit and clarify implicit knowledge, also leading to advances on the reformulation of certain aspects of their C-K maps. We were also able to observe knowledge re-ordering (Poitier et al., 2015). The new knowledge integrated from one of the partners forced to rethink existing knowledge bases, opening up new knowledge bases. The co-generation effects described above are the ones expected through our theoretical model, as illustrated in Figure 1.

In the words of research-industry partners the C-K PhD co-generation method helped them to clarify their own needs and expectations, as well as the research program behind the PhD. The PhD C-K map shed new light on what could be inside PhD and what had to be outside, but could be treated in complementary research projects driven by the same or different partners. It helped to manage the time constraint to finish the research program in three years. Thanks to the C-K map they were able to better evaluate which paths could be included inside the PhD's limited time, and which should be the object of other partnerships or research programs. The drafted C-K maps were seen by both the research teams as interesting tools to challenge their activities and research goals. Both teams agreed that the C-K map they build was a powerful tool to help in internal management and to place their activity regarding the rest of the firm or the scientific community. The firm's research team further declared it was a useful tool to present their activity to other research teams inside the firm, since it helped to clarify their research strategy and to formalise the logic behind their actions. These C-K maps are living tools, and have to be regularly updated to be able to develop their full potential. These results and their interpretation using a C-K framework illustrate how the research partnership went beyond a simple transfer of knowledge or a transfer of concepts, to a co-generation, both of knowledge and concepts.

LIMITATIONS OF OUR STUDY AND FURTHER RESEARCH

We believe the results from our case study are promising for the design, organisation and management of industry-academia partnerships beyond an industrial PhD. Our theoretical model has however only been tested on one type of collaboration so far. The models we propose try to characterize specific partnerships, in practice they can clearly be combined between them and a firm should explore all of them, since different situations will demand different approaches. Further research should focus on experimenting on the different types of identified research partnerships.

Despite the need for more research to confirm our results, our case leads us to believe not only that the research program for the partnership can be co-generated and therefore create value for both partners, but that this co-generation is valuable for each one of the partners because it allows them to make their own research programs evolve. The use of a C-K framework furthermore leads to a reflexive approach of the research programs, that the concerned parties had trouble achieving before. C-K mapping seems to be helpful for elaborating and managing new relations between science and industry on a more equal basis, reducing by a dialog in the conceptual space. However, we still need to further investigate the inputs from the partnership C-K mapping to the innovation and research strategies. Evidence from our case study shows that firms and academia can and should engage in co-generation in their partnerships, since it allows creating more value for both partners. We do however identify another limitation linked to the setting we chose. As has been highlighted by several scholars (e.g. [START_REF] Perkmann | University-industry relationships and open innovation: Towards a research agenda[END_REF], in disciplines like engineering, where academia is closer to industry, it is easier to create value in industry-academia partnerships. Our case study was placed in this kind of setting, it would be valuable to verify if in other contexts and disciplines the model proposed by us and a framework based on C-K theory might reach the same kind of results. We further believe this method could be used to coordinate two or partnerships for a university or firm on similar subjects. In this case the method would not only allow the university or firm to coordinate, but also the ressources to coordinate between them, creating synergies. We conclude by stating that other usages for this model might exist, and that the results found so far with it encourage us to test it in different contexts.

  The CIFRE collaboration we studied was in hydrology, between the IRSTEA's (National Research Institute of Science and Technology for Environment and Agriculture) Hydrology-Hydraulic research unit and SNCF Réseau's (a French railway network manager and maintainer) Hydraulic-Drainage team. The design process was accompanied by Innovation and Prospective SNCF corporate team (Innovation & research department) and the Chair Design Theory and Methods for Innovation (Mines ParisTech).

  de Vrande et al. (2010) scholars need to go beyond the open/closed innovation debate towards how open innovation strategies demand a different organisational structure and mindset.

When looking at literature on open innovations, researchers agree that focus should be given to theory development on this field. As pointed out by

[START_REF] Elmquist | Exploring the field of open innovation[END_REF]

, there is still a need for a critical discussion of the open innovation concept, the strengths and weaknesses of this model have hardly been theorized. The particular interaction of collaborative design with academia and how to make this profitable for both researchers and industrials has also, to our knowledge, not yet been sufficiently treated. As stated by Le

Masson et al. (2013, 241)

, the goal of design theories is to "understand and support contemporary forms of collective action". They therefore seem particularly appropriated to help structure the debate on industry-academia research and to theorize this aspect of open innovation. Furthermore, in the open innovation literature, despite the discussion of different degrees of openness,

Table 1

 1

	illustrates the generativity, knowledge creation and

Table 1 .

 1 Generativity and knowledge creation expected through our theoretical model compared avec the previously discussed models

		Science application Problem solving	Innovation research	Innovation design
				partnership (M1)	partnership (M2)
	Academia	Develops new	Develops	Develops knowledge Develops new
					ICED17

1 CIFRE (Convention industrielle de formation par la recherche) could be translated as "Convention for Learning by Industrial Research". This collaborative mechanism has been in operation in France since 1981. The CIFRE PhD student is partly funded by the ANRT (Association Nationale de la Recherche et de la Technologie), the National Agency for Technology and Research, an association that assembles the public and private research actors in France since 1953. More information on the ANRT and the CIFRE device can be found on http://www.anrt.asso.fr/