Cheng-Wei Chou

Ping-Chiang Chou

Chang-Shing Lee

David Lupien Saint-Pierre

Olivier Teytaud

Mei-Hui Wang

Li-Wen Wu

Shi-Jim Yen

Strategic Choices: Small Budgets and Simple Regret

Keywords: Go, Bandit problem, Recommendation policy, Selection policy, Metagaming

In many decision problems, there are two levels of choice: The first one is strategic and the second is tactical. We formalize the difference between both and discuss the relevance of the bandit literature for strategic decisions and test the quality of different bandit algorithms in real world examples such as board games and card games. For exploration-exploitation algorithm, we evaluate the Upper Confidence Bounds and Exponential Weights, as well as algorithms designed for simple regret, such as Successive Reject. For the exploitation, we also evaluate Bernstein Races and Uniform Sampling. As for the recommandation part, we test Empirically Best Arm, Most Played, Lower Confidence Bounds and Empirical Distribution. In the one-player case, we recommend Upper Confidence Bound as an exploration algorithm (and in particular its variants adaptUCBE for parameter-free simple regret) and Lower Confidence Bound or Most Played Arm as recommendation algorithms. In the two-player case, we point out the commodity and efficiency of the EXP3 algorithm, and the very clear improvement provided by the truncation algorithm TEXP3. Incidentally our algorithm won some games against professional players in kill-all Go (to the best of our knowledge, for the first time in computer games).

Introduction

Many important optimization problems can be separated in two parts: strategic decisions and tactical behavior. Table 1 provides several examples in industry and games. In the recent years, a wide body of theoretical and experimental work, namely the bandit literature, has been developed around one-step and often unstructured decision making. However, strategic decisions are specific bandit problems; they usually have a very restricted time budget and, in the two-player case, a huge sparsity (in the sense that the optimal solution, namely a Nash equilibrium, is usually sparse). This paper is devoted to the analysis of the relevance of this literature for strategic decisions.

In this section we will formalize the problem (1.1) and present the notations (1.2). In Section 2 we will present classical algorithms. In Section 3 we will test them experimentally; we will conclude in Section 4.

Formalization of the problem

There's no clear formal definition of what is a strategic choice, compared to a tactical choice. However, the idea is that a strategic choice is at a higher level; we will formalize this as follows: in a strategic bandit problem, the number of iterations T is not huge compared to the number of options (K in the one player case, or K × K ′ in the two player case). In the one-player case, we will therefore focus on T ≤ 100K, and in 1: Problems with strategy/tactics decomposition. Sometimes, it would be possible to define more levels (e.g. deciding investments for electricity production). Batoo is a recent yet popular game with strong strategic decision: the choice of initial stones.

the two-player case T ≤ K × K ′ . Also, we use simple regret, and not cumulative regret, for the one-player case; and average performance of the recommended distribution for the two player case, which is somehow a natural extension of simple regret for the two player case.

Let us consider a set of strategic choices, also termed arms or options in the bandit literature, denoted without loss of generality by {1, . . . , K}. We want to choose θ ∈ {1, . . . , K} for some performance criterion. We have a finite time budget T (also termed horizon), which means that we can have access to T realizations L(θ 1 ), L(θ 2 ), . . . , L(θ T ) and we then choose some θ. This is the metagame in the one-player case; it is detailed in Fig. 1. There are several remarks on this framework:

• The algorithm chooses θ1 ∈ {1, . . . , K}.

• The algorithm gets a reward r1 distributed as L(θ1).

• The algorithm chooses θ2 ∈ {1, . . . , K}.

• The algorithm gets a reward r2 distributed as L(θ2).

• . . . • The algorithm chooses θ T ∈ {1, . . . , K}.

• The algorithm gets a reward r T distributed as L(θ T ).

• The algorithm chooses θ.

• The loss, termed simple regret, is r T = max θ EL(θ) -EL( θ). • For evaluating L(θ i ), we need a simulator, including the tactical decisions. This possibility is based on the assumption that we can simulate the tactical choices once the strategic choices have been made. • Without loss of generality, the simple regret is always positive, and the goal is to have a simple regret as small as possible.

In the two player case, the framework is detailed in Fig. 2. As in the one-player case, the loss is always positive (without loss of generality), and the goal is to have a loss as small as possible. There are several remarks on this framework:

• As in the one-player case, we assume that we can simulate the tactical behaviors (included the tactical behavior of the opponent). Basically, this is based on the assumption that the opponent has a strategy that we can nearly simulate, or the assumption that the difference between the strategy we choose for the opponent and the opponent's real strategy is not a problem (playing optimally against the first is nearly equivalent to playing optimally against the latter). This is a classical assumption in many game algorithms; however, this might be irrelevant for e.g. Poker, where opponent modelization is a crucial component of a strategy for earning money; it might also be irrelevant in games in which humans are by far stronger than computers, as e.g. the game of Go.

• The algorithm chooses θ1 ∈ {1, . . . , K} and θ ′ 1 ∈ {1, . . . , K ′ }. • The algorithm gets a reward r1 distributed as L(θ1, θ ′ 1 ). • The algorithm chooses θ2 ∈ {1, . . . , K} and θ ′ 2 ∈ {1, . . . , K ′ }. • The algorithm gets a reward r2 distributed as L(θ2, θ ′ 2 ). • . . . • The algorithm chooses θ T ∈ {1, . . . , K} and θ ′ T ∈ {1, . . . , K ′ }. • The algorithm gets a reward r T distributed as L(θ T , θ ′ T ). • The algorithm chooses a random variable θ.

• The loss, termed simple regret, is r T = max θ min θ ′ EL(θ, θ ′ )min θ ′ EL( θ, θ ′ ) (where here maxima and minima are for random variables θ, θ ′ ; in the 2-player case we look for Nash equilibria and we expect optimal strategies to be nondeterministic). • We use a simple regret algorithm; this is somehow natural (under assumptions above) as the simple regret is directly the expected increase of loss due to the strategic choice (at least, if we trust assumptions above which ensure that L(•, •) is a good sampling of possible outcomes).

In the game literature, the non-strategic part is usually termed "ingaming" for pointing out the difference with the metagaming.

Terminology, notations, formula

Useful notations: #E is the cardinal of the set E. N t (i) is the number of times the parameter i has been tested at iteration t, i.e. N t (i) = #{j ≤ t; θ j = i}. Lt (i) is the average reward for parameter i at iteration t, i.e. Lt (i) = 1

Nt(i) j≤t;θj =i r j (well defined if N t (i) > 0). Confidence bounds will be useful as well:

U B t (i) = Lt (i) + log(t)/N t (i); LB t (i) = Lt (i) -log(t)/N t (i).
Various constants are sometimes plugged into these formula (e.g. a multiplicative factor in front of the √ .). These confidence bounds are statistically asymptotically consistent estimates of the lower and upper confidence bounds in the one-player case for a confidence converging to 1. In some cases, we need a weighted average as follows (with ∀i, Ŵ0 (i) = 0): Ŵt (i) = 1 t j≤t;θj =i r j /p j (i) where p j (i) is the probability that i is chosen at iteration j given observations available at that time. This will in particular be useful for EXP3. When there are two players, similar notations with a ' are used for the second player: Ŵ ′ t (j), L′ t (j),. . . As we can see in Figs 1 and2, specifying a metagaming algorithm implies specifying several components:

• The tactical simulators (necessary for computing L), which, given the sequence of strategic and tactical decisions, provide the loss; this is part of the problem specification. • The simulator of our tactical strategy; this is also necessary for computing L. We will not work on this part, which is precisely not the meta-gaming part. • For the two-player case, the simulator of the opponent's strategy as well. This could be considered as a part of metagaming because the uncertainty on the opponent's strategy should, in a perfect world, be taken into account in the strategic module. However, we simplify the problem by assuming that such a simulator is given and fixed and satisfactory. • The two components which are the core of metagaming/strategic choices (following the terminology of [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF]):

exploration module, aimed at choosing θ i and θ ′ i (the latter in the two-player case); -recommendation module, aimed at choosing θ.

The underlying assumption in this paper is that we do not seek to work on the detailed structure or the problem, and we just want to have access to it through high-level primitives like the L function. [START_REF] Bourki | Parameter Tuning by Simple Regret Algorithms and Multiple Simultaneous Hypothesis Testing[END_REF] has done a similar comparison, with a different family of bandits and a different context; we here use their best performing bandits, and add some new ones (the LCB recommendation, Bernstein races which were cited but not tested, Successive Rejects and Adapt-UCB-E).

• Define Z = 1 2 + K i=2 1/i and A = {1, . . . , K} and n0 = 0 and

n k = ⌈(1/Z) T -K K+1-k ⌉ for k ≥ 1.
• For each epoch k = 1, . . . , K -1:

-For each i ∈ A, choose (exploration) arm i during n kn k-1 steps.

-Then, remove from A the arm with worse average reward.

• Recommend the unique remaining element of A.

Figure 3:

The Successive Reject algorithm from [START_REF] Audibert | Best Arm Identification in Multi-Armed Bandits[END_REF] for K arms and T iterations.

Algorithms

We summarize below the state of the art, for exploration and for recommendation.

Algorithms for exploration

We present below several known algorithms for choosing θ i , θ ′ i .

