Samir Medjiah
email: medjiah@labri.fr

Toufik Ahmed

Eleni Mykoniati
email: e.mykoniati@ee.ucl.ac.uk

David Griffin
email: dgriffin@ee.ucl.ac.uk

Scalable Video Streaming over P2P Networks: A Matter of Harmony?

Keywords: P2P Video Streaming, H.264/SVC, Mesh-based P2P, Pull Delivery, Optimization, Harmony Search

In this paper we address the problem of efficient layered video streaming over peer-to-peer networks and we propose a new receiver-driven streaming mechanism. The main design goal of our new layered video requesting policy is to optimize the overall distribution of video streams in terms of reliability and overhead. Since the layered peer-to-peer streaming problem is NP-Hard, we show that the classic approaches widely used in layered P2P streaming systems have some limitations and we propose an optimization technique based on harmony search which aims at increasing the rate of successful data transmissions for the most important video layers, while reducing the protocol overhead and ensuring load balancing among the participating peers. Analytical results have demonstrated that our new requesting policy enhances the streaming of layered video over mesh-based peer-to-peer networks and outperforms classic approaches.

I. INTRODUCTION

Nowadays, Peer-to-Peer (P2P) video streaming has become a popular service in the Internet. P2P streaming systems such as CoolStreaming [1], PPLive [2], UUSee [3], Sop-Cast [4], and TVAnts [START_REF] Zhang | DONet/CoolStreaming: a data-driven overlay network for live media streaming[END_REF] attract a lot of users. As more users get used to viewing multimedia content on-line, they will demand higher video quality than what is available with current P2P streaming systems. Providing high-quality streaming over P2P systems, however, faces multiple challenges, including: (i) the limited upload capacity of peers, (ii) high heterogeneity of receivers in terms of download bandwidth, screen resolution, and CPU capacity, and (iii) high churn rate as the peer population is constantly changing. Addressing these challenges requires not only increasing the capacity of peers and deploying additional seeding servers to make up the shortage in resources, but also employing novel methods for encoding and distributing multimedia content and developing algorithms and protocols to optimally utilize the available resources.

Most of the currently deployed P2P streaming systems, e.g., [1][2] [3][4] [START_REF] Zhang | DONet/CoolStreaming: a data-driven overlay network for live media streaming[END_REF], do not use scalable video streams. Thus, they serve a single version of the video stream to all peers, and therefore they have limited support for heterogeneous peers. To address these issues, several studies have proposed P2P streaming systems with scalable video streams, e.g. [START_REF] Cui | Layered peer-to-peer streaming[END_REF][7] [START_REF] Lan | A peer-to-peer architecture for efficient live scalable media streaming on Internet[END_REF] [9] [START_REF] Rejaie | PALS: peer-to-peer adaptive layered streaming[END_REF]. Cui and Nahrstedt [START_REF] Cui | Layered peer-to-peer streaming[END_REF] presented an algorithm to decide at each receiver how to request video layers from a given set of senders. They assume that layers have equal bitrate and provide equal video quality. However, in Scalable Video Coding (H.264/SVC), layers do not have equal bitrate (spatial scalability enhancement layers may require more bandwidth than the base layer). Hefeeda and Hsu [START_REF] Hefeeda | Rate-distortion optimized streaming of fine-grained scalable video sequences[END_REF] studied the problem of video streaming in P2P networks for Fine-Grained Scalable (FGS) videos, taking into account the ratedistortion model of the video for maximizing the perceived quality. Rejaie and Ortega [START_REF] Rejaie | PALS: peer-to-peer adaptive layered streaming[END_REF] presented a framework for layered P2P streaming, where a receiver coordinates the transmission of video packets from multiple senders using a TCP-friendly congestion control mechanism. The allocation of seed server resources in P2P streaming systems with scalable videos has been also considered in [START_REF] Mokhtarian | Efficient allocation of seed servers in peer-to-peer streaming systems with scalable videos[END_REF]. Lan et al. [START_REF] Lan | A peer-to-peer architecture for efficient live scalable media streaming on Internet[END_REF] proposed a scheduling algorithm for peers to request data from senders. These papers do not consider optimal delivery of data units in terms of reliability and overhead in case of SVC content having the following characteristics: (1) Inter-layer dependency, (2) layers with different and variable bitrates, and (3) consumers may view different sub-streams of the original content. In this paper, we considered a mesh-based peer-topeer architecture in order to distribute a layered video content (H.264/SVC). The main idea behind our contribution is the use of lightweight optimization heuristic in order to perform efficient content pulling in terms of small network overhead, reliability and load balancing. The rest of this paper is organized as follows: section II introduces harmonious requesting policy, section III presents and discusses the performance evaluation results and finally, section IV concludes the paper.

II. HARMONIOUS REQUESTING POLICY

We present in sub-section II.A the problem formulation of layered video delivery in a mesh-based peer-to-peer architecture. Given the information at each receiving peer (pieces to request, neighbouring peers, pieces availability …), we present a heuristic-based solution to solve the problem in sub-section II.B.

A. Problem Formulation

An overlay network is constructed upon an SVC stream; the overlay may be composed of different peers with different These peers are interested in different stream scalabilities (i.e. different sub-streams). For example, a mobile device is interested in a lower spatial resolution, while a TV-set is interested in higher spatial resolution. Thus, the requested content differs from one peer to another one. Figure 1 shows an overview of such configuration. In the following sub-sections, we introduce the necessary definitions to formulate our requesting policy (i.e. how the pieces are being requested from the P2P network):

A.1. Layer-encoded Stream:

In our architecture, we have considered an SVC video to be streamed over the P2P network. The H.264/SVC format introduces three types of scalability: Spatial scalability: by layering image resolution, Temporal scalability: by layering the frame rate, Quality scalability: by layering the image compression ratio. Thus, any combination of the three scalabilities is called a "layer". The first combination of the lower scalabilities is called the Base Layer (BL) while the other layers (i.e. other combinations) are called Enhancement Layers (ELs) and may depend on lower layers in order to be decoded. Regarding the SVC bitstream, it can be seen as a collection of atomic data pieces named Network Abstraction Layer Units (NALUs).

Figure 2 shows a 3D representation of an SVC stream. In this figure, we can see that the stream contains three spatial resolutions (QCIF, CIF, 4CIF), four temporal resolutions (3.25, 7.5, 15 and 30 fps) and three quality levels (low, medium, and high). From this stream we can view any combination of the three types of scalability. For example, the NALUs that are shown in dark represent the necessary NALUs to extract in order to decode a CIF resolution stream with 7.5 frames/s and having a medium image quality.

A.2. Layered Video Pieces:

A stream map is a data structure that describes the entire SVC stream and it contains all the necessary information about all the NALUs that form the bitstream. Each piece π j is described by its offset o j in the overall stream, its size s j , and the index of the layer l j it belongs to (i.e. π j =(o j ,s j ,l j )). In the other side, the buffer map is a data structure that describes the availability of the different pieces (as described in the stream map) at a local peer. The buffer map is more likely a set of flags that indicate whether the peer has the corresponding NALU or not.

A.3. Peers:

In our architecture, each peer maintains a set of peers

} , , , , { = Π 3 2 1 N p p p p
serving the video stream. Each peer i p is associated with information used to estimate its reliability i r to deliver the video stream. This information includes: (1) the similarity of its buffer map with the local one, (2) the ratio of satisfied requests so far and (3) information about its uplink capacity.

A.4. Pieces Availability:

When a peer connects to the overlay to begin downloading the stream, it exchanges a buffer map that indicates the availability of the pieces described in the stream map. Considering a stream that contains K pieces, then the buffer map is as follows:

else available is piece the if b K} b j j 0 1 = ; j 1 ,

{ {

All the received buffer maps from the peers that belong to the same overlay will form a matrix

K j N i ij b 1 ; 1
) ( (where ij b indicates the availability of the piece j π at the peer i p ) that we will call further the Piece Map.

The Piece Map differs from the stream map. The former describes the availability of data pieces (NALUs) among the peers for the current streaming session while the latter describes the stream organization in terms of number of layers, index of each NALU, size of NALUs, etc.

The main goal of our architecture and, especially of our new requesting policy, is to achieve efficient requests in the network. By efficient requests, we mean: (1) requesting the important pieces (i.e. pieces with a lower layer index) from reliable peers, (2) reducing the overhead introduced by multiple-piece requests, and (3) load balancing the requests of different layers from different peers.

The SVC Streaming over P2P problem (SSP Problem):

Given a set of pieces to request from other peers with multipieces requests, the SSP problem is to "pack" these pieces into a minimum number of multi-piece requests while optimizing the following metrics: (1) the reliability of all the requests, (2) the overhead induced by the multi-piece requests, and (3) the load balancing of requests among the senders.

Theorem:

The SVC streaming over P2P problem (SSP Problem) is NP-Hard.

Proof: First we show the problem is NP. The best set of requests can be found by going through all the possible requests sets, considering only the feasible ones, and assessing the "goodness" of each set in order to choose the best among them in a polynomial time. Next of capacity C each, a BP formulation is to pack all the items in a way that minimizes the number of used bins. The SSP problem can be seen as a constrained variant of the classical BP problem. Indeed, the SSP formulation is to "pack" pieces i p of different sizes i s into a set of requests while aiming at the same time to optimize other objectives (i.e. R : Reliability, LB : Load Balancing and O : Overhead). The problem instance reduction is in fact done by considering an overloaded version of the objective function. In the classical formulation of the BP problem, the objective function used to evaluate an "assignment" A is the number of used bins U (i.e.

U A f = ) (
), while in the SSP problem, the objective function considers other parameters in addition to the number of "bins" (i.e. requests in the SSP problem), in other words ) , , , ( )

( O LB R U f A f
. Above, we showed that BP can be reduced to our problem. Therefore, the SSP problem is also NP-Hard.

B. Harmony Search Heuristic

Given the NP-Hardness of the SSP problem, we propose a heuristic based on Harmony Search (HS) [START_REF] Geem | A new heuristic optimization algorithm: harmony search[END_REF]. The idea behind the original HS heuristic is the process of searching a perfect state of musical harmony where each musician in a group plays a note to find the best harmony all together. The Harmony Search meta-heuristic exhibits the following properties:

HS can consider both continuous and discontinuous objective functions. HS can handle discrete as well as continuous variables. HS is free from divergence and may escape local optima. 1 Actually, the cardinality of the subset of B that will be used to pack the items in I, is bounded to the number of items in I, i.e., |B| <= |I|. In other words, for the worst case, each item is packed into a different bin Along these properties, the harmony search heuristic is known to be a quick optimization technique in terms of necessary iterations to converge to the optimum. Figure 3 shows the harmony search heuristic applied to the SSP problem. Harmony Search algorithm is known to be free from parameter setting problem. In fact, the default values [START_REF] Geem | A new heuristic optimization algorithm: harmony search[END_REF] are often of good choice.

Harmony_Search_for_SSP (SSP Data) SSP inputs:

PieceSet: a set of data pieces to request (i.e. NALs) π. Peers

B.1. Solution Coding

A solution to the SSP problem is a set of requests. Each request is a collection of information including the peer to which it is sent, and the different pieces to request. To apply the harmony search algorithm to the SSP problem, we need a vector representation of the solution. Thus, we introduce the following definitions: Given a set of K pieces to request, ] ,..., , [

2 1 K s s s S= is a
solution, where i s represents the peer from which the piece i π will be requested. Since all the peers do not have the same pieces, each i s takes a value in a different set rather than the global peers set P. We denote this set as Peers i π .

. It represents the peers that have the piece i π .

Based on a solution vector S , the algorithm will construct the requests with respect to the size constraint C (for example, KB C 16 is the optimal response size in BitTorrent Protocol as described in [START_REF] Marciniak | Small is not always Beautiful[END_REF][13]).

B.2. Solution Fitness

In order to measure the fitness of a SSP solution f(s), we compute the following criteria: a) Requests Diversity: First, the diversity of a single request is computed by eq. 1.

(Eq. 1)

Where * l is the dominant layer index in the request i Req (for example, * l related to the request Req[1,2,3,2,2,3,2] is * l =2). L is the highest layer index of the SVC stream and α is a constant set to avoid a zero dominator (any α≠1). This indicator computes the "distance" between a layer index of a piece i l and the dominant layer index * l within a particular request, in a way that a larger difference will result in a larger "distance". Moreover, this distance is not the same for two layer indexes i l and j l surrounding * l (i.e. ). We defined this indicator in a way to tolerate diversity with lower layer indexes rather than with higher layer indexes. A plot of this indicator is given in Figure 4.

Figure 5 shows this indicator regarding a scalable stream composed of 10 layers. The diversity indicator has the following properties:

a) The diversity between * l and itself is null.

b) The diversity is proportional to the lag between * l and a layer index i l .

c) The diversity is less important with lower layers than with higher layers.

While the first two properties are obvious, the third property is driven by the fact that a peer having pieces of layer l * is more likely to have lower layers (l < l * ) than higher layers (l > l * ).

Second, the overall diversity of a SSP solution D(s) is defined as follows:

(Eq. 2)

b) Requests Reliability

The reliability of a request depends inherently on the reliability of the peer to which it is sent and the priority of the layers being requested in this request. The reliability of a request is computed by equation 3:

(Eq. 3)
Where, * l is the priority of the dominant layer index in a request. In order to have a monotone increasing function, the priority of a layer l is l L l -= (i.e. lower layers are given higher priority values, and higher layer are given lower priority values). Clearly, the reliability of a request is proportional to the priority of the dominant layer in the request and the reliability of the peer to which this request is sent. A plot of ρ is given in Figure 6 for a scalable stream composed of 15 layers and peer reliability ranging from 0% to 100%. This figure shows that in the p function, more importance is given to the layer priority than to the reliability of the peer. This is because the lower layers in a SVC stream are essential for its successful decoding. The overall reliability of a SSP solution ) (s R is defined as follows:

(Eq. 4) Layer [3] Layer [4] Layer [START_REF] Zhang | DONet/CoolStreaming: a data-driven overlay network for live media streaming[END_REF] Layer [START_REF] Cui | Layered peer-to-peer streaming[END_REF] Layer [START_REF] Hefeeda | Rate-distortion optimized streaming of fine-grained scalable video sequences[END_REF] Layer [START_REF] Lan | A peer-to-peer architecture for efficient live scalable media streaming on Internet[END_REF] Layer [START_REF] Mokhtarian | Efficient allocation of seed servers in peer-to-peer streaming systems with scalable videos[END_REF]

i i Req s D s d Req ¦ * i i Req l r U u i i Req s R s Req U ¦ c) Requests Overhead
In our architecture, we have defined a BitTorrent-like protocol for data exchange between the peers. Each data piece, when sent to a peer, introduces an overhead (piece index, bloc index, offset) while the overhead of a request is defined by the request index and the data size. Thus, the overhead of a request depends on the number of pieces sent in the response, since all these pieces will share the same request header.

(Eq. 5)

To model overhead, we have also considered the ratio of response filling to the optimal response size C. Thus, a response to a request that minimizes the overhead will contain a great number of pieces while filling the response to its optimal size C. (Eq. 6)

So the overall overhead for a SSP solution is defined as follows:

(Eq. 7)

Having the entire indicators (i.e. the criteria to optimize), we build a simple objective function that is a linear combination of all the standardized indicators: request count, request diversity, request reliability and request overhead (N , D , R and W ):

(Eq. 8)

A simple objective function has the coefficient equal to 1 which we have utilized in our requesting policy. These coefficients can be managed to give more importance to certain parameters.

III. PERFORMANCE EVALUATION

In order to evaluate the performance of our new requesting policy, we carried out some simulation experiments, using a real data set. The data set is a snapshot of a P2P network streaming a real SVC file. Table 1 summarizes the different parameters. The entire piece set was organized into small NALU subsets (according to the reception buffer size). For each NALU subset we run our pull algorithm (HS), and two other existing approaches: (1) the Chunk per Peer (CPP) and the Layer per Peer (LPP) [START_REF] Liu | LayerP2P: Using Layered Video Chunks in P2P Live Streaming[END_REF].

Data Set Summary

In the CPP approach, the NAL units are packed into requests with no consideration of their layer; the CPP is equivalent to the Best-Fit method in the classical Bin Packing Problem [START_REF] Johnson | Fast algorithms for bin-packing[END_REF]. In the LPP approach on the other hand, the NALUs are packed into requests according to their layer and each request contains only NALUs of the same layer. Figure 7 shows an example of the generated requests for the three pull approaches. 0 1 2 0 1 2 1 3 0 1 3 0 1 2 3 0 2 0 2 3 NAL Subset CPP Requests LPP Requests HS Requests 0 2 0 2 3 3 0 1 2 3 2 1 3 0 1 0 1 2 0 1 0 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 3 3 3 3

0 1 0 2 0 1 0 1 0 0 2 1 1 2 2 3 3 2 3 3
Figure Generated requests for the three pull approaches.

For each NALU subset, the three algorithms: HS, CPP, LPP output a set of requests considered as a "solution". This solution is then evaluated by computing its overall fitness (i.e. score) which is based on the selected optimization indicators (Request Count, Request Diversity, Request Reliability, and the Request Overhead). The overall objective function (i.e. solution fitness) is a linear combination of the different standardized indicators (N , D , R and W ). These indicators were transformed to be always maximized (i.e. to minimize the number of request N, we maxmize N ).

Figure 8 shows a plot for the objective function for the three approaches. We can see clearly that our pull algorithm outperforms the other two algorithms since the HS approach optimizes conjointly all the criteria at the same time unlike the two other approaches.

Then, we have separately studied each criterion of the objective function; Figure 9 shows a plot of the number of generated request per NALU subsets for the three approaches. We can see in this figure that our approach generates a number of requests that is closest to the optimal number of requests achieved here by the CPP approach. Since the CPP approach is more likely a file download, the number of its requests is the smallest that we can have (see Figure 7). From this figure, we can also see that the LPP gives poor results. Indeed, when the peers are specialized to different layers, the number of requests will considerably grow since each request must have the same layer NALUs and requests for NALUs in different layers cannot be merged.

Figure 10, shows a plot of the request reliability indicator. In this figure we can see that LPP has the best performance since each request contains only NALs of a single layer. This results in a greater reliability when requests for lower layers are sent to more reliable peers (as performed in the LPP approach). However, the HS approach results are quite good since the average reliability indicator in the entire data set is 0.500 (i.e. 50%) and the standard deviation is 0.096 (i.e. 9.6%).

Figure 11 shows a plot for the request overhead indicator for the three approaches. In this figure, we can see that the overhead introduced by our approach is no significantly greater than the minimum overhead achieved here by the CPP approach. This overhead can be explained by the fact that, when trying to form requests in order to optimize all the criteria at the same time, NALUs can be assigned to a request without filling it to its optimal size (i.e. C=16KB), increasing

IV. CONCLUSION

In this paper, we proposed a new pull approach (HS) for efficient layered video content (e.g. SVC bitstream) distribution in a mesh-based peer-to-peer architecture. The proposed scheme optimizes different distribution criteria such as request diversity, request reliability, the number of requests and the request overhead. The performance evaluation of HS shows comparative results against two existing approaches.

Figure 1 :

 1 Figure 1: Distribution of a layered video content in a BitTorrent-like peer-to-peer architecture.

Figure 2 :

 2 Figure 2: 3D representation of an SVC bitstream.

Figure 3 :

 3 Figure 3: Harmony Search algorithm for the SSP problem.

Figure 4 :

 4 Figure 4: The diversity "distance" for a certain layer l* and the other layers in the scalable stream.

Figure 5 :

 5 Figure 5: The diversity "distance" for all the layers in the 10-layers stream.

Figure 6 :

 6 Figure 6: The reliability indicator for a 15-layers stream

Figure 8 :

 8 Figure 8: Objective Function Value per NAUL subset for the three pull approaches.

Figure 9 :

 9 Figure 9: Request count per NAL subset for the three approaches.

Figure 10 :

 10 Figure 10: Request Reliability Indicator per NAL subset for the three pull approaches.

Figure 11 :

 11 Figure 11: Request Overhead Indicator per NAL subset for the three pull approaches.

  2011 IEEE 16th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD)

978-1-61284-282-0/11/$26.00 ©2011 IEEE profiles (terminal/network capabilities, user preferences …).

  we show the problem is NP-Hard. The Bin Packing Problem (BP) can be reduced to the

	SSP problem. Given a set of items	I={i 1	,i	2	,...,i N	}	of different
	packing cost i c (volume, size, weight…) and an infinite set 1
	of bins	,b B={b 2 1	,...}