• The UCB (Upper Confidence Bound) formula is well known since [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF][START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF]. It is optimal in the one player case up to some constants, for the criterion of cumulative regret. The formula is as follows, for some parameter α:

θ t = mod(t, K) + 1 if t ≤ K; θ t = arg max i Lt-1 (i) + α log(t)/N t-1 (i) otherwise.
• The EXP3 (Exponential weights for Exploration and Exploitation) algorithm is known in the two-player case [START_REF] Auer | Gambling in a rigged casino: the adversarial multi-armed bandit problem[END_REF]. It converges to the Nash equilibrium of the strategic game. In our variant, θ t+1 = i with probability

β K √ t + (1 -β/ √ t) exp( √ t Ŵt-1 (i)) j∈{1,...,K} exp( √ t Ŵt-1 (j)) .
• [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF] has discussed the efficiency of the very simple uniform exploration strategy in the one-player case, i.e.

θ t = arg min i∈{1,...,K} N t-1 (i);
in particular, it reaches the provably optimal expected simple regret O(exp(-cT )) for c depending on the problem. [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF] also shows that it reaches the optimal regret, within logarithmic terms, for the non-asymptotic distribution independent framework, with O( K log(K)/T ). • [START_REF] Mnih | Empirical Bernstein stopping[END_REF] has revisited recently the progressive discarding of statistically weak moves, i.e. Bernstein races;

in this paper, we choose the arm with smallest number of simulations among arms which are not statistically rejected:

θ t+1 = arg min i∈{1,...,K} U Bt(i)≥max k LBt(k) N t (i).
In many works, Bernstein bounds are used with a large set of arms, and coefficients in LB or UB formula above take into account the number of arms; we will here use the simple LB and UB above as our number of arms is moderate.

• Successive Reject (SR) is a simple algorithm, quite efficient in the simple regret setting; see Fig. 3.

• Adaptive-UCB-E is a variant of UCB, with an adaptive choice of coefficients; see Fig. 4 2

.2 Algorithms for final recommendation

Choosing the final arm, used for the real case, and not just for exploration, might be very different from choosing exploratory arms. Typical formulas are:

• Define Z = 1 2 + K i=2 1/i and n k = ⌈(1/Z) T -K K+1-k ⌉.
• Define t0 = 0 and t1 = Kn1 and

t k = n1 + • • • + n k-1 + (K - k + 1)n k .
• Define Bi,t(a) = Lt-1(i) + a/Nt-1(i).

• For each epoch k = 1, . . . , K -1:

-Let H = K if k = 0, and H = max K-k+1≤i≤K i ∆-2 (< i >, k) otherwise, where ∆i,k = (max 1≤j≤K Lt-1(j) -Lt-1(i), and

< i > is an ordering such that ∆ <1>,k ≤ • • • ≤ ∆ <K>,k .
-For t = t k + 1, . . . , t k+1 choose (exploration) arm i maximizing Bi,t(cn/H).

• Recommand i maximizing Lt(i).

Figure 4:

The Adaptive-UCB-E algorithm from [START_REF] Audibert | Best Arm Identification in Multi-Armed Bandits[END_REF].

• Empirically best arm (EBA): picks up the arm with best average reward. Makes sense if all arms have been tested at least once. Then the formula is θ = arg max i LT (i). • Most played arm (MPA): the arm which was simulated most often is chosen. This methodology has the drawback that it can not make sense if uniformity is applied in the exploratory steps, but as known in the UCT literature (Upper Confidence Tree [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF]) it is more stable than EBA when some arms are tested a very small number of times (e.g. just once with a very good score -with EBA this arm can be chosen). With MPA, θ = arg max i N T (i). • Upper Confidence Bound (UCB): θ = arg max i U B T (i). This makes sense only if T ≥ K. UCB was used as a recommendation policy in old variants of UCT but it is now widely understood that it does not make sense to have "optimism in front of uncertainty" (i.e. the positive coefficient for t/N t (i) in the UB formula) for the recommendation step. • As Upper Confidence Bound, with their optimistic nature on the reward (they are increased for loosely known arms, through the upper bound), are designed for exploration more than for final recommendation, the LCB (Lower Confidence Bound) makes sense as well: θ = arg max i LB T (i). • EXP3 is usually associated with the empirical recommendation technique (sometimes referred to as "empirical distribution of play"), which draws an arm with probability proportional to the frequency at which it was drawn during the exploration phase; then P ( θ = i) = N T (i) T . • For the two-player case, a variant of EXP3 benefit from sparsity through truncation (TEXP3, Truncated EXP3) has been proposed [START_REF] Flory | Upper confidence trees with short term partial information[END_REF]. It is defined in Fig. 7. • For SR (successive reject), there are epochs, and one arm is discarded at each epoch; therefore, at the end there is only one arm, so there is no problem for recommendation.

Experimental results

We experiment algorithms above in the one-player case (with kill-all go, in which the strategic choice is the initial placement of stones for the black player) and in the two-player case in sections below.

One-player case: killall Go

We refer to classical sources for the rules of Go; KillAll Go is the special case in which black is given an advantage (some initial stones), but has a more difficult goal: he must kill all opponent stones on the board. So, one player only has initial stones to set up; the game is then played as a standard Go game. We refer to two different killall-Go frameworks: 7x7, 2 initial stones for black (Section 3.1.1); 13x13, 8 or 9 initial stones for black (Section 3.1.2). The human opponent is Ping-Chiang Chou (5p professional player).

7x7 killall Go

Here, the black player must choose the positioning of two initial stones. Human experts selected 4 possibilities: (1) a black stone in C5, and next black stone chosen by the tactical system as a first move; (2) a black stone in C4, and next black stone chosen by the tactical system as a first move; (3) a black stone in D4 (center), and next black stone chosen by the tactical system as a first move; (4) two black stones in C4 and E4. We tested intensively each of these strategic choices by our tactical system (ColdMilk program, by Dong Hwa university), in order to get a reliable estimate of the winning rate in each case (Table 2). Then, we simulated (using these estimates as ground truth) what would happen if we used various strategic tools for choosing the initial placement, for various limited budgets (T = 16, 64, 256). Results, for kill-all Go as explained above and also for various artificial settings with the same number of arms, are presented in Tables 5 and5. Arms are randomly rotated for getting rid of trivial bias. Table 5 contains both real-world and artificial results; artificial results are as follows: (1) random uniform probabilities of winning for each arm; (2) all arms have probability 0 of winning except one arm which has probability 0.1 of winning (3) all arms have probability 1 of winning except one arm which has probability 0.9 (4) all arms have probability 0.5 except one which has probability 0.4 (5) all arms have probability 0.5 except one which has probability 0.6. Please note that in the artificial cases, the index of the special arm (the arm with different reward) is randomly drawn and is indeed not necessarily the first. Left: Efficiency of each strategic choice for black in killall Go. These numbers will be used as ground truth for experiments below (Table 5). Center and Right: Games played by our program MoGoTW as White (center) and as Black (right) in 7x7 killall Go. The center game is a win for the program whereas the right game is a loss.

Two 7x7 killall-go games were then played against Ping-Chiang Chou (5P), with one win of the computer as White and one loss of the computer as Black (i.e. White won both). Results are presented in Fig. 2 (right). The pro player did not make the same strategic choice as our program (he chose C4 E3 instead of our choice C4 E4) but agreed, after discussion, that C4 E4 is better.

13x13 killall Go

We reproduced the experiments with 13x13 initial placement of stones. Fig. 5 presents the five different handicap placements considered in the experiment. As for 7x7, heavy computations allowed us to find an approximate ground truth, and then experiments are run on this ground truth. Experimental results for various bandit approaches on this 13x13 killall Go metagaming are given in Table 3. We also test on artificial problems. We then show in Fig. 6 the games played against Ping-Chiang Chou by our program as White with 8 and 9 initial stones respectively; we see on these games the strategic choice made by Ping-Chiang Chou (5P), which is the same as the strategic choice by our program, i.e. the first choice in Fig. 5.

Two-player case: Sparse Adversarial Bandits for Urban Rivals

Recently [START_REF] Flory | Upper confidence trees with short term partial information[END_REF] proposed a variant of EXP3 called TEXP3. TEXP3 takes its root into the fact that decision making algorithms in games rarely have enough time to reach the nice asymptotic behavior guarantied by EXP3. Also, EXP3 fails to exploit that in most games, the number of good moves is rather low compared to the number of possible moves K. TEXP3 is an attempt to exploit these two characteristics. It uses the outcome of EXP3 and truncates the arms that are unlikely to be part of the solution. Alg. 7 describes the implementation. The constant c is chosen as 1 T max i (T x i ) α for some α ∈]0, 1[ (and d accordingly), as in [START_REF] Flory | Upper confidence trees with short term partial information[END_REF], while T is the number of iterations executed. We set α = 0.7 in our experiments, following [START_REF] Flory | Upper confidence trees with short term partial information[END_REF][START_REF] Auger | Sparse bandit algorithms[END_REF]. The natural framework of EXP3 is a two-player game. In this section we apply EXP3 and TEXP3 to Urban Rivals, a stochastic card games available for free on Internet and that fits the framework. The game is as follow: (1) player 1 choose a combination θ 1 ∈ {1, . . . , K 1 }; (2) simultaneously, player 2 choose a combination θ ′ ∈ {1, . . . , K ′ }; (3) then the game is resolved (ingaming). We consider a setting in which two players choose 4 cards from a finite set of 10 cards. There exists 10 4 combinations, yet by removing redundant arms, we Let x and y be the approximate Nash equilibria as proposed by EXP3 for the row and column players respectively. Truncate as follows remain with 715 different possible combinations (both K 1 = K 2 = 715) if we allow the same card to be used more than once. The first objective is to test whether EXP3 (and TEXP3) is stronger than a random player for different numbers of iterations T . We are specifically interested in situation where T is small (compared to K 1 × K 2 ) as it is typically the case in games. strategic choice that outperforms a random player when they have similar tactical capabilities. As T grows, the strategic choice becomes better. Next we look into a way to make an even better choice with a smaller T . Recently TEXP3 has been proven to outperform a random player with less information than EXP3 (experimentally in [START_REF] Flory | Upper confidence trees with short term partial information[END_REF], theoretically in [START_REF] Auger | Sparse bandit algorithms[END_REF]). Table 4 (right) presents the performance of TEXP3 against a random player under the same settings as EXP3 above. These results are in line with previous studies; however, the improvement is much better -probably because we have here a highly sparse problem. Even with the lowest setting (T = 10000), TEXP3 managed a strong performance against a random player. Again, with little information (T << K 1 × K 2 ), TEXP3 can make strategic choices that influence the outcome of the game positively; furthermore, it clearly outperforms EXP3.

x ′ i = xi if xi > c, x ′ i = 0 otherwise; y ′ i = yi if yi > d, y ′ i = 0 otherwise. Renormalize: x ′′ = x ′ / i x ′ i ; y ′′ = y ′ / i y ′ i . Output x ′′ , y ′′ .
4 Conclusions for small time budgets: adversarial and stochastic frameworks, cumulative regret or simple regret, and the importance of sparsity

We compared various algorithms for strategic choices including widely played games (Killall Go, a classical exercise of Go schools, and Urban Rivals); we defined strategic choices in terms of moderate exploration budget for a simple regret criterion. We distinguished the one-player case and the two-player case; this distinction, in bandit terms, is a distinction between stochastic and adversarial bandits. As clearly shown by the good performance of UCB/LCB variants, SR, and EXP3 on their original frameworks (one-player and two-player cases respectively), and by the poor performance of EXP3 in the one-player case, this distinction is relevant. Consistently with theory, bandits designed for the stochastic case (typically UCB) performed well in the one-player case and bandits designed for the adversarial case (typically EXP3) performed well in the two-player case. The distinction between simple regret and cumulative regret is less striking; yet, successive rejects, which was designed for simple regret algorithms, performed very well in particular for very small budgets.

We also show the relevance of a careful recommendation algorithm; UCB is a good exploration algorithm, but it should be accompanied by a good recommendation strategy like LCB or MPA as soon as the number of options is not negligible compared to the number of time steps; otherwise weak poorly explored arms can be recommended. This is however less critical than in Monte-Carlo Tree Search, where bandits are applied many times per run (once per move in a control problem or in a game).

The results in the two-player case also suggest that sparsity should be used whenever possible in the adversarial case; the superiority of TEXP3 over EXP3 in this context is the most clearest contrast in this work. Whereas simple regret and cumulative regret make little difference, even in the context of small time budget, sparse or not sparse makes a big difference, as much as distinguishing one-player case and two-player case. A main further work is the analysis of cases where structure on options or a priori ranking of options is available. We conclude below with more details for the one-player and two-player case respectively.

One-player case

There are two crucial components under test: exploration algorithm, and recommendation algorithm. The most important component in strategic choices is the exploration formula. In many of our tests (with the notable exception of very small budget, very relevant here for our setting), the best algorithm for exploration is UCB, which is designed for the one-player case with cumulative regret; the surprising thing is that we here work on the simple regret, which is the natural notion of regret for the framework of strategic choices. Nonetheless, the variant of UCB termed Adapt-UCB-E, designed for parameter free simple regret, performs correctly. Consistently with artificial tests in [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF], UCB is non-asymptotically much better than uniform exploration variants (which are nonetheless proved asymptotically optimal within logarithmic factors both for a fixed distribution and in a distribution free setting, in the "simple regret" setting). The asymptotic behavior is far from being a good approximation here. Importantly for our framework, Successive Reject, designed for simple regret, is very stable (never very bad) and outperforms UCB variants for the smallest budgets.

Consistently with some folklore results in Monte-Carlo Tree Search, the recommendation should not be made in a UCB manner; in fact, the lower confidence bound performed very well; we also got good results with the most played arm or the empirically best arm, as recommendation rules. We point out that many practitioners in the Computer-Go literature (which is based on heavily tuned bandit algorithms) use combinations of EBA and MPA and LCB as recommendation arms for optimal performance. Consistently with intuition, EBA becomes weaker with larger numbers of arms. This is consistent with experiments in [START_REF] Bourki | Parameter Tuning by Simple Regret Algorithms and Multiple Simultaneous Hypothesis Testing[END_REF]. Bernstein races performed moderately well; there was no effort for tuning them and maybe they might be improved by some tuning. Adapt-UCB-E performed well as a variant of UCB dedicated to simple regret, but not better than SR or other UCB variants.

Results include games won against a professional player, in 7x7 Killall Go and in 13x13 Killall Go; in this case, the strategic decision is the initial choice.

Two-player case

In the two-player case, EXP3 (dedicated to this adversarial setting) naturally performed well.We made experiments confirming the good behavior of the algorithm, following [START_REF] Flory | Upper confidence trees with short term partial information[END_REF][START_REF] Bouzy | Multi-agent learning experiments on repeated matrix games[END_REF][START_REF] Auger | Multiple tree for partially observable monte-carlo tree search[END_REF]. As metagaming is a good candidate for providing sparse problems, we tested the efficiency of the truncation algorithm TEXP3 [START_REF] Flory | Upper confidence trees with short term partial information[END_REF], with indeed much better results here than in the original paper (this is certainly due to the fact that, in our metagaming context, we have a much more sparse benchmark than [START_REF] Flory | Upper confidence trees with short term partial information[END_REF]).

Results include experiments on a real game, namely Urban Rivals; the strategic choice consists in choosing the cards, which is directly a strategic choice setting.

Figure 1 :

 1 Figure 1: Metagaming with one player.

Figure 2 :

 2 Figure 2: Metagaming with two players.

Figure 5 :

 5 Figure 5: Five different handicap placements proposed by Go experts for 13x13 killall Go with 9 initial stones.

Figure 6 :

 6 Figure 6: These two games are the killall-go games played by our program as White against Ping-Chiang Chou (5P). The program won with 8 initial black stones and lost with 9 initial stones. As Black, the program lost both H8 and H9.

Figure 7 :

 7 Figure 7: TEXP3 (truncated EXP3), offline truncation post-EXP3.

Table

		Real world examples
	Electricity	Choosing the	Choosing (real-time)
	Production	maintenance	how to satisfy the
		dates	demand (switching
			on/off the plants)
	Logistics	Warehouse/factory	Trucks/boats/trains
		positioning	scheduling
	Military	Choosing the date	Military tactics
	operations	& the planning
	Games
	Handicap	Placing the	Standard Go
	Go	handicap stones	gameplay
	Batoo	Opening	Batoo variant of
		stones	Go gameplay
	Chess	Opening choice	Chess gameplay
	New card games	Choosing	Choosing
	(Pokemon,	the deck	cards/attacks
	Urban Rivals)

Table 2 :

 2

Table 3 :

 3 Experimental results of average simple regret when comparing five different stone placements for 9 stones in 13x13 as shown in Fig. 5. All experiments are reproduced 1000 times.

Table 4 (

 4 left) present the score (in %) of EXP3 versus a random player. EXP3 significantly beats the random player when T > 25000. It can thus execute a

Table 4 :

 4 EXP3 vs Random (left) and TEXP3 vs Random (right).

	T	Score ±1σ	T	Score ±1σ
	10 000	0.5042 ± 0.001	10 000	0.7206 ± 0.005
	25 000	0.5278 ± 0.001	25 000	0.7238 ± 0.003
	50 000	0.5421 ± 0.002	50 000	0.7477 ± 0.002
	100 000 0.5749 ± 0.004	100 000 0.7871 ± 0.006

Table 5 :

 5 Left: Average simple regret for various exploration/recommendation methodologies. Performance of various strategic systems for choosing initial placement for Black in 7x7 killall-Go. The first row is the real-world case, with 4 arms; then, we consider various cases with the same number of arms (see text). Each experiment is reproduced 1000 times and standard deviations are less than 0.04. Right: similar to Left, but we do not remove the symetries; this increases the number of possible choices to 11. This is obviously not what we should do from the point of view of the application; we just do this in order to generate a new test case. The same artificial cases as in the 4-options case are reproduced with 11 options. All experiments are reproduced 1000 times and standard deviations are less than 0.004.

	Exploration / Recommendation Algorithm	Average simple regret (16,64,256 time steps)	Exploration / Recommendation Algorithm	Average simple regret (16,64,256 time steps)
	Strategic choice in 7x7 killall Go (with symetry-breaking; 4 possible choices)	Strategic choice in 7x7 killall Go (without symetry-breaking; 11 possible choices)
	unif. sampling, EBA UCB+MPA UCB+UCB UCB+LCB Bernstein+LCB UCB+EBA EXP3+EDP	0.092 0.0603 0.0244 0.079 0.0563 0.022 0.0673 0.0523 0.0304 0.0751 0.0466 0.0222 0.0633 0.0537 0.0226 0.0744 0.0474 0.0185 0.0849 0.0809 0.0748	unif. sampling, EBA UCB+MPA UCB+UCB UCB+LCB Bernstein+LCB UCB+EBA EXP3+EDP	0.121 0.0973 0.0488 0.127 0.0677 0.0235 0.0835 0.0826 0.0543 0.0976 0.0656 0.0213 0.116 0.076 0.0488 0.104 0.0657 0.0222 0.1 _ 0.1 0.094
	SR	0.0627 0.0448 0.021	SR	0.0987 0.0557 0.0232
	adaptUCBE, EBA	0.0707 0.0483 0.0188	adaptUCBE, EBA	0.103 0.067 0.023
	4 artificial options, with reward unif. in [0, 1]	11 artificial options, with reward unif. in [0, 1]
	unif. sampling, EBA	0.0652 0.0197 0.00394	unif. sampling, EBA	0.172 0.0614 0.017
	UCB+MPA	0.0535 0.0198 0.00453	UCB+MPA	0.219 0.0263 0.00829
	UCB+UCB	0.064 0.0386 0.00931	UCB+UCB	0.202 0.0837 0.0366
	UCB+LCB	0.0495 0.0142 0.00626	UCB+LCB	0.165 0.0286 0.00758
	Bernstein+LCB	0.0563 0.0191 0.00465	Bernstein+LCB	0.185 0.0513 0.0111
	UCB+EBA	0.0454 0.0175	0.00401	UCB+EBA	0.168 0.0273 0.00708
	EXP3+EDP	0.184 0.145 0.11	EXP3+EDP	0.289 0.238 0.223
	SR	0.0611 0.0205 0.00681	SR	0.123 0.0336 0.0118
	adaptUCBE, EBA	0.0505	0.014 0.00478	adaptUCBE, EBA	0.154 0.0267 0.0083
	4 artificial options, (0.1, 0, 0, 0)			11 artificial options, (0.1, 0, . . . , 0)
	unif. sampling, EBA	0.0509 0.0129 0.0002	unif. sampling, EBA	0.0787 0.0474 0.0073
	UCB+MPA	0.0519 0.0148 0.0001	UCB+MPA	0.0787 0.0509 0.0089
	UCB+UCB	0.0695 0.0277 0.0049	UCB+UCB	0.089 0.0773 0.038
	UCB+LCB	0.0503 0.0155	0	UCB+LCB	0.0776 0.048 0.0074
	Bernstein+LCB	0.0483 0.0136 0.0004	Bernstein+LCB	0.0764 0.0493 0.009
	UCB+EBA	0.0501 0.014 0.0001	UCB+EBA	0.0788 0.0498 0.0094
	EXP3+EDP	0.0706 0.062 0.0524	EXP3+EDP	0.0862 0.0814 0.0765
	SR	0.0532 0.0409 0.012	SR	0.0788 0.0619 0.0319
	adaptUCBE, EBA	0.0528 0.014 0.0001	adaptUCBE, EBA	0.0764 0.0465 0.0079
	Exploration / Recommendation Algorithm	Average simple regret (16,64,256 time steps)	Exploration / Recommendation algorithm	Average simple regret (16,64,256 time steps)
	4 artificial options, (0.9, 1, 1, 1)			11 artificial options, (0.9, 1, . . . , 1)
	unif. sampling, EBA UCB+MPA UCB+UCB UCB+LCB Bernstein+LCB UCB+EBA EXP3+EDP SR adaptUCBE, EBA	0.0151 0.0045 0 0.0189 0.0061 0.0001 0.0179 0.0045 0.0246 0.0167 0.006 0.0001 0.0168 0.0048 0 0.0165 0.0048 0.0001 0.0209 0.0211 0.0214 0.0118 0.0033 0 0.0152 0.0057 0	unif. sampling, EBA UCB+MPA UCB+UCB UCB+LCB Bernstein+LCB UCB+EBA EXP3+EDP SR adaptUCBE, EBA	0.0069 0.0045 0.0007 0.0072 0.005 0.0005 0.0082 0.0051 0.0005 0.0065 0.0041 0.0006 0.0074 0.0048 0.0003 0.0072 0.005 0.0009 0.0076 0.0086 0.0063 0.0052 0.0011 0 0.0072 0.0041 0.0003
	4 artificial options, (0.4, 0.5, 0.5, 0.5)		11 artificial options, (0.4, 0.5, . . . , 0.5)
	unif. sampling, EBA UCB+MPA UCB+UCB UCB+LCB Bernstein+LCB UCB+EBA EXP3+EDP SR adaptUCBE, EBA	0.0176 0.0088 0.0019 0.0128 0.0095 0.0027 0.0157 0.0114 0.0065 0.0142 0.0078 0.0012 0.0167 0.0084 0.0028 0.016 0.0094 0.002 0.0206 0.0189 0.0174 0.0175 0.0105 0.0025 0.0153 0.0081 0.0018	unif. sampling, EBA UCB+MPA UCB+UCB UCB+LCB Bernstein+LCB UCB+EBA EXP3+EDP SR adaptUCBE, EBA	0.0055 0.0042 0.0011 0.0071 0.0032 0.0008 0.0067 0.0037 0.0032 0.0055 0.0017 0.0004 0.0045 0.0039 0.0018 0.0075 0.003 0.0003 0.0074 0.0071 0.0066 0.0062 0.0023 0.001 0.0049 0.0025 0.0009
	4 artificial options, (0.6, 0.5, 0.5, 0.5)		11 artificial options, (0.6, 0.5, . . . , 0.5)
	unif. sampling, EBA UCB+MPA UCB+UCB UCB+LCB Bernstein+LCB UCB+EBA EXP3+EDP SR adaptUCBE, EBA	0.0637 0.0527 0.0277 0.0636 0.053 0.0246 0.0675 0.0561 0.0346 0.0621 0.0494 0.0244 0.0643 0.0498 0.0284 0.061 0.05 0.0257 0.0715 0.0709 0.0665 0.0631 0.0531 0.03 0.0642 0.0509 0.0247	unif. sampling, EBA UCB+MPA UCB+UCB UCB+LCB Bernstein+LCB UCB+EBA EXP3+EDP SR adaptUCBE, EBA	0.0892 0.0824 0.0686 0.0888 0.0764 0.0563 0.087 0.0843 0.0726 0.0875 0.0766 0.0556 0.0869 0.0812 0.0691 0.0862 0.0783 0.0567 0.0887 0.0869 0.0895 0.0868 0.0817 0.0622 0.0868 0.0776 0.0569


Riad Khalil

Phd Bouzidi
email: riad.bouzidi@cstb.fr

Senior Bruno Fies
email: bruno.fies@cstb.fr

Marc Bourdeau
email: marc.bourdeau@cstb.fr

Senior Catherine Faron-Zucker
email: catherine.faron-zucker@unice.fr

Nhan Le Thanh
email: nhan.le-thanh@unice.fr

AN ONTOLOGY FOR MODELLING AND SUPPORTING THE PROCESS OF AUTHORING TECHNICAL ASSESSMENTS

Keywords: Ontology, Semantic Web, Knowledge Management, Building Industry, e-regulations

In this paper, we present a semantic web approach for modelling the process of creating new technical and regulatory documents related to the Building sector. This industry, among other industries, is currently experiencing a phenomenal growth in its technical and regulatory texts. Therefore, it is urgent and crucial to improve the process of creating regulations by automating it as much as possible. We focus on the creation of particular technical documents issued by the French Scientific and Technical Centre for Building (CSTB), called Technical Assessments, and we propose services based on Semantic Web models and techniques for modelling the process of their creation.

INTRODUCTION

In this article, we address the general problem of the creation of regulatory documents and present an engineering overview to help staff in the authoring of new regulations. Our approach takes into account the constraints expressed in the existing statutory corpus. We chose to apply our work in the context of the French Scientific and Technical Centre for Building (CSTB) to help it in the writing of Technical Assessments. The issue is to specify how such assessment document is created and how to standardize its structure using models and adaptive semantic services. A Technical Assessment (in French: Avis Technique ou ATec) is a document containing technical information on the usability of a product, material, component or element of construction, which has an innovative character. We chose this Technical Assessment as a study model because CSTB has the mastership and a wide experience in these kinds of technical documents. We were able to lead interviews on the CSTB site of Sophia-Antipolis with experts directly involved in the drafting of technical assessments. There are multiple users of Technical Assessments:

 Firms working on tender responses and looking for products validated by an Atec;  Manufacturers working on the technical documentation of a new product in order to apply for an ATec;  Insurers who need to verify that a product is implemented according to its domain of use;  Craftsmen looking for a product that correspond to a subfamily and a particular job domain.

The study shows that the technical assessment consists of three parts: (I) an overview and identification of the assessment, (II) the technical assessment itself, formulated by a group of experts from CSTB, and (III) the technical document of the product or process which must be delivered in the technical assessment. We are particularly interested in assisting the creation of technical documents, using entry forms that their enchainment will consider at a time the information modelled in ontology and the entries to be made by the user. In the next section, we describe the process of editing technical assessment; in section 3, we detail our approach to support the creation of technical documents. In section 4, we introduce a tool developed to validate our approach. Finally, we conclude in section 5.

PROCESS OF EDITING TECHNICAL ASSESSMENTS

A Technical Assessment is drafted at the request of an industrial. The industrial starts by sending a request for technical assessment to relevant departments within the CSTB. Then the CSTB instructors transmit to the industrial the resolution of technical assessment and a form for developing the technical document. It is a Word file containing chapters, text and instructions. This form contains all information necessary for the process; the products or materials are studied by a specialized group who will be responsible for delivering the technical assessment. The industrial is supposed to fill in the form and send a complete document to CSTB, which in turn transmits an estimate of the technical assessment to the industrial. Once the estimate is accepted by the industrial, the CSTB instructors will check the contents of the technical document and can ask the industrial to justify some elements shown in his case by experimental tests that will serve as proof of the resistance of the product to various external risks. Site and / or factory visits can be planned to ensure smooth functioning of the manufacturing processes and / or product installation. To be valid the technical document must eventually include a detailed description of the field and conditions of use to the applicant, the requirements for implementation, the experimental results, and the references of use. Once the file is complete, CSTB instructors transfer it to the relevant specialist group. The assignment of this group is to verify the compliance of information according to current standards, and to issue an assessment. Then CSTB instructors publish the assessment on CSTB website and transfer a copy to the industrial. The process above described is ideal. In practice, it is not fully followed. Through our discussions with CSTB experts, it appears clearly that the industrial fails to properly inform the weft of the technical document. A dialogue between CSTB and the applicant too many exchanges are necessary before reaching an acceptable version of the technical file. Without CSTB's accompaniment, most ATec applicants fail to properly complete their technical documents. On its side, CSTB is not able to afford to mobilize resources outside some estimate. The industrial's process is poorly anticipated and considered too administrative. As a direct consequence, this leads to a long casework, about 6 to 8 months. The role of CSTB is limited to verify the contents of the document and not to assist the industrial. The latter must take on the task to fill in the weft of the technical dossier correctly before returning it to CSTB. The slowness of the process is accentuated by the absence of a common format for representing various sources of data that CSTB instructors will be led to examine in the technical document. The technical document is a long Word form sent by CSTB instructors to the industrial to certify their products / processes / materials. This file to be completed is generic for a particular domain. We have realized in our study of ATec in the photovoltaic area of that the technical document to be completed contains information common to all photovoltaic modules, that is to say, information relative to all the products that can be used in the field of photovoltaic. Industrial thus have each to fill the only parts concerning them. But industrials are struggling to understand this file and inquire properly. As a result, the CSTB's instructors receive a badly informed technical document. Following this analysis, we concluded that the process of writing technical documents would benefit from being modelled and supported by tools to guide this creation by identifying at the same time the parts to be informed and the expected information.

MODELLING THE PROCESS OF CREATING TECHNICAL AND REGULATORY DOCUMENTS

In continuation of the work performed at CSTB [START_REF] Yurchyshyna | Modélisation du contrôle de conformité en construction : une approche ontologique[END_REF], on building ontology and checking conformity of construction projects (Gehre and Katranuschkov 2005), we propose to model the process of creating the technical dossier using an ontology-based approach to build a semantically rich model of the weft of the technical document.

Construction of the technical document ontology

We have studied the technical documents issued by the PV group within CSTB with the objective to to build an ontology of the domain based on the terms identified from the weft of the technical document. Many solutions have been proposed for the manual construction of ontologies, notably (Gruninger and Fox 1995), (Ushold and King 1995), Methontology (Gomez-Perez et al. 2003), and On-To-Knowledge [START_REF] Staab | Knowledge Processes and Ontologies[END_REF]. The common idea in these solutions is to reuse as much as possible existing ontologies related to the domain to model. This is the approach that we chose to adopt: we do not address the problems of NLP 1 , we only build an ontology from experts' interviews and by reusing existing ontological resources. Specifically, in our work, with the help of PV experts, we began to identify what knowledge to represent and with which degree of accuracy. From the weft of the technical document, we extracted the terms corresponding to different elements or components of the product to certify . Then, we associated concepts to those terms. Our first result is an ontology where each concept considered relevant to the creation of technical documents has been identified and modelled. We have compared our ontology with the terms of the building thesaurus developed by CSTB for its REEF product. The idea of reusing the CSTB thesaurus is to have a controlled vocabulary and to potentially link / integrate the ATec in the REEF [START_REF] Bus | Reef sémantique, Diffusion et application des textes technico-réglementaires, Accompagnement des pouvoirs publics dans la rédaction des textes officiels[END_REF].

By doing so, we adopted an approach similar to that of [START_REF] Hernandez | TtoO: une méthodologie de construction d'ontologie de domaine à partir d'un thésaurus et d'un corpus de référence[END_REF]): reusing the domain thesaurus that required heavy design efforts for the development of new resources with a higher formal level. This principle is interesting insofar as it avoids building a new ontology from scratch. The design of ontologies from thesauri has the advantage of considering all the terms identified by experts as being representative of the domain.

We adapted this approach to our case study by reusing part of the transformation process proposed by [START_REF] Hernandez | TtoO: une méthodologie de construction d'ontologie de domaine à partir d'un thésaurus et d'un corpus de référence[END_REF]) and merging the resulting ontology with our ontology of technical document. However, the resulting ontology is light, with a minimum of semantics; it contains general concepts of the building industry and it lacks of specific terms of the Photovoltaic industry. To respond to our problem we need a specific concept issue from technical documents. Our approach reflects this in three steps: (I) Extracting hierarchical relationships explicit in the REEF thesaurus, (II) Removing redundancy in hierarchical relations of the thesaurus, (III) Merging REEF ontology resulting of steps (I) and (II) with our ontology of technical documents.

Extracting concepts and relations

For this task, we used the REEF resources, containing a majority of entities in the building field. For example, the core concept of "étanchéité" (sealing) is connected to several more specific concepts (narrower terms) as « joint d'étanchéité » (watertight joint) or « étanchéité à l'air » (airtightness). It is also tied by a relationship "Broad" (broader term) to the concept of « calfeutrage » (draughtproofing).

Figure 2: Extract of REEF thesaurus 1 Natural language processing First, we organized the concepts of the REEF thesaurus hierarchically based on the relation "subclassOf" in the conceptual schema of the ontology. Some hierarchical relationships between concepts are directly derived from explicit links in the thesaurus. To extract the relationships of the thesaurus, the relations "narrower" and "broader" are taken into account. These are selected as potential candidates for "subclassOf" relationships between a concept and the concept to which the related term in the thesaurus.

If not formalized, redundancies in the structure of the thesaurus may exist. Our ontology can be confronted with transitive relations of the inference type: if A is a subclassOf B and B is a subclassOf C, then A is a subclassOf C. A, B, C are concepts the hierarchical relationship between A and C need not be explicit. To remove this type of redundant relationships, we checked the relevance of each relation "is a subclass of". Hernandez offers an analysis through graph theory.

Merging REEF ontology and ontology of technical document

Once we have established the REEF ontology we began the part of integration consisting in bringing closer the REEF ontology concepts with the concepts of the ontology of the Technical document (OntoDT) that have the same label. We aim to clarify the semantics that is vague (soft) around the REEF terms describing the technical document by restricting it to the regulatory aspect of the PV field.

To achieve this integration we chose to merge the REEF ontology and those of technical document (OntoDT). The resulting ontology unifies and replaces the original ontology The most common approaches for merging ontologies use union or intersection to connect the resulting ontology to the original ontologies. In the union approach, the resulting ontology contains the union of entities coming from the original ontologies and suppose resolved the differences of representation of the same concept. In the intersection approach, the resulting ontology contains only the common parts of the original ontologies. We adopted the intersection approach: once the merge is completed, the resulting ontology is the intersection between the REEF ontology and the ontology of technical document Several approaches and systems for merging ontologies have been proposed, including PROMPT [START_REF] Noy | Prompt: Algorithm and tool for automated ontology merging and alignment[END_REF], Chimaera [START_REF] Mcguinness | The chimaera ontology environment[END_REF], OntoMerge [START_REF] Dou | Ontology translation by ontology merging and automated reasoning[END_REF]. We chose PROMPT as a tool for merging the REEF ontology and the technical document ontology as it creates a complete ontology. It identifies a set of operations for ontology merging (fusion classes, merging of links) and a set of possible conflicts resulting from the application of these operations (name conflicts, redundancy in the class hierarchy). As a result, our ontology of technical document has 50 classes and 26 properties formalised in the OWL2 Lite language. 35% of these classes are created from REEF terms. The remaining 65% are concepts more specific than those of the REEF thesaurus, which contains general concepts of the building industry. In its current state, it lacks specific terms relative to a particular field (Photovoltaic). However, it remains in constant evolution

Modelling the technical document

We use our ontology of the technical document to represent the technical document. Our approach is to model the semantics conveyed by the technical document to a formal interpretable knowledge. We changed the formatting of the technical document as a set of forms interconnected with each other, each one relative to a component of the product to be described. Each form contains components that represent the nomenclature of the same product, the component itself may be formed of one or more elements.

For example, a PV glass polymer module (a component) enters into the composition of a PV panel (the product). This glass polymer module is composed of several elements: polymer film, photovoltaic cell, etc. (elements).

To model this composition, each concept representing a component or an element or a product is defined by an axiom. Axioms are used in the definition of an ontological class, they are of the form A ⊑ B, where A is a primitive concept (Product) and B description composed concept. For instance, Figure 3 provides the definition of class VerrePolymere in the OWL language: it is a subclass of class We have described the interdependencies between the different concepts modelling the interactions or interdependencies between parts of PV modules. These have a number of intrinsic characteristics (length, weight, manufacturer, etc.) represented in our modelling by properties attached to the corresponding concepts. Once the industrial fills in the form relative to a concept with all the elements relative to its definition, they are stored in an RDF3 annotation file. By doing so, we acquire an interoperable representation of a technical document, reusable in other systems. The use of the RDF model will allow us later to check the conformity of the technical document with the standards of the photovoltaic domain.

Modelling the process of writing a technical document

The question which now arises, is how to model the process itself of filling the technical document, in order to produce a dynamic sequence of forms to fill. The dynamicity stands in the fact that the forms to fill in depend on the way previous forms are filled in: we want to adjust to the information provided without requiring him to fill irrelevant parts of the technical document. Our approach is to ask first of high-level information (name the type of product, etc.) then browse the explicit dependency rules in the ontology to seek all information required for a product. Each information provided by the industrial will be confronted to the ontology and will determine the next interaction. The industrial has to choose in a first form a product among all those concerned with the photovoltaic field. From that first choice, based on our ontology, we determine the list of components used in its manufacture and we offer a list of corresponding forms. The dynamicity of the sequence of forms relies upon a SPARQL4 query pattern presented in Figure 4 that we instanciate to query the ontology to determine each next form. More precisely, by using this query template, we query a product on its composition by questioning its definition. The concepts involved in its definition are returned by the query and are so much information that the industrial must provide through entry forms generated on the fly. The chaining of forms thus depends on the query results: each form corresponds to one or more elements of the result. For example, the query below searches the ontology on the definition of the concept "VerrePolymere".

SELECT ?Composant WHERE{ ?x rdfs:subClassOf ?y FILTER( ?x=dt:VerrePolymere) ?y owl:intersectionOf ?z ?z rdf:rest*/rdf:first ?f ?f owl:onProperty ?p ?f owl:someValuesFrom ?Composant}

The result is that "VerrePolymere" is a module which has as components a "Cadre", a "CellulePhotoV", etc.

Result : [Cadre, CellulePhotoV, FilmPolymere, VerreInterieur…] At each step of the process of writing a technical document, we display to the industrial a form for entering information related to a concept belonging to the result of such a query. If this concept is itself defined, the same query template is instanciated with a new query in order to provide the Industrial with new forms matching with the components involved in the definition of the current concept. The same query pattern is recursively instanciated until reaching terminal concepts, i.e. primitive concepts (with no definition). As a result, the industrial browses thereby transparently into our ontology to complete all components of its product by filling out the forms provided; only relevant questionnaires are displayed.

SUPPORT TOOL FOR THE CREATION OF TECHNICAL DOCUMENTS

To validate our model, we developed a tool to assist in the creation of technical documents. This application has been developed in J2EE. It conforms to the three-tier architecture. The first third consists of a web page on the client side (GUI) that supports various forms requiring to be filled in by the industrial. The second third on server side is a servlet containing business code that interacts with the GUI part and the business part. It is connected to the CORESE5 semantic engine [START_REF] Corby | Querying the SemanticWeb with Corese Search Engine[END_REF]) to query the ontological knowledge that represents of the technical documents and generates the RDF model of the filled technical document. The last third is relative to the data. It includes the ontology of the technical document and information of the product stored as RDF annotations.