Peers endwith endwith with probability 1-hmcr do Assign

	Piece-Map: a matrix for the availability of the different
	pieces at the different peers.
	HS inputs (default values):
	HMS: Harmony Memory Size (default : 20)
	hmcr: Harmony Memory Choosing Rate (default: 0.80)
	par: Pitch Adjustment Rate (default : 0.20)

/ π in PieceSet: a set of peers having piece π Termination Criterion: (default: 10 iterations) 1. Generate the set HarmonyMemory of size S: foreach solution s in HarmonyMemory do foreach piece π in s.Pieces do Assign piece π to randomly chosen peer p in the set π.Peers. 2. Harmony Search Algorithm: repeat : Generate a new solution s * : foreach piece π in PieceSet do with probability hmcr do Assign piece π to the same peer p in a randomly chosen solution s from HarmonyMemory. with probability par do Assign piece π to a peer p * "similar" to peer p within the set π.piece π to randomly chosen peer p in the set π.Peers. endwith endforeach Compare the new solution s * to the worst solution s ∞ in HarmonyMemory: if (solution s * "is better than" solution s ∞ ) then Replace solution s * by solution s ∞ in the set HarmonyMemory. endif until (termination criterion is satisfied).

Table 1 :

 1 Data Set Information

	Number of Layers	14 Layers
	Number of NALs	7030 NALs
	Reception Buffer Size	~60 KB
	Total Video Length	~60sec

ACKNOWLEDGEMENT

The research leading to these results has received funding from the European Union's Seventh Framework Programme (FP7/2007-2013) in the ENVISION project, grant agreement 248565.


Lucie Daubigney

Matthieu Geist

Olivier Pietquin

Apprentissage off-policy appliqué à un système de dialogue basé sur les PDMPO

Keywords: Apprentissage par renforcement, Système de dialogue vocal Reinforcement Learning, Spoken Dialogue System

L'apprentissage par renforcement (AR) fait maintenant partie de l'état de l'art dans le domaine de l'optimisation de systèmes de dialogues vocaux. La plupart des méthodes appliquées aux systèmes de dialogue basées sur l'AR, comme par exemple celles qui utilisent des processus gaussiens, requièrent de tester des changements plus ou moins aléatoires dans la politique. Cette manière de procéder est appelée apprentissage ≪ on-policy ≫. Néanmoins, celle-ci peut induire des comportements de la part du système incohérents aux yeux de l'utilisateur. Les algorithmes devraient idéalement trouver la politique optimale d'après l'observation d'interactions générées par une politique sous-optimale mais proposant un comportement cohérent à l'utilisateur : c'est l'apprentissage ≪ offpolicy ≫. Dans cette contribution, un algorithme efficace sur les échantillons permettant l'apprentissage off-policy et en ligne de la politique optimale est proposé. Cet algorithme, combiné à une représentation compacte, nonlinéaire de la fonction de valeur (un réseau de neurones), permet de gérer des systèmes à grande échelle.

Introduction

Les systèmes de dialogues vocaux (SDV) sont maintement fréquemment utilisés dans la vie quotidienne pour remplir des tâches variées : prise de rendez-vous, aide au diagnostic de pannes, information, tutorat, etc. La conception de ces systèmes est souvent laissée à des experts du traitement du langage naturel afin que le SDV soit efficace et interagisse de fac ¸on naturelle avec l'utilisateur. Ces deux qualités sont primordiales car le SDV interagit avec un humain et ce dernier peut très rapidement être lassé de communiquer avec une machine peu fiable. Le gestionnaire de dialogue (GD) du SDV, module responsable de la prise de décisions à propos de ce qui est dit et à quel moment, doit donc avoir un comportement prenant en compte les réactions de l'utilisateur. Cette tâche est compliquée par le fait que les modules de reconnaissance vocale et d'analyse sémantique, qui respectivement retranscrivent et reconnaissent le sens de ce qu'a dit l'utilisateur, commettent des erreurs. Cela rend la requête de l'utilisateur partiellement observable du point de vue du GD. Une solution parmi les plus courantes pour éviter les erreurs de reconnaissance est de demander à l'utilisateur de confirmer ce qu'il a dit. Mais cette solution ralentit les échanges et les rend moins naturels. Il est donc important que le GD utilise une stratégie d'interaction efficace et naturelle, qui puisse faire aboutir la requête de l'utilisateur. Définir à la main cette stratégie devient rapidement impossible quand la tâche est réaliste. En effet, cela nécessite d'identifier toutes les situations qui peuvent être rencontrées au cours du dialogue. Des solutions ont donc été proposées pour automatiquement chercher la stratégie optimale. Parmi celles-ci, nous nous concentrons sur celles basées sur l'apprentissage par renforcement (AR) [START_REF] Sutton | Reinforcement learning : An introduction[END_REF]. L'AR est une technique d'appren-tissage automatique qui a déjà été appliquée avec succès à l'optimisation de SDV [START_REF] Singh | Reinforcement learning for spoken dialogue systems[END_REF][START_REF] Levin | A stochastic model of human-machine interaction for learning dialog strategies[END_REF][START_REF] Pietquin | A probabilistic framework for dialog simulation and optimal strategy learning[END_REF][START_REF] Young | The hidden information state model : A practical framework for POMDP-based spoken dialogue management[END_REF]. L'idée fondamentale de ces algorithmes est d'apprendre une stratégie optimale à partir d'interactions entre un SDV et des utilisateurs de fac ¸on à optimiser une valeur numérique (appelée récompense) liée à la satisfaction de l'utilisateur. Cette récompense est généralement une combinaison linéaire de différentes mesures connues comme étant liées à la satisfaction de l'utilisateur (par exemple l'aboutissement de la requête, la longueur du dialogue, etc) [START_REF] Walker | PARADISE : A framework for evaluating spoken dialogue agents[END_REF]. La qualité d'une stratégie est mesurée comme étant la récompense cumulée espérée obtenue par le système alors qu'il suivait cette stratégie. Ceci mène à la définition d'une fonction, appelée fonction de valeur qui associe une récompense cumulée espérée à chaque contexte de dialogue. La stratégie optimale est celle qui associe la plus haute récompense cumulée espérée à chaque situation du dialogue.

Les méthodes standard d'AR utilisées jusqu'alors présentent l'inconvénient de nécessiter beaucoup de données : la quantité est telle qu'il n'est pas possible d'en réunir assez pour apprendre la politique optimale. Durant la dernière décennie, les dialogues ont donc été simulés pour générer artificiellement suffisamment de données [START_REF] Eckert | User modeling for spoken dialogue system evaluation[END_REF][START_REF] Pietquin | A probabilistic framework for dialog simulation and optimal strategy learning[END_REF][START_REF] Schatzmann | A survey of statistical user simulation techniques for rl of dialogue management strategies[END_REF][START_REF] Pietquin | Consistent Goal-Directed User Model for Realistic Man-Machine Task-Oriented Spoken Dialogue Simulation[END_REF]. Mais cette méthode introduit un biais de modélisation qui peut mener à une inadéquation entre la stratégie apprise et le comportement d'utilisateurs réels [START_REF] Schatzmann | Effects of the user model on simulationbased learning of dialogue strategies[END_REF]. C'est pourquoi un autre type de solutions, basé sur des algorithmes d'AR utilisant une approximation de la fonction de valeur a été récemment introduit. Des méthodes hors-ligne, utilisant un petit jeu de données fixes, ont d'abord été proposées. Elles sont assez performantes [START_REF] Henderson | Hybrid reinforcement/supervised learning of dialogue policies from fixed data sets[END_REF][START_REF] Li | Reinforcement Learning for Dialog Management using Least-Squares Policy Iteration and Fast Feature Selection[END_REF][START_REF] Pietquin | Sample-Efficient Batch Reinforcement Learning for Dialogue Management Optimization[END_REF]. Cependant, comme les stratégies apprises ne peuvent s'adapter en ligne ni à des changements de comportement de l'utilisateur, ni aux performances du système, des problèmes peuvent survenir si les données fournies ne sont pas représentatives de l'ensemble des situations possibles. Ces méthodes peuvent néanmoins donner une stratégie de départ correcte, à améliorer en ligne par la suite.

Des algorithmes mettant en place un apprentissage en ligne et on-policy de la stratégie ont récemment été proposés [START_REF] Gašić | Gaussian processes for fast policy optimisation of POMDP-based dialogue managers[END_REF][START_REF] Jurčíček | Natural Belief-Critic : a reinforcement algorithm for parameter estimation in statistical spoken dialogue systems[END_REF]. Ces algorithmes effectuent un changement et un test permanents de la politique à apprendre (un problème connu sous le nom de ≪ dilemme exploration/exploitation ≫, comme traité dans [START_REF] Daubigney | Uncertainty management for on-line optimisation of a POMDP-based largescale spoken dialogue system[END_REF]). Ces changements, puisqu'ils sont effectués durant l'apprentissage, pourraient mener à des comportements du GD qui gêneraient l'utilisateur (choix d'une action aléatoire). De plus, ces méthodes sont basées sur des approximations linéaires de la fonction de valeur rendant ainsi leur utilisation dans des systèmes à large échelle difficile. Pour passer à l'échelle, le contexte du dialogue doit être représenté de manière compacte [START_REF] Williams | Scaling up POMDPs for dialogue management : the summary POMDP method[END_REF] avec le risque que cela mène à des erreurs d'approximation.

Dans ce papier, nous proposons l'utilisation de l'algorithme KTD (Kalman Temporal Differences en anglais) [START_REF] Geist | Kalman Temporal Differences[END_REF] pour réaliser un apprentissage en ligne, effi-cace sur les échantillons et off-policy [START_REF] Pietquin | Sample Efficient On-line Learning of Optimal Dialogue Policies with Kalman Temporal Differences[END_REF] sur un système à grande échelle. KTD consiste à adopter une représentation paramétrique de la fonction de valeur. Les paramètres associés sont modélisés comme un processus aléatoire caché, lié aux récompenses via l'équation de Bellman. Ces paramètres sont alors appris en utilisant un filtre de Kalman non-parfumé (voir [START_REF] Geist | Kalman Temporal Differences[END_REF] pour les détails). L'utilisation de cet algorithme sera combinée à celle d'une représentation compacte de la fonction de valeur de fac ¸on à minimiser l'impact des approximations. La solution proposée dans [START_REF] Gašić | Gaussian processes for fast policy optimisation of POMDP-based dialogue managers[END_REF] servira de référence pour les résultats présentés ici. Dans [START_REF] Gašić | Gaussian processes for fast policy optimisation of POMDP-based dialogue managers[END_REF], la fonction de valeur est estimée grâce à l'algorithme GPTD (Gaussian Processes Temporal Differences en anglais) [START_REF] Engel | Reinforcement Learning with Gaussian Processes[END_REF] entraînant un apprentissage en ligne et une dépendance linéaire de la fonction de valeur aux paramètres. Dans cet algorithme, la fonction de valeur est modélisée comme étant un processus gaussien. Elle est liée à la récompense via un modèle génératif transcrivant l'équation de Bellman. Etant donné un a priori, la distribution a posteriori est alors déterminée par inférence Bayésienne. Dans le cadre de KTD, deux manières de représenter la fonction de valeur vont être étudiées : une linéaire, basée sur des Fonctions à Bases Radiales (RBF) et une nonlinéaire, basée sur des réseaux de neurones. La question de la représentation est importante car un compromis doit être trouvé entre la compacité de la représentation et l'information qu'elle peut représenter. Si la paramétrisation n'est pas assez compacte, elle ne sera pas utilisable. L'adaptation au cadre de l'AR du problème d'optimisation de la stratégie pour le dialogue est présentée dans la Section 2. Ensuite (Section 3), la question de la représentation de la fonction de valeur sera posée. La Section 4 présentera les expériences et pour finir, dans la Section 5 quelques résultats seront donnés.

2 La gestion de dialogue vue comme un Processus Décisionnel de Markov continu

La gestion du dialogue (GD) est un problème de décisions séquentielles. A partir de données provenant de l'utilisateur, les observations, le gestionnaire de dialogue doit choisir et effectuer une action. Cette action doit être choisie dans le but d'interagir avec l'utilisateur de manière efficace et naturelle. La satisfaction est quantifiée par une récompense fournie à la fin d'un dialogue. Vue sous cet angle, la gestion du dialogue peut être envisagée comme un Processus Décisionnel de Markov Partiellement Observable (PDMPO) : des décisions doivent être prises en accord avec l'historique des observations et des actions du système. Une manière de représenter succinctement l'historique en un état unique, appelée hidden information paradigm, a été proposée par [START_REF] Young | The hidden information state model : A practical framework for POMDP-based spoken dialogue management[END_REF]. Ainsi la GD s'envisage ici comme un MDP continu. Les algorithmes visent à apprendre une stratégie, appelée politique π qui associe une action a ∈ A à chaque état s ∈ S. La qualité de la politique est quantifiée par la fonction Q qui donne la récompense cumulée espérée en partant d'une paire état-action donnée, (s, a), et suivant la politique π :

Q π (s, a) = E[ i≥0 γ i r i |s 0 = s, a 0 = a, π].
Le facteur γ est le facteur d'actualisation, (s, a) la paire état-action et (r i ) i≥0 le jeu de récompenses obtenues lors de l'interaction. La fonction Q optimale, notée Q * , est telle que pour toute politique π et pour toute paire (s, a), De fac ¸on générale, la fonction Q optimale se calcule de deux manières. L'apprentissage on-policy améliore incrémentalement la politique courante par des phases répétées d'évaluation de la valeur de cette politique suivi de l'amélioration de cette dernière, amélioration qui se fait en prenant la politique gloutonne par rapport à la fonction de valeur nouvellement mise à jour. La phase d'évaluation peut se faire grâce à l'équation d'évaluation de Bellman :