Our tool provides the industrials with a rich interface, interactive and easy of handling. At the launch of the application, a first general form allows the industrial to define the context of its technical document. It is at this first level of choice in a dropdown lists. The choices correspond to concepts of the ontology of technical documents whose labels correspond to the vocabulary defined in the thesaurus of the REEF. Depending on the choices made by the industrial in this first level, the system adapts and goes through the ontology to seek to progressively more specific information. These sequences of forms are orchestrated through SPARQL queries that run on the ontology of the technical document. At the end of the sequence of forms, two files are generated: a readable file in format PDF / HTML containing the information filled in by the industrial, and a semantic description of the document in RDF. This will be exploited to help in writing the technical assessments itself, by automatically checking the conformity of the information in the technical document with the regulatory texts of the domain. We developed a first version of this tool and we have submitted to functional tests with photovoltaic instructors of the CSTB. This allowed us of validate the pertinence of our approach.

CONCLUSION

In this paper, we have presented an innovative approach to support the authoring of technical documents by industrials, and thus get technical assessment on their products more quickly. Our approach is based on the construction of an ontology relative to the concerned domain which concepts represent different elements of the technical document This knowledge is exploited through a semantic query pattern to establish a dynamic chaining of forms. The instanciation of this query pattern provides a dynamic chaining of forms, coherent with user entries, where no component of the product is missing, where the entire elements specific to the product are shown. We have developed a tool to assist the creation of technical documents based on such a dynamic chaining of forms. It is based on the languages and techniques of the Semantic Web, ensures the interoperability of knowledge, and manipulated the results A first version exists which allowed us to validate our approach. We now need to enrich the ontology to compare our tool to a real use case.