Q * ≥ Q π .
Q π (s, a) = E s ′ |s,a [R(s, a, s ′ ) + γQ π (s ′ , π(s ′ ))].
L'état s ′ est l'état dans lequel se trouve le système après avoir effectué l'action a en partant de s. La politique optimale est trouvée de cette fac ¸on avec l'algorithme GPTD utilisé dans [START_REF] Gašić | Gaussian processes for fast policy optimisation of POMDP-based dialogue managers[END_REF]. Dans ce cas, l'équation de Bellman est linéaire, ce qui est requis pour l'utilisation des processus gaussiens. Ces derniers contraignent aussi la paramétrisation de la fonction Q à être linéaire. L'autre fac ¸on de calculer la politique optimale est l'apprentissage off-policy. Cette méthode consiste à directement calculer la fonction Q optimale, Q * (s, a), en utilisant l'équation d'optimalité de Bellman (non-linéaire) :

Q * (s, a) = E s ′ |s,a [R(s, a, s ′ ) + γ max b∈A Q * (s ′ , b)].
Le cadre défini par KTD [START_REF] Geist | Kalman Temporal Differences[END_REF] permettant de gérer les nonlinéarités, cette équation peut directement être résolue et un apprentissage off-policy est ainsi rendu possible [START_REF] Pietquin | Sample Efficient On-line Learning of Optimal Dialogue Policies with Kalman Temporal Differences[END_REF]. Dans ce papier, nous profitons de cet avantage pour utiliser une paramétrisation non-linéaire, Q * θ (s, a), afin d'obtenir une représentation compacte de la fonction Q et d'envisager une représentation de l'espace d'état plus riche.

3 Approximation de la fonction Q Ainsi qu'il a été précisé dans la partie précédente, dans certains cas, comme lorsque l'espace d'état S est continu, la fonction Q (optimale ou non) doit être approchée par Qθ (s, a) puisque Q : S × A → R. La représentation pour la fonction Q peut être linéaire ou non. Dans le cas linéaire, la fonction Q est représentée par Qθ (s, a) = θ T Φ(s, a), où Φ(s, a) est une matrice formée de N fonctions de bases définies à l'avance, φ i (i ∈ [1..n]), telle que Φ = [φ 1 (s, a)...φ N (s, a)] T et θ est un vecteur contenant les poids associés. Ici, des Fonctions à Bases Radiales (RBF) ont été utilisées. Si une représentation non-linéaire est choisie, la fonction Q peut être représentée par Qθ (s, a) = f θ (s, a), avec f θ n'ayant pas de dépendance linéaire aux paramètres θ. Dans ce papier, nous avons utilisé un réseau de neurones dont une des propriétés est de pouvoir approximer une fonction quelconque s'il contient un nombre suffisant de neurones sur chaque couche cachée. Dans ce cas, le vecteur θ contient les poids synaptiques du réseau. Nous définissons H comme étant l'espace d'hypothèses généré par Φ(s, a) ou par f θ (s, a). L'espace H doit être assez riche pour contenir la vraie fonction Q mais le nombre de paramètres ne doit pas être trop grand à cause des risques de sur-apprentissage et des coûts de calcul. En effet, s'il y a trop de paramètres à trouver pour un nombre restreint de données d'entraînement, l'approximation de la fonction suivra les exemples et n'aura pas un grand pouvoir de généralisation. Un compromis est à faire entre l'information à représenter et la taille de la paramétrisation.

Expériences

Tâche

Les résultats présentés dans la section suivante ont été obtenus avec le système CamInfo [START_REF] Young | The hidden information state model : A practical framework for POMDP-based spoken dialogue management[END_REF], un SDV à grande échelle, développé afin de fournir des informations touristiques sur la ville de Cambridge. La requête de l'utilisateur peut contenir jusqu'à 12 attributs différents. Tous les résultats ont été obtenus avec des utilisateurs simulés [START_REF] Schatzmann | Agenda-based user simulation for bootstrapping a pomdp dialogue system[END_REF] à cause de la difficulté à obtenir des données réelles et à cause de la grande variabilité inter-utilisateurs qui ne rend pas les expériences facilement comparables. Les erreurs de compréhension sont aussi simulées.

Paramètres du MDP

Durant la phase d'apprentissage, une récompense de +20 est donnée au système à la fin du dialogue s'il a réussi à répondre à la requête de l'utilisateur. Une pénalité de -1 est donnée à chaque fois que le système effectue une action. L'espace d'état utilisé est celui décrit dans [START_REF] Young | The hidden information state model : A practical framework for POMDP-based spoken dialogue management[END_REF]. Il est constitué d'un vecteur contenant deux variables continues (représentant les deux meilleurs scores de confiance associés aux deux meilleures hypothèses de ce qui a été reconnu par le système ; ces scores sont fournis par les modules de reconnaissance vocale et de l'analyse sémantique). Le GD propose une action choisie parmi un jeu de 12 meta-actions qui sont retranscrites en 22 actions effectivement proposées à l'utilisateur (voir [START_REF] Young | The hidden information state model : A practical framework for POMDP-based spoken dialogue management[END_REF]). Cet espace d'état est ensuite amélioré afin de construire des stratégies plus robustes (voir Section 5.2).

Algorithmes

L'algorithme GPTD qui utilise une paramétrisation basée sur un dictionnaire construit durant l'apprentissage [START_REF] Engel | Reinforcement Learning with Gaussian Processes[END_REF] est comparé à KTD qui utilise d'abord une paramétrisation linéaire puis une paramétrisation non-linéaire. Les resultats ont été obtenus en laissant le GD construire une estimation de la fonction Q, Qlearnt (s, a), ∀(s, a) ∈ S × A. Dans le cas où GPTD est utilisé, l'estimation de la fonction concerne la fonction de valeur de la politique suivie tandis que dans le cas où KTD est utilisé, l'estimation faite correspond à la fonction de valeur associée à la politique optimale. Ensuite, la fonction Q estimée est utilisée pour améliorer la stratégie. Cette stratégie, appelée π learnt , est calculée de fac ¸on gloutonne par rapport à l'estimation : π learnt = arg max a Qlearnt (s, a). Avec un nombre suffisant de données, les deux algorithmes sont supposés apprendre la même stratégie optimale : π learnt devrait être égale à π * . Sur les graphes présentés, les récompenses cumulées moyennes obtenues en utilisant π learnt sont tracées pour différentes tailles de jeux de dialogues d'entraînement.

Stratégie comportementale

L'apprentissage suppose d'utiliser une stratégie comportementale pour explorer l'espace d'état. Les algorithmes KTD et GPTD fournissent une estimation de la fonction Q et des informations d'incertitude quant à la qualité de cette estimation (σ Q ) [START_REF] Geist | Managing Uncertainty within the KTD Framework[END_REF][START_REF] Gašić | Gaussian processes for fast policy optimisation of POMDP-based dialogue managers[END_REF]. Une approche dans laquelle l'agent apprenant fait un compromis sûr entre l'exploitation de l'information déjà sue et l'exploration de l'espace d'état, a été étudiée dans [START_REF] Daubigney | Uncertainty management for on-line optimisation of a POMDP-based largescale spoken dialogue system[END_REF] pour le même SDV. Cette approche est appelée bonus-gloutonne (inspirée de [START_REF] Kolter | Near-Bayesian Exploration in Polynomial Time[END_REF]). Le choix de l'action suivante est fait ainsi :

a i+1 = arg max a Qi (s i+1 , a) + β σQi (s i+1 , a) β 0 + σQi (s i+1 , a)
.

L'approche bonus-gloutonne donne les meilleurs résultats comparée à l'approche ǫ-gloutonne classique :

a i+1 = arg max a Qi (s i+1 , a) w.p. 1 -ǫ aléatoire (uniform.) w.p. ǫ.
Elle sera donc utilisée lors des expériences (Section 5).

Résultats

Dans cette partie, des résultats comparant l'efficacité des algorithmes KTD et GPTD dans différentes conditions de bruit sont donnés.

Paramétrisation linéaire

Tout d'abord, KTD utilisant une paramétrisation linéaire pour l'approximation de la fonction Q est comparé à GPTD dans une environnement presque sans bruit (taux d'erreurs de reconnaissance fixé à 10% : une fois sur dix, ce qui est dit par l'utilisateur est mal reconnu par la machine). Le nombre de paramètres est d'environ 300 pour l'approche avec GPTD et 144 pour celle avec KTD. Pour cette dernière, le vecteur de paramètres, défini pour tout s ∈ S et pour tout a ∈ A est : Φ(s, a) = [δ a,a1 φ(s, a 1 ), ..., δ a,a12 φ(s, a 12 )] T , avec

δ a,a ′ = 1 si a = a ′ sinon δ a,a ′ = 0 et φ(s, a) T = [1, ϕ 1 1 , ϕ 1 2 , ϕ 1 3 , ϕ 2 1 , ϕ 2 2 , ϕ 2 3 , E 1 , E 2 ](s, a).
Les fonctions ϕ sont des gaussiennes. Trois gaussiennes par dimension sont utilisées sur les dimensions continues de l'espace d'état et deux entiers (E 1 ,E 2 ) sur les dimensions discrètes. Le GD choisit ses actions parmi 12 actions (a 1 , a 2 , ..., a 12 ). Les résultats présentés Fig. 1(a) montrent que la politique apprise avec l'algorithme KTD est meilleure que celle apprise avec GPTD : en moyenne, il faut 2 tours de moins au GD pour satisfaire la requête de l'utilisateur. Dans les deux cas, la solution trouvée est imparfaite du fait de la perte d'information sur l'état lors de sa compression, détaillée dans l'article [START_REF] Young | The hidden information state model : A practical framework for POMDP-based spoken dialogue management[END_REF]. En quelques mots, les modules de reconnaissance vocale et d'analyse sémantique fournissent une liste d'hypothèses sur ce qui a été reconnu. A chaque hypothèse est associé un score de confiance. De cette liste d'hypothèses est extrait un certain nombre d'informations (deux meilleures hypothèses, action de l'utilisateur associée à la meilleure et but de l'utilisateur pressenti). Comme toutes les hypothèses ne peuvent être prises en compte, de l'information est perdue. Sur la Fig. 1(b), les fréquences moyennes des actions possibles proposées par le gestionnaire de dialogue sont présentées. Elles ont été obtenues par le test de la politique apprise avec 1000 dialogues d'entraînement. En étudiant quelles sont les actions proposées, les différences apparaissant Fig. 1(a) peuvent être expliquées. Les deux algorithmes ne proposent pas la même action principale : l'approche utilisant GPTD demande à l'utilisateur de faire un choix entre deux propositions (action ≪ Se-lect2 ≫) tandis que celle utilisant KTD fournit directement à l'utilisateur une information (action ≪ Inform ≫). La politique apprise avec GPTD demande à l'utilisateur de répéter assez souvent ce qu'il a dit (action ≪ RedRepeat ≫) tandis que l'autre politique apprise (avec KTD) préfère demander une confirmation explicite (action ≪ ExplConfReq ≫). Il est plus facile de reconnaître une réponse à une question fermée (oui/non) qu'une phrase complète. La politique apprise avec KTD fait aussi usage d'une action qui en combine deux autres en fournissant une information tout en faisant une confirmation implicite (action ≪ ImplConfReq ≫) ce qui peut aussi contribuer à raccourcir le dialogue. L'approche qui utilise GPTD propose quelques fois une solution partiellement correcte (action ≪ Deny ≫) à laquelle est liée l'utilisation de l'action ≪ Select2 ≫. Ainsi, l'étude des différentes actions proposées par les politiques permet de les comparer entre elles.

Paramétrisation non-linéaire

Une paramétrisation non-linéaire, basée sur un réseau de neurones, est maintenant introduite. Un réseau ayant une couche cachée qui comporte 8 neurones est utilisé (N H1 = 8). Le nombre de neurones sur la couche d'entrée est déterminé par le fait que chaque paire (s, a) ∈ (S × A) doit être associée à une combinaison binaire étant donné qu'il n'y a pas de métrique définie sur l'espace d'action. Le nombre de neurones sur la couche d'entrée, N I est : pour l'espace d'état, 2 neurones pour les composantes continues (qui correspondent aux deux meilleurs scores de confiance) et 22 pour l'action de l'utilisateur reconnue ; pour l'espace d'action, 12 neurones sont nécessaires. Donc N I = 2 + 6 + 22 + 12 = 42. La couche de sortie du réseau contient un seul neurone dont la valeur correspond à l'estimation de la fonction Q. Le nombre de paramètres est ainsi de :

N I • N H1 + (N H1 + 1) • 1 = 42 • 8 + 9 = 345.
Une paramétrisation basée sur un réseau de neurones est intéressante car même si l'espace d'état est enrichi, le nombre de paramètres requis pour correctement représenter la fonction à estimer ne devient pas démesuré. Par exemple, si une valeur discrète pouvant prendre N valeurs différentes est ajoutée à l'espace d'état, le nombre de paramètres utilisés dans le cas linéaire est multiplié par N tandis qu'avec l'approche utilisant un réseau de neurones, seulement N H1 • N paramètres sont ajoutés à la paramétrisation précédente (si le nombre de neurones sur la couche cachée est identique). Dans le cas d'une variable continue, seulement un neurone est ajouté à la couche d'entrée. Cette propriété peut être utilisée pour accroître l'espace d'état et enrichir la représentation d'un état. Ceci évite la perte d'information due à la compression de l'état (processus décrit Sec. 5.1). Dans cette partie, l'espace d'état est enrichi par l'ajout d'une dimension continue qui correspond au troisème plus important score de confiance et par l'ajout d'une dimension discrète qui est l'action de l'utilisateur associée au deuxième meilleur score de confiance. Le nouvel espace d'état a donc six composantes, trois continues et trois discrètes. Le nombre de neurones sur la couche d'entrée est N I = 42 + 22 + 1 = 65 donc le nombre de paramètres est 65 • 8 + 9 = 529. A titre de comparaison, si une approche de type RBF était utilisée, le nomre de paramètres serait de (1+3 3 )•6•22•22•12 = 975 744, avec seulement 3 gaussiennes par dimension, ce qui n'est pas envisageable. La performance de l'approche utilisant KTD dans un environnement peu bruité (taux d'erreurs de reconnaissance fixé à 10%) utilisant la paramétrisation non-linéaire décrite précédemment en utilisant l'espace d'état initial puis l'espace d'état enrichi est comparée à celle de GPTD sur la Fig. 2(a). Les résultats obtenus avec KTD sont meilleurs que ceux obtenus avec GPTD si un nombre suffisant de données d'entraînement est fourni. En effet, les mauvaises performances de KTD avec un nombre de données d'entraînement faible sont dues au réseau de neurones qui soit fournit une mauvaise estimation de la fonction soit en fournit une correcte, sans intermédiaire. La largeur de la zone de transition entre les deux phases, c'est-à-dire ici entre 250 et 600 données, dépend des politiques apprises : pour certaines, la transition se fera tôt, vers 250 échantillons alors que pour d'autres, celle-ci se fera vers 600. La différence entre les deux courbes lorsque de l'information est ajoutée à l'espace d'état n'est pas significative. En effet, ajouter de l'information lorsque l'environnement est peu bruité n'est pas très intéressant puisque le module de reconnaissance vocale et l'analyseur sémantique sont sûrs de l'information qu'ils fournissent. La liste d'hypothèses qui est faite n'est pas très longue et toute l'information qu'elle contient est dans les toutes premières hy-pothèses. En prendre en compte de nouvelles n'influe pas sur la décision. Sur la Fig. 2 Enrichir l'espace d'état devrait être plus intéressant dans des environnements bruités car la liste d'hypothèses est plus longue et les scores de confiance associés distribués plus uniformément sur les hypothèses. L'approche utilisant KTD a donc été comparée à celle utilisant GPTD dans une situation très bruitée (taux d'erreurs de reconnaissance fixé à 50% : une fois sur deux, ce qui est dit par l'utilisateur est mal reconnu par la machine). Le nombre moyen de paramètres dans l'approche utilisant GPTD est d'environ 700. Il est supérieur par rapport au cas où il y a peu de bruit car il est directement lié à la dispersion des états rencontrés dans l'espace d'état et lorsqu'il y a beaucoup de bruit, l'espace d'état est plus vastement utilisé. Les resultats sont présentés Fig. 3. Alors qu'il n'y avait pas de différence notable entre les cas où l'espace d'état initial et celui enrichi étaient utilisés dans une situation peu bruitée, une différence apparaît dans ce cas-là. Sur la Fig. 3(a), l'approche utilisant KTD et un réseau de neurones est toujours plus performante que celle utilisant GPTD. Mais maintenant que de l'information est ajoutée dans l'espace d'état en situation très bruitée, la politique apprise sur un espace d'état plus riche est meilleure : la longueur du dialogue est raccourcie de 2 tours en moyenne. Sur la Fig. 3(b), les fréquences des actions proposées durant le test de la politque apprise avec 1000 dialogues d'entraînement sont présentés. La tendance entre les politiques apprises par GPTD et KTD sont les mêmes que celles obtenues dans un environnement peu bruité. Néanmoins, les histogrammes montrent qu'une demande explicite d'information (action ≪ ExplConfReq ≫) est plus fréquente quand moins d'information est présente dans l'espace d'état.