Figure 1 :

 1 Figure 1: The process of creating technical assessment

Figure 3 :

 3 Figure 3: Example of a defined concept

Figure 4 :

 4 Figure 4: Extract of the SPARQL query pattern

http://www.w3.org/TR/owl-ref/

http://www.w3.org/RDF/

http://www.w3.org/TR/rdf-sparql-query/

http://www-sop.inria.fr/edelweiss/software/corese/


INTRODUCTION

Regulations in the Building Industry are becoming increasingly complex and involve more than one area. They cover products, components and project implementation. They also play an important role to ensure the quality of a building, its features, and to minimize its environmental impact. For 30 years, CSTB proves its expertise in this field through the development of the complete encyclopaedia of French technical and regulatory texts in the domain of the construction: the REEF. In the framework of a collaboration between CSTB and the I3S laboratory, we work on the acquisition of knowledge from technical and regulatory information contained in the REEF and the automated processing of this knowledge with the final goal of assisting professionals in the exploitation of these texts and the creation of new texts. We implement our work in CSTB to help in the writing of Technical Assessments. It is a question to specify how these assessments are created and how to standardize their structure using models and adaptive semantic services.

A Technical Assessment (in French: Avis Technique or ATec) is a document containing technical information on the usability of a product, material, component or element of construction, which has an innovative character. We chose Technical Assessments as a study model because CSTB has the mastership and a wide experience in these kinds of technical documents.

A Technical Assessment is drafted at the request of an industrial. The industrial starts by sending a request for technical assessment to relevant departments within the CSTB. Then the CSTB instructors transmit to the industrial the resolution of technical assessment and a form for developing the technical document. It is a preformatted Word file containing chapters, text and instructions on how to fill it out. When done, the document is supposed to describe with the right accuracy the process, product or material candidate for a Technical Assessment. This document is therefore studied by a specialized group who will be responsible for delivering the technical assessment. The industrial is supposed to fill in the form and send a complete document to CSTB.

We are particularly interested in this paper to model regulatory constraints that validates the Technical Assessment. In section 2 we describe the practical guides. In section 3 we present our approach to model regulatory constraints. In section 4 we detail our approach to interpret compliance checks results. Related work is discussed in section 5.We conclude in Section 6.

O. Corby

INRIA Sophia Antipolis, France

ABSTRACT: Regulations in the Building Industry are becoming increasingly complex and involve more than one technical area. They cover products, components and project implementation. They also play an important role to ensure the quality of a building, and to minimize its environmental impact. In this paper, we are particularly interested in the modeling of the regulatory constraints derived from the Technical Guides issued by CSTB and used to validate Technical Assessments. We first describe our approach for modeling regulatory constraints in the SBVR language, and formalizing them in the SPARQL language. Second, we describe how we model the processes of compliance checking described in the CSTB Technical Guides. Third, we show how we implement these processes to assist industrials in drafting Technical Documents in order to acquire a Technical Assessment; a compliance report is automatically generated to explain the compliance or noncompliance of this Technical Documents.

Technical guides are regulatory complements offered by CSTB to industrials. They do not replace the texts, regulations (decree, circular), normative (DTU) or code (Atec). They enable an easier reading of technical rules and collect details of execution presenting a wide range of possible implementations. The main actors concerned by these guides are project owners, contractors, firms. The main purpose of these documents is to address issues of health and safety faced by industry in particular during the design phase.

There are many case studies, diagrams, summary tables. The major regulatory requirements which must be respected (safety, hygiene, accessibility, performance) are based on the product and the nature of its implementation. Also, the proposed solutions to the risk that could threaten the safety or health of users are discussed and clearly illustrated with examples. To sum up, these guides provide an exhaustive description of the available knowledge helping to verify the conformity of a product to the regulations: definition of the risks, diagnosis, technical solutions, choices, implementation, compatibility with existing rules, controls, usage examples and useful links.

Classification of guides