Discussion

Dans cette partie, après avoir testé une paramétrisation linéaire pour représenter la fonction Q estimée par l'approche utilisant KTD, une paramétrisation non-linéaire a été employée. Avec une approche utilisant un réseau de neurones, un bon compromis entre la taille de la paramétrisation et la capacité d'approximation de la fonction Q a été trouvé. Plus d'information peut être représentée avec un nombre raisonnable de paramètres. Ainsi, comme plus d'information est prise en compte pour l'estimation, moins de biais de modélisation est introduit. Dans les deux cas, linéaires et non-linéaires, lorsque KTD est utilisé, la paramétrisation, dès lors que l'espace d'état est constuit, utilise toute l'information rencontrée sans faire d'approximation, contrairement à l'approche qui utilise GPTD, ce qui peut expliquer les meilleurs résultats obtenus de KTD par rapport à GPTD.

Conclusion

Dans ce papier, nous avons proposé l'utilisation de l'algorithme KTD [START_REF] Geist | Kalman Temporal Differences[END_REF] pour apprendre de fac ¸on off-policy, efficacement, une stratégie de dialogue pour un système à grande échelle. A cause de sa capacité à gérer des paramétrisations non-linéaires, l'approche KTD peut être associée à une approximateur de fonction compact, sous la forme d'un réseau de neurones. Grâce à la représentation compacte de l'espace d'état, ce dernier peut-être enrichi avec des informations sur la distribution des scores de confiance sur la liste d'hypothèses. Cette nouvelle représentation fournit une meilleure stratégie et plus robuste que celles déjà exisantes, comme celle fournie par GPTD. Dans le futur, une représentation d'états encore plus riche sera testée. Un nombre plus important de paramètres n'est

FIGURE 1 -

 1 FIGURE 1 -Comparaison de GPTD et KTD utilisant une paramétrisation linéaire.

  (b) sont comparées les fréquences des actions proposées par le GD lors du test de la politique après apprentissage avec 1000 dialogues d'entraînement. Les histogrammes sont similaires à ceux obtenus Fig. 1(b).

FIGURE 2 -

 2 FIGURE 2 -Comparaison de GPTD et KTD (avec une paramétrisation non-linéaire)(taux d'erreur de reconnaisance à 10%).

  La politique optimale est gloutonne par rapport à la fonction Q optimale : π * (s) = arg max a Q * (s, a). Il est à noter que la fonction Q permet de comparer non seulement des politiques entre elles mais aussi des actions en partant d'un même état et d'une politique fixée. Trou-

ver la politique optimale se résume donc à trouver la fonction Q optimale. Dans la plupart des cas, l'espace formé par l'ensemble des états et des actions est trop grand pour autoriser un calcul exact de la fonction Q ce qui impose le calcul d'une approximation de cette fonction, Q. La représentation choisie pour cette approximation est souvent paramétrique : Qθ , θ étant le jeu de paramètres à apprendre.

Remerciements

Les auteurs tiennent à remercier le groupe dialogue de l'Université de Cambridge, tout particulièrement Steve Young et Milic ¸a Gašić, pour la mise à disposition et leur aide à l'utilisation du système CamInfo. Ce travail est financé par INTERREG IVa dans le cadre du projet ALLE-GRO et par la région Lorraine (France).

en effet pas un frein pour les approches qui utilisent un réseau de neurone comme approximateur.