The guides provided for our work contain information to verify the validity of technical documents provided by the manufacturers. They are made in a way to simplify the understanding and application of the law. Also, they include all the structural and dimensional characteristics related to the validation of the construction products.

However, our goal is to organize these guides on a query base that can be exploited by a system. The organization of this base will be according to classification criteria issued from the structure of the guides. We propose a classification according to three criteria:



MODELLING OF REGULATORY CONSTRAINTS

Regulatory constraints of guides

Regulations that validate technical documents are first defined and represented in a language understandable by humans (experts and nonexperts). In guides, the regulations have legal status derived from DTU. After reviewing various studies related to technical regulations, we have identified a structure to implement a process functionally complete to verify technical documents.

We use the guide "The coverage and tile" issued by CSTB in our work as a study model. Our first goal is to build a domain ontology based on the terms identified in the thread of the technical documents and contained in this guide. This ontology captures the different types of tile and their characteristics. Also, it defines their conditions of implementation and verification of various criteria such as: slope of tiles, support or climatology of where they should be installed. Monitoring of these instructions is drastic since the non-compliance with a requirement leads to a non-validation of the technical document. Each tile has a shape and a material according to these criteria. We were able to identify nine different types of tiles. In addition to its material and its form, each tile has an implementation that includes a slope support, an installation and an attachment. These characteristics are different from one tile to another hence the difference of their types:

 The slopes: the minimum allowable slopes for the types of tiles are given in the guides according to application areas and specific situations of exposition.  Establishment of support: the tiles are based on a wooden litonnage which the elements are fixed at the rate of a point or a clip at each intersection of a chevron and a batten.  Fixation: it is designed to maintain the assembly of the tiles with each other's when the wind effects risk to disturb the schedule. The fixing of tiles, if not total, is in a distributed manner, by nailing, and / or crocheting. A convention must exist between the regulations (verification requests) and the structural properties of the Technical Documents. In our ontology, we considered this convention and integrated the content of the guides.

Construction of the technical document ontology OntoDT

Many solutions have been proposed for the manual construction of ontology among them (Gruninger and Fox, 1995), (Ushold and King, 1995) Methontology (Gomez-Perez et al. 2003), On-To-Knowledge [START_REF] Staab | Knowledge Processes and Ontologies[END_REF]. The common idea in these solutions is to reuse as much as possible existing ontologies related to the domain. This is the approach we adopted: we do not address the problem of NLP, we build an ontology from expert's interviews and by reusing existing ontological resources.

Specifically, in our work, with the help of photovoltaic experts, we began to identify what knowledge to represent along with the desired level of accuracy. From the technical documents, we extracted the terms corresponding to different elements or components of the products to certify. Then, we associated concepts to these terms. Our first result was an ontology where each concept considered relevant to the creation of technical documents is identified and modeled. We have confronted our ontology with the REEF thesaurus of the building domain developed by CSTB. The idea of reusing this Thesaurus is to have a controlled vocabulary and to link or integrate the technical advices to the REEF [START_REF] Bus | Reef sémantique, Diffusion et application des textes technico-réglementaires, Accompagnement des pouvoirs publics dans la rédaction des textes officiels[END_REF].

By doing so, we adopted an approach similar to that of [START_REF] Hernandez | TtoO: une méthodologie de construction d'ontologie de domaine à partir d'un thésaurus et d'un corpus de référence[END_REF]): reusing the domain thesaurus that required heavy design efforts for the development of new resources with a higher formal level. This principle is interesting insofar as it avoids building a new ontology from scratch. The design of ontologies from thesauri has the advantage of considering all the terms identified by experts as being representative of the domain.

We adapted this approach to our case study by reusing part of the transformation process proposed by [START_REF] Hernandez | TtoO: une méthodologie de construction d'ontologie de domaine à partir d'un thésaurus et d'un corpus de référence[END_REF]) and merging the resulting ontology with our ontology of technical document. However, the resulting ontology is light, with a minimum of semantics; it contains general concepts of the building industry and it lacks of specific terms of the Photovoltaic industry. To answer our problem we need specific concepts issued from technical documents.

Our approach reflects this in three steps: (I) Extracting hierarchical relationships explicit in the REEF thesaurus, (II) Removing redundancy in hierarchical relations of the thesaurus, (III) Merging the REEF ontology resulting of steps (I) and (II) with our ontology of technical documents.

Extracting concepts and relations

For this, we use the resources of the French REEF thesaurus, containing the major entities in the building industry. For example, the central concept of "étanchéité" (sealing) is connected to several more specific concepts (narrower) as "joint d'étanchéité" (sealing gasket) or "étanchéité à l'air" (airtightness). It is also tied by a relationship "broad" (broader term) to the concept of "calfeutrage" (caulking).

First, we hierarchically organize concepts corresponding to terms in the REEF thesaurus with the "subclassOf" relation. Some hierarchical relationships between concepts are directly acquired from explicit links present in the thesaurus: relations "narrower" and relations "broader" in the thesaurus. They are selected as candidates for eliciting a hierarchical relation between the concepts in the ontology corresponding to the related terms in the thesaurus.

If not formalized, redundancies in the structure of the thesaurus may exist. Our resulting ontology therefore initially contains some redundancy relative to the transitivity of the relations: if A is a subclass of B and B is a subclass of C, then A is a subclass of C: the hierarchical relationship between A and C need not be explicit. To remove this type of redundant relationships, we checked the relevance of each of the relations. Hernandez proposes an automatic analysis through graph theory operations.

Merging of the REEF ontology and the ontology of technical document

Once the REEF thesaurus has been transformed into the now so-called "REEF ontology" following the two steps described above, we integrate this ontology with the concepts of the ontology of the Technical document. We aim to explicit the semantics of the REEF terms describing the technical documents relative to the regulatory aspect of the photovoltaic field. The resulting ontology unifies and replaces the original ontology.

The most common approaches for merging ontologies use union or intersection to connect the resulting ontology to the original ontologies. In the union approach, the resulting ontology contains the union of entities coming from the original ontologies and suppose resolved the differences of representation of the same concept. In the intersection approach, the resulting ontology contains only the common parts of the original ontologies. We adopted the intersection approach: once the merge is completed, the resulting ontology contains:

 The intersection between the REEF ontology and the ontology of technical document  Concepts specific to the Technical Document. Several approaches and systems for merging ontologies have been proposed, including PROMPT [START_REF] Noy | Prompt: Algorithm and tool for automated ontology merging and alignment[END_REF], Chimaera [START_REF] Mcguinness | The chimaera ontology environment[END_REF], OntoMerge [START_REF] Dou | Ontology translation by ontology merging and automated reasoning[END_REF]. We chose PROMPT as a tool for merging the REEF ontology and the technical document ontology as it creates a complete ontology. It identifies a set of operations for ontology merging (fusion of classes, merging of links) and a set of possible conflicts resulting from the application of these operations (name conflicts, redundancy in the class hierarchy). As a result, our ontology of technical document called OntoDT has 121 classes and 39 properties formalized in the OWL Lite language. 35% of these classes are created from REEF terms. The remaining 65% are concepts more specific than those of the REEF thesaurus which only contains general concepts of the building industry. In its current state, it lacks specific terms relative to a particular field (e.g. Photovoltaic). However, it remains in constant evolution.

Integration of guides into OntoDT

We use the same approach to formalize information collected from the guide "Coverage and Tile". Each tile is represented as a concept and integrated into OntoDT. The ontology includes all the semantics that reflects the structural and dimensional criteria of a tile, these criteria are represented by properties.

To model each type of tile with its characteristics, we used the notion of axiom to represent this structure. This knowledge contains specific information to a particular area, they are called "domain axioms".

The modeling as an axiom allows us to describe general knowledge. It includes the definition of concepts and properties.

The following axiom provides a definition PlatClayTile ≡ Tile ˄ hasaMaterial.Clay ˄ hasAForm.Flat ˄ etc

MODELLING GUIDES

We aim to show how it is possible to model the guides by representing the semantics of these rules. This knowledge is extracted manually from texts which they are derived. We will use for this SBVR formalism. It is based on a controlled vocabulary of the ontology OntoDT.

SBVR "Semantics of Business Vocabulary and Business Rules"

SBVR stands for "Semantics of Business Vocabulary and Business Rules". It is an OMG standard whose ultimate objective is to provide a meta-model that allows establishing data exchange interfaces for tools that create, organize, analyze and use vocabularies and business rules [START_REF] Chapin | Semantics of Business Vocabulary & Business Rules (SBVR)[END_REF]. The SBVR meta-model facilitates the validation, analysis, alignment, and fusion of business rules for different tools of different constructors.

The development of an SBVR repository is done in two steps: the development of a business vocabulary and the writing of business rules based on the terms and concepts defined in the vocabulary. SBVR controlled vocabularies consist in hierarchies of concepts specific to some domains, their relationships, definitions and synonyms. In our case, the SBVR vocabulary is represented in Technical document ontology OntoDT.

However, technical standards can be understood in different ways that is why the manual intervention of a domain expert is essential. We argue that NLP approaches of knowledge extraction from regulatory texts can significantly alleviate the task of domain experts but cannot replace them. In our work, we do not consider linguistic analysis of texts and focus on the representation of expert knowledge. CSTB experts helped us to identify and classify the constraints expressed in the photovoltaic standards and then the rules which represent them. The goal of this categorization is to determine the levels of interoperability of each sentence or paragraph of the standards and classify it.

Once these texts are identified, a step of disambiguation is necessary. The transformation of texts into SBVR rules will provide a normative, unambiguous and reusable source.

The extraction of rules from standards or statutory text is a tedious job, it often requires to the structure the information. The regulations used have been detailed enough to show how their content can be converted into SBVR vocabulary and business rules. However, a clarification of the text was needed before the transformation into SBVR.

Example: Let us consider the following example:

This table is extract from the guide "coverage and tile" expresses the acceptable slope for the plat till made with clay. We reformulate this table into set of SBVR rules

In our eg of SBVR rules we use several font styles:

 Concept are underlined in green color  Properties are underlined in blue color  Literal values are underlined in red  Nouns and other information are given in orange

The concepts identified in this fragment are Tile, Zone1, Protected, which belong to the ontology of technical document.

Implementation of SBVR rules

In certain implementation process is based on the interpretation of the expert and its translation of knowledge into computer language. In other cases the logic of statements of human language is formally interpreted and later translated into language processable. However, our goal is to model the way where experts use CSTB guides and try to automate their know-how. It forces us to follow their interpretation and to establish a formal representation of regulations (requests or rules). SBVR describes the concepts and requirements regardless of their implementations.

To validate our model, we developed a rule base to verify the compliance of DT with regulatory standards expressed in guides. The availability of verifications information maybe addressed as follows:

 Provide explicit information in the DT model. While this is natural for some aspects (material, form), others aspects are derived from more basic information and rely on fallible human judgment that are current causes of error (slope, fastening, fixing).  Requests for verification are important they apply on properties that require more analysis like structural, dimensional or climatological constraints. Our SBVR rules are implemented in SPARQL language. It allows reasoning automatically on the representation of regulatory and modelling the process of compliance check. This analysis model must implement a set of verification queries associated to a model of DT and to process of compliance check.

We organized the basic SPARQL queries representing different regulatory constraints in a process of compliance check. For each elementary component involved in a DT we associate a verification process consisting of SPARQL queries sequences that verify the compliance of its characteristics. This RDF representation called "elementary process" contains in addition to SPARQL "ASK" queries an SBVR rule and other elementary process (if the element contains several components in its nomenclature) Figure 2. For example: the elementary process of compliance testing slopes eligible for a tile contains SPARQL queries of compliance checking the slope and a SBVR representation of these regulatory constraints. A complex process of verification is also defined recursively. It is built automatically from elementary processes associated with the components entering into its definition, under OntoDT ontology. Let's take the photovoltaic module "polymer glass" as an example, this module contain in its nomenclature: photovoltaic Cell, polymer glass and should be implemented on tiles.

The complex process of this module should contain elementary process of: photovoltaic Cell, polymer glass and tile. This declarative representation as RDF annotation uses a resolution formalism, which allows monitoring, coordinating and describing an execution sequence in which we can run one or several queries sequentially with an abstract syntax. This controlled vocabulary is supported by the engine Kgram [START_REF] Corby | The KGRAM Abstract Machine for Knowledge Graph Querying[END_REF]) and consists of four properties (body, if, then, else) and 7 classes where the class "Pipeline" is the main class that describes the beginning of annotation verification.

As shown below, this vocabulary can load, execute a set of rule or request and run on-demand queries/rules when a specific condition is met. Also, it can invoke other processes including the process itself. This notion of recursion allows to model complex process of solving where each process contains a description of one or several SPARQL queries.



Supporting Technical Assessment

The implementation of our compliance checking model is based upon the matching of standards representations with those of a DT, i.e. the matching of SPARQL queries with RDF annotations if there are conditions for applying the standard. For this purpose, we use the KGRAM semantic engine.

One major problem when automating the compliance checking process is to justify the decisions taken by the systemthe compliance or noncompliance of the product. Guides (Technical standards) that validate the products are modelled as set of compliance checking requests. The fail of these requests means the noncompliance of some components and involves a non-validation of the DT. The key point is to identify the source of this noncompliance by demonstrating the "Why" of this noncompliance and explain this negative decision to the industrials.

We use the KGRAM engine that implements the notions of "Event" and "Event Listener" allowing them to catch some predefined events in the inference engine. Some of these events are related to success or failure of execution of SPARQL queries.

In our case, we implement a program that's designed to intercept and identify which events are generated after the execution of the SPARQL queries. Thus we can identify the real cause of noncompliance by identifying the request failed and the cause of this failure. Once the condition is checked, non-compliance identified, a SPARQL query pattern is executed Figure 4 with as a parameter the ID of the non-compliant component. The results are one/several SBVR formulations related to regulations that validate this component. We sent these results as a noncompliance report to the users (industrials). In our case it is essentially the "why" of the negative decision. We use a knowledge base containing a list of justification established by experts in Figure 5. Each justification or answer is unique to a single state of non-compliance. The answer is extracted using another query pattern that takes as input the noncompliant component and displays the appropriate response. To summarize the process is triggered when a non-compliance of DT is identified. The verification of the parameters of non-compliance is achieved in Kgram engine. We identify the failing part of the query by retrieving the relative event. Each rule in this control process has a semantic link to a SBVR rules to explain the cause of non-compliance.

RELATED WORK

Regulatory modelling becomes an important issue. This issue was discussed under two different approaches. The first is to automatically analyse the regulations and to confront the complexity of natural language [START_REF] Dinesh | Reasoning about conditions and exceptions to laws in regulatory conformance checking[END_REF]). In the second, regulatory constraints are written in normalized manner with the expert's help, which facilitates their translation into formal language [START_REF] Reeder | Usability challenges in security and privacy policyauthoring interfaces[END_REF]), [START_REF] Nazarenko | Integrating Written Policies in Business Rule Management Systems[END_REF].

Our approach provides a third way, it takes account the regulations written in natural language, offers a tool for writing technical regulatory and automatically analyses the content of these documents.

In parallel, various efforts have been made to apply conformity rules on IFC representation or textual descriptions [START_REF] Yurchyshyna | Modélisation du contrôle de conformité en construction : une approche ontologique[END_REF], [START_REF] Pauwels | A semantic rule checking environment for building performance checking[END_REF][START_REF] Eastman | Automatic rule-based checking of building designs[END_REF]. The originality of our work is the combination of basic SPARQL queries and SBVR rules derived from regulation itself and use both to explain the why of decision making.

CONCLUSION

We are particularly interested in the modeling of the regulatory constraints derived from the Technical Guides and used to validate the Assessment. These Guides are regulatory complements offered by CSTB to the various industrials to enable easier reading of technical regulations. We formalize this GP in a machineprocessable model to assist the creation of Technical Assessments by automating their validation.

First, we constructed a domain-ontology, which defines the main concepts involved in the Technical Guides. This ontology called "OntoDT" is coupled with domain thesauri. Several are being developed at CSTB among which one seems the most relevant by its volume and its semantic approach: the thesaurus from the REEF project.

Our second contribution is the use of standard SBVR (Semantics of Business Vocabulary and Business Rules) and SPARQL to reformulate the regulatory requirements of guides on the one hand in a controlled language and on the other hand in a formal language Third, our model incorporates expert knowledge on the verification process of Technical Documents. We have organized the SPARQL queries representing regulatory constraints into several processes. Each component involved in the Technical Document corresponds to a elementary process of compliance checking. An elementary process contains a set of SPARQL queries to check the compliance of an elementary component. A full complex process for checking a Technical Document is defined recursively and automatically built as a set of elementary processes relative to the components which have their semantic definition in OntoDT.

Finally, we represent in RDF the association between the SBVR rules and SPARQL queries representing the same regulatory constraints. We use annotations to produce a compliance report in natural language to assist users in the writing of Technical Assessments.

As a result, we have designed a Semantic Web application to support and guide the process of writing Technical Assessment. The current version has allowed us to validate our approach. Also, we have developed a base of SBVR rules to describe business requirements of guides. This base of rules is implemented in SPARQL language. The experimentation and full evaluation, however, must be completed. In the future, we would like to enrich the OntoDT ontology and to compare our tool to a real use case

  <owl:Class rdf:about="#VerrePolymere"> <rdfs:subClassOf rdf:resource="#ModulePhotoV"/> <rdfs:subClassOf> <owl:Class> <owl:intersectionOf rdf:parseType="Collection"> <owl:Restriction> <owl:onProperty rdf:resource="#hasComponent"/> <!--CableElectrique --> <owl:someValuesFrom rdf:resource="http://www.cstb.fr/reef/#01573"/> </owl:Restriction> <owl:Restriction> <owl:onProperty rdf:resource="#hasComponent"/> <!--Cadre --> <owl:someValuesFrom rdf:resource=" http://www.cstb.fr/reef/#01593"/> </owl:Restriction> ... </owl:intersectionOf> </owl:Class> </rdfs:subClassOf> </owl:Class>

Figure 1 :

 1 Figure 1: Example of a defined concept

Figure 2 :

 2 Figure 2: Extract of the process of compliance check

Figure 3 :

 3 Figure 3: Example of the process of compliance check

Figure 4 :

 4 Figure 4: Extract of the request pattern

Figure 5 :

 5 Figure 5: Extract of SBVR response