Damien Saucez

Chadi Barakat

Thierry Turletti

Leveraging Information Centric Networking in Over-The-Top Services

The ubiquity of broadband Internet and the proliferation of connected devices like laptops, tablets or TV result in a high demand of multimedia content such as high definition video on demand (VOD) for which the Internet has been poorly designed with the Internet Protocol (IP). Information-Centric Networking and more precisely Content Centric Networking (CCN) overtake the limitation of IP by considering content as the essential element of the network instead of the topology.

CCN and its content caching capabilities is particularly adapted to Over-The-Top (OTT) services like YouTube or Netflix that distribute highdefinition multimedia content to millions of consumers, independently of their location. However, bringing content as the most important component of the network implies fundamental changes in the Internet and the transition to a fully CCN Internet might take a long time. Despite this transition period where CCN and IP will co-exist, we show that OTT service providers and consumers have strong incentives for migrating to CCN. We also propose a transition mechanism that leverages caching and enable loosely collaboration.

Introduction

The Internet usage has dramatically changed since its creation and a large part of the traffic is now generated by the consumption of multimedia content [START_REF] Labovitz | ATLAS Internet Observatory[END_REF] like video on demand (VOD) or high quality calls. However, the TCP/IP model used today binds content to topological location limiting the mobility of contents, devices, and users between devices. In order to tackle the limitation of IP, Information Centric Networking and Content-Centric Networking (CCN) in particular [START_REF] Jacobson | Networking named content[END_REF][START_REF] Koponen | A data-oriented (and beyond) network architecture[END_REF][START_REF] Ahlgren | Design considerations for a network of information[END_REF][START_REF] Zhang | Named Data Networking (NDN) Project[END_REF] have been proposed to completely remove the notion of location in data networks. In CCN, when a user wants to consume content, it simply has to announce the name of the content it is interested to consume to its neighbor routers. If the content is not available at a neighbor, this last forwards the interest to its neighbors and so on until the content is found. The content then back tracks the trail followed by the interest until the initial requester is reached and intermediate router can cache the content to speed up further content retrieval.

In this paper, we show that Over-The-Top (OTT) service providers like Netflix [2], YouTube [3], Hulu [START_REF] Hulu | [END_REF], or the Xbox LIVE [5] that produce and distribute content to a large basis of consumers can take advantage of using CCN and its loosely collaborative caching mechanism. The idea of CCN and ICN in general is appealing however their deployment require fundamental changes in the Internet [START_REF] Rexford | Future Internet Architecture: Clean-Slate Versus Evolutionary Research[END_REF] and it is then inevitable that CCN will co-exist with IP. Despite the fact that CCN would be only partially deployed in the Internet, we show that it is possible to design a mechanism to interconnect CCN islands over the IP Internet that leverages the use of CCN in OTT even though CCN is not deployed in the Internet core. We design our interconnection mechanism with an overlay optimized for performance and a semi-centralized naming resolution infrastructure that dynamically discover the caches and the content that they store.

To achieve these goals, we first give the necessary background on CCN in Sec. 2. Afterwards, in Sec. 3, we give incentives for OTT consumer networks and OTT service providers to migrate to CCN and determine the conditions that make the adoption profitable for both of them. We then present, in Sec. 4, an overlay-based technique allowing efficient interconnection of OTT consumers and providers over the Internet. The particularity of our overlay is that it is designed to operate in a loosely collaborative environment where consumers might not cache the contents they consume. Our technique relies on a dynamic overlay that associates names and CCN islands and that is optimized for fast transfers. The technique to associate names and CCN islands is described in Sec. 4.3. Finally, Sec. 5 concludes this work.

Content-Centric Networking in a Nutshell

Content-Centric Networking (CCN) proposed by Jacobson et al. in [START_REF] Jacobson | Networking named content[END_REF] rethink the behavior of network while removing any notion of location or topology to only keep the notions of content and content names. In CCN, contents can be anywhere in the network potentially moving or replicated. When a CCN client wants a particular content, it sends an Interest message to its neighboring routers. When a CCN router receives such an interest, it forwards it to its neighbors that can potentially provide the content identified by the name contained in the Interest message.

Because there is no information about its origin in an Interest message, the router maintains an entry in its Pending Interest Table (PIT). The entry maps the name in the interest to the list of faces (i.e., interfaces) on which the interest has been received. When the publisher of the content receives an interest, it replies with a data message. The data message contains the name of the interest and its corresponding ContentObject.

The data message is sent directly to the face on which the interest has been received. The data message then follows the trail defined by the PITs until it arrives at the origin of the interest message. As there is no notion of location in CCN, the content can be at any place. Therefore, every router can maintain a cache to copy and store the ContentObjects from the data messages that transit it and any subsequent request for the same content will then receive the content from the copy instead of the content publisher.

Incentives for OTT to use CCN

Before trying to integrate CCN with Over-The-Top services, it is important to determine whether there are incentives for such integration. As stated in Sec. 2 or in [START_REF] Jacobson | Networking named content[END_REF], CCN, compared to IP, provides better security and performance. This last point is very interesting for OTT service providers that deliver multimedia content where performance is a key factor for the adoption of the service by consumers. With CCN, the content can be retrieved from the caches in the different CCN islands, instead of always being delivered by the content publisher. As a result, content retrieval is faster for the consumer and the operational cost of the publisher is reduced. Moreover, as the content is cached by the consumers and because the consumer can provide the content to other consumers, the overall performance increases with the number of consumers instead of decreasing as it is the case in IP today where the content is delivered by the hosting server. This property is particularly interesting because it dampens the effect of flash crowds which are normally very costly for OTT service providers as they have to provision their servers and networks to support them. Using CCN with caching at the consumers has then a direct impact on the profit earned by the OTT service provider as its costs are reduced. However, to benefit from the caching capabilities of consumers, the producer must propose real incentives to its consumers to collaborate and cache the content. To understand how incentives can be provided, it is necessary to remember that content in OTT is provided either freely to the consumer or in exchange of a fee. When the content is provided freely, the incomes for the publisher are ensured by advertisements dispersed in the content (e.g., banner, commercial interruptions. . . ). A consumer has incentives to collaborate with the system if it receives some sort of discount, expressed in advertisement reduction or fee reduction. On the one hand, the discount has a cost for the publisher as its revenues will be reduced. On the other hand, the collaboration from its consumers reduces its operational costs. Hence, the publisher must determine the optimal discount, such that it maximizes its profit. The situation for the consumer is the exact opposite: its costs are increasing because it is providing content to other consumers but its revenues also increase as it receives a discount on its expenses. We determine in Sec. 3.1 the conditions to be respected by the system to increase the profit of both publishers and consumers when caching is used in CCN. As long as these conditions are respected, deploying CCN at the OTT is beneficial for both producers and consumers.

Profitability Conditions

To generalize and formalize the discussion started above, let's define C, the set of consumers of a given content, C c ⊆ C the set of collaborative consumers (i.e., those caching content), and C n ⊆ C the set of consumers that do not collaborate (i.e., those that not cache content). We have,

C n ∪ C c = C ∧ C n ∩ C c = ∅. (1)
Let F : C → R be the fee requested to the consumer, C : C → R be the cost of providing the content to a consumer from the publisher, and D : C → R be the discount given to the consumers for caching and serving the content on behalf of the publisher. The general formulation of the profit p for a given content at the publisher is given by Table 1. Summary of the variable and function symbols used in Sec. 3.

1 p = x∈C F(x) -C(x). ( 2
)
When discount is provided to collaborative consumers, this profit becomes:

p = c∈Cc F(c) -D(c) -C(c) + n∈Cn F(n) -C(n). (3)
When the number of collaborative consumers is high and their caches are well dimensioned, we can assume a balanced scenario where the publisher only provides content to collaborative consumers and pays the discount to them, whereas non-collaborative consumers retrieve content directly from caches inside the network. In somehow, we ignore the requests from non-collaborative coming directly to the publisher as they do not enter in the calculation of the optimal discount to propose. Eq. (3) then becomes

p = c∈Cc F(c) -D(c) -C(c) + n∈Cn F(n). (4)
In this balanced scenario, the publisher gains at providing discount to its collaborative consumers as long as the profit generated with discount (Eq. ( 4)) is higher than the profit generated without any form of discount (Eq. ( 2)), as shown below.

c∈Cc

F(c) -D(c) -C(c) + n∈Cn F(n) ≥ x∈C F(x) -C(x), (5)
⇔ n∈Cn C(n) ≥ c∈Cc D(c), (6)
where Eq. ( 5) is simplified in Eq. ( 6) because of the conditions in Eq. ( 1). In other words, the publisher gains at providing discount to some consumers if the total cost of distributing the content to consumers that do not collaborate would be higher than the total amount of discount given to the consumers that collaborate. Eq. ( 6) defines the conditions under which collaboration from consumers is profitable for the producer. To determine the optimal discount function D(x), we first have to determine the conditions necessary for a consumer to collaborate, which decides on the sizes of the two sets C c and C n In order to determine whether a consumer will collaborate or not, we must determine its costs structure and compare it to the discount proposed by the publisher. As above, we consider a balanced scenario where consumer that do not collaborate always consume cached copies of the content as these copies provide better quality to them for a lower cost [START_REF] Aggarwal | Can isps and p2p users cooperate for improved performance?[END_REF]. In addition, to obtain an upper bound on the cost per collaborative consumer, we add the further assumption for that. The expenses for a non collaborative consumer n to retrieve the content are the minimum over all cached copied and can be written as:

E(n) = F(n) + arg min c∈Cc C * (n, c), ∀n ∈ C n , (7)
where C * (n, c) : C × C → R is the cost for consumer n to retrieve content from consumer c.

where R(n, c) : C × C → {0, 1} is a binary function that determines whether consumer n demands to retrieve content cached at consumer c or not. The total expenses for the collaborative consumer c is thus

E(c) = F(c) + C * (c) + n∈Cn R(n, c) • C(c, n) -D(c), ∀c ∈ C c . (9)
To accept to collaborate in the system, the expenses payed by an undecided consumer u must be lower if it collaborates than if it does not.

From Eq. ( 8) and Eq. ( 7) we thus have:

F(u)+C * (u)+ n∈Cn R(n, u)•C(u, n)-D(u) ≤ F(u)+arg min c∈Cc C * (u, c). ( 10
)
In other words, a consumer should collaborate if the cost overhead caused by the collaboration compared to the cost it should have supported without cooperation (i.e., cost when collaboration minus cost when no collaboration) is compensated by the discount, or:

D(u) ≥ C * (u) + n∈Cn R(n, u) • C(u, n) -arg min c∈Cc C * (u, c). (11)
A producer that wants to maximize its profit by promoting collaboration with the help of discount has to solve the following optimization problem defined by the combination of Eq. ( 6) and Eq. ( 11):

n∈Cn C(n) ≥ c∈Cc C * (c) + n∈Cn R(n, c) • C(c, n) -arg min i∈Cc C * (c, i), (12)
C n ∪ C c = C, (13)
C n ∩ C c = ∅. (14)
Unfortunately, the producer cannot determine an exact solution for this optimization problem as it knows neither the cost structure of its consumers nor their demands. As a first approximation, the producer can offer the same discount d for all the consumers that collaborate and assume that the cost of providing all the consumers, when no collaboration is performed, is equal and of value ĉ (e.g., the average cost). In this case, Eq. ( 6) is approximated by

d ≤ |C| -|C c | |C c | ĉ. ( 15
)
Eq. [START_REF] Honda | Is it still possible to extend TCP?[END_REF] shows that the discount is a function of the proportion of consumers that collaborate in the system with the more the number of consumers collaborating, the less the discount can be. This equation is summarized in Fig. 1 for different proportions of collaborative consumers.

For a given proportion of collaborative consumers, the profit for the producer is increased as long as the choice of the discount is below the curve.

The exact value that maximizes the profit depends on Eq. ( 11) as the discount is the incentive for consumers to enter in the collaborative system.

As this demand is unknown by the operator and depends of the consumer, it can use a conservative approach by first proposing a discount laying in its own area of acceptable discounts. For that amount of discount, the operator will observe a certain amount of consumers entering the collaborative system. If the proportion of collaborative consumers is too high (resp. too low), then the operator reduces (increases) the discount to reduce (resp. increase) the proportion of collaborative consumers. By continuously adapting its discount, the producer can construct the consumers demand function and progressively offer personalized discounts.

Interestingly, as shown by Fig. 1, negative costs are possible and imply negative discounts. A negative value of cost corresponds to the situation where the producer earns values when using its network. This situation typically corresponds to the case where the OTT service provider is at the provider end of of a customer-provider link [START_REF] Gao | Stable internet routing without global coordination[END_REF]. In this case, the reduction of traffic caused by the collaboration must be compensated by the increase of the fee requested to the consumers (i.e., a negative discount) which can be justified by the offer of a premium service.

Loosely Collaborative Inter-connection of CCN Networks

We have seen in Sec. 3 that Over-The-Top service providers and consumers have incentives in using CCN for participating in the OTT service. We can thus imagine that CCN is deployed at the content producer network and in each consumer network. However, as appealing is contentcentric networking, its deployment requires fundamental changes in the Internet and it is very likely that the Internet core will not shift to the new paradigm rapidly, if ever [START_REF] Rexford | Future Internet Architecture: Clean-Slate Versus Evolutionary Research[END_REF]. We will thus see the emergence of CCN networks at the OTT consumer and producer networks, forming CCN islands composed of devices supporting CCN but inter-connected together via the traditional IP Internet core. To ensure this co-existence with IP, the CCN islands will form an IP overlay. The construction of such IP overlays has been extensively studied for peer-to-peer systems [START_REF] Androutsellis-Theotokis | A survey of peer-to-peer content distribution technologies[END_REF][START_REF] Buford | P2P Networking and Applications[END_REF] and mostly focus on reliability and scalability. However, OTT services provide multimedia content making so the performance criterion passing before reliability and the scalability. In addition, we have seen in Sec. 3 that interest of migrating to CCN for an OTT service is in the caching capabilities of CCN. Finally, the adoption of the new model assumes collaboration from the consumers but while strong collaboration is possible inside a network operated by the administrative instances, the OTT consumers are spread on the Internet under distinctive administrations and only a loosely collaboration is possible (e.g., some consumer can cheat or have policies that they cannot disclose). To achieve our goals, we propose an overlay that (i) is closely embedded on the IP network in order to minimize path stretch, (ii) authorizes traffic deflection to consumer caches as long as performance of consuming contents from caches are better than those of consuming content directly from the publisher, and (iii) dynamically learns the cached contents and the consumer CCN islands while operated in loosely collaborative networks.

IP Overlay for CCN Interconnection

The network in a CCN island can be composed of an arbitrary number of CCN nodes that communicate together by natively using the CCN protocol. Each island is connected to the Internet with a dual-stacked gateway which role is to allow CCN islands to seamlessly communicate over the IP Internet core. The role of a gateway is three-fold: (i) associate content to possible CCN islands, (ii) encapsulate CCN messages over IP and forward them on the Internet core, and (iii) decapsulate packets received from other CCN islands and forward them to the CCN island it is attached to. Fig. 2 summarizes the overlay behavior in normal conditions.

The association between contents and their possible locations is achieved by the Naming Resolution Infrastructure (NRI) that dynamically binds content names to the IP address of the gateways of the CCN islands that potentially cache the content. The NRI binds each name with a list of gateway addresses, each address annotated with a priority and a weight.

The gateway with the lowest priority value address should be selected because it will offer the best performance. In addition, CCN provides the support of multipath transfers, then if several choices are possible (i.e., several addresses with the same lowest priority value), they can be used in parallel proportionally to their weight (i.e., an address with a high weight is more likely to be selected than an address with a low weight). The presence of several addresses with different priorities improves the robustness of the binding as it is possible that the best gateways determined by the NRI might not be reachable from the NRI's client. A detailed description of the NRI is given in Sec. 4.3.

On the one hand, when a gateway receives an Interest message from its CCN island, it first determines the list of remote gateways that cache the content by sending a resolution querying to the NRI. The gateway selects the best remote gateways according to priorities and weights found in the binding retrieved from the NRI. The interest message is then encapsulated into an IP packet which source is the address of the local gateway and the destination is the address of the remote gateway. To maximize the chance of traversing the middleboxes in the Internet while minimizing the connection time, the CCN message is not encapsulated directly in IP or TCP but in UDP [START_REF] Honda | Is it still possible to extend TCP?[END_REF]. The encapsulated packet is then sent directly to the Internet core. This encapsulation scheme constitutes a minimalist overlay that minimizes path stretch as packets are sent to the gateways via the direct IP path which avoid detour that can degrade performance.

Moreover, our overlay does not require any routing mechanism as it relies directly on its underlay avoiding so routing inconsistencies but also convergence problem. It is worth noticing that the gateway can cache the binding it learns from the NRI for future use.

On the other hand, when a gateway receives an encapsulated CCN message, it decapsulates and forwards it into the CCN network it is attached to. Care must be taken when messages are decapsulated. Indeed, by principle, CCN messages do not contain any explicit information about the node that initially emitted interest for the content. To overtake this constraint, CCN uses symmetric paths between the Interest message and its corresponding Data message. When a Data message is received, it is forwarded to the faces on which an Interest messages for the same content name have been received. Alas, the face that is connected to the Internet at the gateway is an IP interface and thus implies that CCN messages must be encapsulated in IP with the destination address corresponding to the address of the gateway that sent the corresponding Interest message.

As this address is not present in the Data message, additional state must be kept by the gateway that received the Interest. To comply with CCN and keep the system its genericity, we do not add this state into CCN but instead use the notion of virtual IP face. A virtual IP face is seen as a normal face by CCN. However, virtual IP faces are dynamically instantiated when an Interest message is decapsulated and destroyed whenever the corresponding data message has been encapsulated and sent back to the initial gateway. The necessary state is maintained directly by the virtual IP face that remembers the parameters of the encapsulating IP packet (i.e., IP addresses and UDP ports). Hence, the virtual face can encapsulate and send Data message it receives to the appropriate gateway. On the contrary, when an encapsulated Data message is received, the gateway only has to decapsulate it and forward it to its attached CCN network that maintain PIT entries for the content provided in the message.

The overlay that we propose is a tradeoff between the constraints of IP, the location independence of CCN, and the performance requirements of OTT services. On the one hand, IP strongly depends on the topological location because of the IP addresses, but, on the other hand, CCN is decoupled to location as content can be anywhere in the network. For that very reason and because OTT services require good network performance, the interconnection of CCN islands is done by the mean of a dynamically constructed overlay directly embedded in the IP infrastructure. Hence, the locations remain invisible in the CCN networks but CCN messages are sent optimally between the islands according to the IP path.

Performance Based traffic Deflection

The role of the Name Resolution Infrastructure is to associate content names to the address of the gateways of CCN islands that potentially cache that contents. As discussed in Sec. 4.3, these binding are constructed such that caches offering the best performance are preferred.

However, the conjunction of OTT services and caching forms a loosely collaborative system where the content might not be cached in the selected island even if the binding presumed so. With a traditional IP approach, if the content is not available at a cache, the consumer must try itself another cache as each of its request is targeted to a particular cache with the IP address. On the contrary, with the location independence of CCN, if an Interest message arrives at a CCN island that does not cache the content, it can seamlessly be recursively re-directed to another CCN island that potentially caches the content. Unfortunately, the performance decreases with the number of hops [START_REF] Aggarwal | Can isps and p2p users cooperate for improved performance?[END_REF]

Name Resolution Infrastructure

The very purpose of the Naming Resolution Infrastructure (NRI) is to provide bindings between content names and CCN islands that cache them. However, as the content can be cached at any position in CCN, the producer of the content will not observe the CCN islands that consume cached content. However, to leverage the use of the cache in our overlay, the bindings must be constructed with the knowledge of all the CCN islands that consume the content. To that reason, we construct a semicentralized NRI where every query for a particular content is transmitted to the publisher of the content via a decentralized hierarchical resolution infrastructure. In the NRI, the publisher learns all its consumers and their caching infrastructure. The publisher can then construct the binding to leverage the use of caches while following its own policies. The hierarchical infrastructure used to convey the binding queries from consumers to the publisher is built directly on IP and follows the same principle as the Domain Name Service (DNS) and could even be implemented directly with it [START_REF] Mockapetris | Domain names -concepts and facilities[END_REF]. We copied model DNS for our NRI because its structure is semi-centralized and years of operation have proven its robustness, scalability, and flexibility. In CCN, the namespace is a prefix tree where the name associated to a node is a prefix of the name associated to any of its children [START_REF] Jacobson | Networking named content[END_REF]. We can therefore build a hierarchy of naming resolution servers, each server being authoritative for the name assigned to it, and the name of a server is a prefix of the name assigned to the children of the servers. A resolution server is then in charge of maintaining the bindings for the names it is authoritative and the list of its children with their assigned name. To resolve a name, an NRI client sends a resolution query to a server at the root of the naming tree. The server returns in a referral message the address of the children that are authoritative for the longest prefix matching the queried name. The client then sends a query to one of these children that will, at its turn return the address of its longestmatching children, and so on until the server that is authoritative for the perfectly matching queried name is reached. When a server receives a query for a name it is authoritative for, it replies the client with the binding for the name of interest. As the server that provides the binding is the same for any client that is willing to consume the content identified by this name and that this server is operated by the publisher, the publisher is able to construct a map of the CCN islands that consume its content.

This consumer map is used to construct the bindings dynamically and then leverage the caching capabilities of CCN. Fig. The binding construction is based on the consumer map the producer builds. To optimize the use of cache and retrieval performance, the optimal binding is built by the producer for each consumer. To do so, the map of consumers is consolidated with BGP information and the Application-Layer Traffic Optimization (ALTO) service [START_REF] Seedorf | Application-Layer Traffic Optimization (ALTO) Problem Statement[END_REF]. With this abstracted map of the network, the publisher determines the topological distance between the islands and group consumers by their topological location as nodes inside a prefix present similar performance [START_REF] Cai | Understanding block-level address usage in the visible internet[END_REF]. It is worth noticing that our service is loosely collaborative and an island that consumes the content might not cache it. Because of this particularity, the producer should build a statistical caching behavior of its consumers. To do so, the producer can monitor its consumers with the out-of-band mechanism it maintains with its consumers to customize (e.g., with advertisements) the content it provides them even if the static content is cached.

Conclusion

In this paper, we show that CCN presents strong incentives for Over-The-Top (OTT) service providers and consumers like YouTube or Netflix.

However, the transition to CCN might be long because of the fundamental changes it causes in the network. Therefore, we present a transition mechanism based on a dynamic overlay optimized for performance and a naming resolution infrastructure that allows OTT services to leverage the use of CCN caches in a global Internet where CCN is only partially deployed. The principle of our solution is to place a gateway speaking CCN an IP at the border of each CCN island and to dynamically build bindings between the name of contents cached in the island and the address of the gateway of the island. The binding is then used to dynamically construct an overlay to inter-connect the CCN islands and then leverage the use of caches.

C

  Set of consumersCcSet of consumers that collaborateCnSet of consumers that do not collaborate C(c) Cost supported by the producer to provide the content to consumer c C * (c) Cost supported by consumer c to retrieving the content from the publisher ĉ Approximation of a unique cost for the producer C(c, n) Cost supported by consumer c to provide the cached content to consumer n C * (n, c) Cost supported by consumer n to retrieve the content from consumer n D(c) Discount paid by the publisher to consumer c d Approximation of a unique discount paid by the producer E(c) Expenses supported by consumer c to retrieve the content F(c) Fee requested by the producer to consumer c p Profit of the content producer from providing the content R(n, c) Demand function of the consumer n to retrieve a cached copy from consumer c

  Consumers that collaborate have to support the cost of maintaining and distributing copies. Therefore, if C(c, n) : C × C → R gives the cost for the collaborative consumer c to provide the cached content to the non collaborative consumer n, then the cost of the collaboration for c is given by n∈Cn R(n, c) • C(c, n),

Fig. 1 .

 1 Fig.1. Evolution of the optimum discount with the cost (ĉ) for different percentage of the number of consumer collaborating. The producer increases its profit as long as the discount (y-axis) is below the curve for a given cost (x-axis).

Fig. 2 .

 2 Fig. 2. Example of the transfer of CCN messages with the overlay

Fig. 3 .

 3 Fig. 3. Example of the transfer of CCN messages with the overlay and re-direction to the content producer

Fig. 4 .

 4 Fig. 4. Naming hierarchy traversal

2 3 Content Producer gateway gateway Content Consumer Gateway 6 7 8 5 198

1,5. Interest for /example.org/videos/high/WidgetA.mpg/_v0/_s3 1 4. Encapsulated Interest for /example.org/videos/high/WidgetA.mpg/_v0/_s3 4 7. Encapsulated Data for /example.org/videos/high/WidgetA.mpg/_v0/_s3 6, 8. Data for /example.org/videos/high/WidgetA.mpg/_v0/_s3 192.0.2.1 198.51.100.9 3. Binding for /example.org/videos/high/ {198.51.100.9, 192.0.2.1*} 2. Query binding for /example.org/videos/high/ WidgetA.mpg/_v0/_s3 .51.100.

10 Naming Resolution Infrastructure Content Consumer Content Producer Gateway Content Consumer

Naming Resolution Infrastructure Content Consumer Content Producer gateway gateway Gateway Content Consumer 6 Gateway 9 10 11 12 5 198

  and OTT services depend on network performance. For that reason and to ensure correctness of Interest forwarding in the overlay (i.e., if the content exists, the Interest message will eventually arrive at a CCN island that stores the content), when a CCN island does not store the content requested by another CCN island, it redirects the interest message to the CCN island publisher where it is certain that the content is available. In other words, an Interest message is deflected only once to a cache. To allow this, Interest messages are annotated when they enter the island and when a gateway that connects the CCN network to the overlay receives such annotated Interest message, it forwards it to the publisher island. The address of the publisher island gateway is learned with the bindings where publisher gateway addresses are flagged. Fig.3summarizes the behavior of the overlay when re-direction is required.

				1,5,7. Interest for
				/example.org/videos/high/WidgetA.mpg/_v0/_s3
	2. Query binding for			1
	/example.org/videos/high/WidgetA.mpg/_v0/_s3
	2	3. Binding for	3
		/example.org/videos/high/ {198.51.100.9, 192.0.2.1*}	4
				198.51.100.9
		4/6. Encapsulated Interest for
		/example.org/videos/high/WidgetA.mpg/_v0/_s3
			192.0.2.1
	8, 10, 12. Data for		7	8
	/example.org/videos/high/WidgetA.mpg/_v0/_s3
	9/11. Encapsulated Data for
	/example.org/videos/high/WidgetA.mpg/_v0/_s3

.51.100.10

/example.org/videos/high/WidgetA.mpg/: 192

  100% 198.51.100.9, priority: 10, weight: 100%, publisher 2. Referral for /example.org/ is 192.0.2.29 192.0.2.1 198.51.100.9 Name Resolver 198.51.100.10 1,3, 4, 5, 7. Query for /example.org/videos/high/WidgetA.mpg/ v0/ s3 Referral Server: 192.0.2.11 Name Server: 192.0.2.12 Name Server: 192.0.2.13 Referral Server: 192.0.2.21 Referral Server: 192.0.2.29 Referral Server: 192.0.2.42 Referral Server: 192.0.2.69 4. Referral for /example.org/videos/ is 192.0.2.11 6. Referral for /example.org/videos/high/ is 192.0.2.12

			1
	/		2
				3	4
	/example.com/	/example.org/
				5	6
	/example.org/music/	/example.org/ videos/	7
		/example.org/	/example.org/
		videos/low/	videos/high/
				4.3 gives an example
	of name resolution in the NRI.

.0.2.1, priority: 1, weight:

8 8 .

 8 Binding for /example.org/videos/high/WidgetA.mpg/ is 192.0.2.1, priority: 1, weight: 100% 198.51.100.9, priority: 10, weight: 100%, publisher

Content Consumer Content Producer Gateway Content Consumer Gateway gateway


Keywords: Voxel-based morphometry, biomarkers, magnetic resonance imaging, hippocampus, temporal lobe, para-hippocampal cortex

Learning objectives:

1. To develop a new Patch-Based Morphometry method in order to enable more accurate anatomical comparison between populations. 2. To evaluate the proposed method on AD population compared to normal controls.

Patch-Based Morphometry: Application to Alzheimer's Disease

Pierrick Coupé 1,2 Background: While widely used to detect morphological differences between groups, Voxel-Based Morphometry (VBM) [1] is based on the assumption of one-to-one anatomical mapping between subjects and Gaussian distributions of focal tissue densities during statistical testing. To make data fit this model, tissue densities are blurred with large kernels at the expense of focal accuracy. To these issues, we propose a new Patch-Based Morphometry (PBM) method derived from our recently proposed innovative method to detect fine anatomical changes in MRI called Scoring by Nonlocal Image Patch Estimator [START_REF] Coupe | Simultaneous Segmentation and Grading of Anatomical Structures for Patient's Classification: Application to Alzheimer's Disease[END_REF]. SNIPE takes advantage of non-local analysis to handle the one-to-many mapping between brain anatomies. In this study, we extend SNIPE to the whole brain before comparing populations with PBM scores.

Methods:

We randomly selected 50 MRI from cognitive normal (CN) subjects and 50 MRI from AD patients from the ADNI database.

Step 1: the 100 images were processed as described in [START_REF] Coupe | Simultaneous Segmentation and Grading of Anatomical Structures for Patient's Classification: Application to Alzheimer's Disease[END_REF] (inhomogeneity correction, intensity normalization and rigid registration to MNI-ICBM152-nonlinear). Through a leave-one-out procedure, SNIPE was applied on each of the MRI scans using 30 images from each population as training templates.

Step 2: all grading maps were nonlinearly registered to the MNI-ICBM152-nonlinear template with ANIMAL [3].

Step 3: a non-parametric Kruskall-Wallis test was performed at each voxel to estimate statistical differences between populations.

Results:

Examples of grading maps are presented in Figure 1. Figure 2 shows the pvalues overlaid on the MNI-template. Maximum differences between AD and CN were found in hippocampus and para-hippocampal areas, entorhinal cortex and in the temporal lobe around the lateral sulci and insula. Moreover, diffuse differences appear within the gray matter. These results are consistent with previous VBM results [4]. We also noted an important difference around the superior mammillary notches as previously reported in volumetric studies [5].

Conclusion:

In this proof of concept study, we showed that PBM produces results consistent with previously published VBM studies. However, contrary to VBM, these results were obtained without a blurring step since PBM can work at the voxel resolution. Further work will investigate optimal parameters for SNIPE and the possibility of using multivariate tests.

CNADFigure 1 :Figure 2 :

 12 Figure 1: Left: SNIPE map for a normal control aged of 77 years with an average grading value of 0.7. Right: SNIPE map for a patient with AD aged of 78 years with an average grading value of -0.5. Values close to 1 (red) indicate areas where the image is more similar to CN population and value close to -1 (purple) indicate areas where the image is more similar to AD population. The maps are displayed in the MNI space after rigid registration (Step 1).

  , José V. Manjón 3 , Vladimir Fonov 2 , Simon F. Eskildsen 2 , D. Louis Collins 2 and The Alzheimer's Disease Neuroimaging Initiative * 1 Laboratoire Bordelais de Recherche en Informatique, Unité Mixte de Recherche CNRS (UMR 5800), 351 cours de la Libération F-33405 Talence cedex 2 McConnell Brain Imaging Centre, Montreal Neurological Institute, McGill University, Montreal, Canada. University, 3801 University Street, Montreal, Canada H3A 2B4 3 Instituto de Aplicaciones de las Tecnologías de la Información y de las Comunicaciones Avanzadas (ITACA), Universidad Politécnica de Valencia, Camino de Vera s/n, 46022 Valencia, Spain


Lucie Daubigney

Matthieu Geist

Olivier Pietquin

OFF-POLICY LEARNING IN LARGE-SCALE POMDP-BASED DIALOGUE SYSTEMS

Keywords:

Reinforcement learning (RL) is now part of the state of the art in the domain of spoken dialogue systems (SDS) optimisation. Most performant RL methods, such as those based on Gaussian Processes, require to test small changes in the policy to assess them as improvements or degradations. This process is called on policy learning. Nevertheless, it can result in system behaviours that are not acceptable by users. Learning algorithms should ideally infer an optimal strategy by observing interactions generated by a non-optimal but acceptable strategy, that is learning off-policy. Such methods usually fail to scale up and are thus not suited for real-world systems. In this contribution, a sample-efficient, online and off-policy RL algorithm is proposed to learn an optimal policy. This algorithm is combined to a compact non-linear value function representation (namely a multilayers perceptron) enabling to handle large scale systems.

INTRODUCTION

Spoken dialogue systems (SDS) are now commonly used for addressing various tasks like appointment scheduling, troubleshooting, tutoring, etc. When building an SDS, efficiency and naturalness are of great importance since SDS are interacting with humans who can be quickly annoyed when speaking to a machine. To obtain those characteristics, the dialogue manager (DM) of the SDS -responsible for taking decisions about what to say and when -should have an adapted behaviour which takes the user into account. More difficulty is brought by the speech recognizer and semantic analyser of the SDS which respectively transcripts and analyses what the user said. Indeed, the two components are error-prone which makes the actual user goal partially observable by the DM.

Handcrafting a strategy that will lead to the achievement of the task so as to satisfy the user, becomes rapidly untractable when the task is realistic. Indeed, it requires to identify all the possible situations which can be encountered during the course of a dialogue. So solutions have been proposed to automatically search for optimal strategies. We focus on those based on reinforcement learning (RL) [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]. RL is a machine learning technique that has been successfully applied to SDS optimisation [START_REF] Singh | Reinforcement learning for spoken dialogue systems[END_REF][START_REF] Levin | A stochastic model of humanmachine 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]. The idea of these algorithms is to learn an optimal strategy from interactions between the SDS and users, so as to optimise a numerical value (reward) related to user satisfaction. The optimal value function from which the optimal strategy can be derived is the one that associates the highest possible cumulative reward to each dialogue situation. Finding the optimal strategy thus resumes to the problem of learning the optimal value function. The major drawback of standard RL methods used so far in the field of SDS optimisation is to be very data demanding. The required number of actual interactions could not be collected in a tractable way. For more than one decade, this issue has been addressed by simulating dialogues so as to artificially generate enough data [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]. But this method introduces additional modeling bias which can lead to inadequacy of the learnt strategy with the behaviour of real users [START_REF] Schatzmann | Effects of the user model on simulation-based learning of dialogue strategies[END_REF].

Efficient online algorithms have been proposed recently [START_REF] Gašić | Gaussian processes for fast policy optimisation of POMDPbased dialogue managers[END_REF][START_REF] Jurcicek | Natural Belief-Critic: a reinforcement algorithm for parameter estimation in statistical spoken dialogue systems[END_REF]. These works report the use of online and on-policy algorithms requiring to permanently changing and testing the policy to learn. These changes to the policy made during learning are visible to the user which may cause problems in real applications at the early stage of learning where the changes in the policy can lead to very bad behaviours of the dialogue manager. Moreover, these methods are based on linear approximations of the value function which makes their practical use in large-scale systems difficult. To scale-up, the dialogue context has to be represented in a compact way [START_REF] Williams | Scaling up POMDPs for dialogue management: the summary POMDP method[END_REF] which may lead to approximation errors.

In this paper, we propose to use the Kalman Temporal Differences (KTD) algorithm [START_REF] Geist | Kalman Temporal Differences[END_REF] to achieve efficient online, off-policy learning [START_REF] Pietquin | Sample Efficient Online Learning of Optimal Dialogue Policies with Kalman Temporal Differences[END_REF] in large-scale system. We also propose to use a compact representation to estimate the value function (based on Multilayer Perceptron) so as to minimize the impact of approximations. Off-policy learning will allow learning online from a behavioural strategy which is controlled After enough interactions, the DM can switch to the optimal strategy learnt to present it to the user.

DIALOGUE MANAGEMENT AS A CONTINUOUS MARKOV DECISION PROCESS

Dialogue management (DM) is actually a sequential decision making problem. From user acts (observations), the dialogue manager should choose and perform system acts (actions) in order to interact with the user in an efficient and natural way. User satisfaction is quantified by a reward provided at the end of a dialogue and computed as a linear combination of objective measures (such as the task completion, the dialogue duration, etc.).

Framed like this, DM can be cast as a Partially Observable Markov Decision Process (POMDP): decisions should be taken according to the full history of user and system acts. This history can be briefly and efficiently summarized into a single state by the hidden information state paradigm [START_REF] Young | The hidden information state model: A practical framework for POMDP-based spoken dialogue management[END_REF]. Thus, DM can be cast as a continuous state MDP [START_REF] Williams | Partially observable Markov decision processes for spoken dialog systems[END_REF].

Algorithms search for a policy π associating an action (a ∈ A) to each state (s ∈ S). The quality of the policy is quantified by a function called Q-function. This function associates to each state-action pair the expected cumulative reward after having started in this pair and then followed the policy π: Q π (s, a) = E[ i≥0 γ i ri|s0 = s, a0 = a, π]. The factor γ is the discount factor, (s, a) the state-action pair and (ri) i≥0 the set of obtained rewards. The optimal Q-function, Q * , is defined so that for all (s, a) ∈ S × A, for all π, Q * (s, a) ≥ Q π (s, a). From Q * , the optimal policy π * , which is greedy relatively to it, can be derived: π * (s) = arg max a Q * (s, a). Notice that the Q-function allows comparing not only two policies but also two actions for a given state under a fixed policy. Usually, the state-action space is too large (often continuous) to allow an exact computation of the Q-function and an approximate representation Q(s, a) is mandatory. The representation is often parametric Qθ (s, a), with θ the set of parameters.

Two general schemes are used to compute the optimal Qfunction. First, on-policy learning improves the policy being learnt incrementally, by iteratively computing the value of this policy then changing the policy by making it greedy according the computed Q-function. Because of the Markov property of the transition probabilities, the evaluation phase can be done thanks to the Bellman evaluation equation:

Q π (s, a) = E s ′ |s,a [R(s, a, s ′ ) + γQ π (s ′ , π(s ′ ))].
The state s ′ is reached after having followed the action a returned by the policy π from s. This scheme is adopted by the GPTD algorithm used in [START_REF] Gašić | Gaussian processes for fast policy optimisation of POMDPbased dialogue managers[END_REF]. The results provided by this algorithm will serve as a point of comparison for the experiments presented in this paper. Notice that the Bellman evaluation equation is linear which is mandatory for using Gaussian Processes (GP). GP constrain the parametrisation Qπ θ (s, a) to be linear as well. The other scheme is off-policy learning. This method consists in directly computing the optimal value function Q * (s, a) using the non-linear Bellman optimality equation:

Q * (s, a) = E s ′ |s,a [R(s, a, s ′ ) + γ max b∈A Q * (s ′ , b)].
The KTD framework [START_REF] Geist | Kalman Temporal Differences[END_REF] handling non-linearities, this equation can be solved directly and efficient off-policy learning is made possible [START_REF] Pietquin | Sample Efficient Online Learning of Optimal Dialogue Policies with Kalman Temporal Differences[END_REF]. In this paper, we propose to take advantage of this to use a non-linear parametrisation for Q * θ (s, a) to obtain a compact representation of the optimal value function and to scale-up to a richer state representation.

Q-FUNCTION APPROXIMATION

The Q-function (optimal or not) has to be approximated by Qθ (s, a) since the state space S is continuous and Q : S × A → R. The representation for the Q-function can be linear or non-linear.

In the linear case, the Q-function is represented by Qθ (s, a) = θ T Φ(s, a),where Φ(s, a) is a feature vector of size N (number of parameters) so that Φ = [φ1(s, a)...φN (s, a)] T is a predefined set of basis functions and θ are the associated weights.

If a non-linear representation is chosen, the Q-function can be represented by Qθ (s, a) = f θ (s, a), with f θ being non-linear in the parameters θ. In this paper, we used an MLP which is known to be able to approximate any function if containing enough neurons on hidden layers. The vector θ thus contains the synaptic weights of the MLP.

We define H as the hypothesis space generated by the features Φ(s, a) or by f θ (s, a). The H space has to be rich enough to contain the Q-function but the number of parameters should not be too high because of risks of a poor capacity of generalisation and computational costs.

EXPERIMENT

The results presented in the next section have been obtained with the CamInfo system [START_REF] Young | The hidden information state model: A practical framework for POMDP-based spoken dialogue management[END_REF], a large scale SDS developed to provide tourists informations about the Cambridge city (UK). The user request can contain up to 12 different attributes. All the results have been obtained with simulated users [START_REF] Schatzmann | Agenda-based user simulation for bootstrapping a pomdp dialogue system[END_REF] because of the difficulty of having real data and because of the high variability between users possibly provided. This is not necessarily the case when only a sample of users is available. Speech understanding error are also simulated.

During the learning phase, a reward of +20 is given to the system at the end of the dialogue if the DM managed to satisfy the user request. A penalty of -1 is given at each system turn. The initial state space is built as described in [START_REF] Young | The hidden information state model: A practical framework for POMDP-based spoken dialogue management[END_REF]. A state is a vector containing two continuous variables (representing the 2-best confidence scores in the list of hypotheses of what the user said provided by the speech and semantic analysers) and two discrete ones (representing an hypothesis on the user goal and the user action associated with the top confidence score).

The results have been obtained by first letting the DM learn an estimation of the Q-function, Qlearnt (s, a). In the GPTD case, the Q-function estimation is improved at each step of the learning while in the KTD case, an estimation of the optimal Q-function is directly derived. Then the Q-function learnt will be used to test the greedy strategy π learnt = arg max a Qlearnt (s, a). With sufficient training data, the two algorithms are assumed to give the same optimal strategy: π learnt should be equal to π * . On the graphs presented, the average cumulated rewards got while using π learnt is plotted for different sizes of training sets.

The learning phase supposes to use a behavioural strategy to explore the state space (issue known as the exploration/exploitation dilemma). The KTD and GPTD algorithms provide an estimation of the Q-function and some uncertainty information about the quality of the estimation (σQ) [START_REF] Geist | Managing Uncertainty within the KTD Framework[END_REF][START_REF] Gašić | Gaussian processes for fast policy optimisation of POMDPbased dialogue managers[END_REF]. An approach where the agent makes a safe compromise between exploiting the already known information or exploring the state space has been studied in [START_REF] Daubigney | Uncertainty management for on-line optimisation of a POMDP-based large-scale spoken dialogue system[END_REF] on the same SDS and gave encouraging results. It will thus be used here. This approach is called bonus-greedy (inspired by [START_REF] Kolter | Near-Bayesian Exploration in Polynomial Time[END_REF]) and the choice of the next action is made according to: ai+1 = arg max a ( Qi(si+1, a) + β σQ i (s i+1 ,a) β 0 +σ Q i (s i+1 ,a) ).

RESULTS

The GPTD algorithm using a linear parametrisation based on a dictionary built during the learning phase [START_REF] Engel | Reinforcement Learning with Gaussian Processes[END_REF] is compared to KTD using at first a linear parametrisation and then a non-linear one.

First, the comparison is made in an almost noisyless environment (the recognition error rate is set to 10%). The number of parameters is about 300 for the GPTD algorithm and 144 for the KTD one. The vector of parameters for the latest, defined for all (s, a) ∈ S × A is:

Φ T (s, a) = [δa,a 1 φ T (s, a1), ..., δa,a 12 φ T (s, a12)], with φ T (s, a) = [1, ϕ 1 1 , ϕ 1 2 , ϕ 1 3 , ϕ 2 1 , ϕ 2 2 , ϕ 2
3 , I1, I2](s, a) and δ a,a ′ = 1 if a = a ′ else δ a,a ′ = 0. Three Gaussians ϕ are used per continuous dimension and two integers, I1, I2 are used for discrete ones. The DM can choose actions among 12 meta-actions (a1, a2, ..., a12) which can result into 22 different actual actions for the user (see [START_REF] Young | The hidden information state model: A practical framework for POMDP-based spoken dialogue management[END_REF]).

The results on Fig. 1(a) show that KTD outperforms GPTD. KTD policy results in nearly 2.5 turns less per dialogue. In both cases, the solution found is imperfect because of the compression of the state space as explained in [START_REF] Young | The hidden information state model: A practical framework for POMDP-based spoken dialogue management[END_REF]. The speech and semantic analyzers return a list of hypotheses with a confidence score associated. Some information is extracted from the pool of hypotheses to be given to the DM since all the hypotheses cannot be taken into account. But in the GPTD setting described in [START_REF] Gašić | Gaussian processes for fast policy optimisation of POMDPbased dialogue managers[END_REF], information is also lost because some clustering of the state space is performed. It is not the case with KTD where all the states encountered are taken into account for the estimation of the Q-function.

On Fig. 1(b), the average frequency of each of the actions performed by the dialogue manager during the testing phase is shown. The "Others" action regroups 7 others actions which are not used here. By studying the actions proposed, the differences seen in the graphes can be explained and the two algorithms compared. The two policies found do not propose the same main action: GPTD asks for the user to select between two propositions ("Select2" action) while it provides the user with direct information in KTD ("Inform" action). GPTD asks for the user to repeat quite oftenly ("Re-qRepeat" action) while KTD prefers to ask for explicit confirmation ("ExplConfReq" action). It is easier to recognize a yes/no answer than a complete sentence. KTD asks sometimes for new information while implicity confirming another ("ImplConfReq" action) which can shorten the length of the dialogue. GPTD proposes sometimes partially right solution ("Deny" action) which is linked to the use of the "Select2" action. A non-linear parametrisation based on a Multi Layers Perceptron (MLP) is now introduced. One hidden layer of 8 neurons is used (NH 1 = 8). The number of input neurons of the MLP is determined by the fact that to parts of each pair (s, a) ∈ (S × A) must be associated a unique binary combination, given that no metric is defined over the action space. The number of inputs, NI is: for the state space, 2 neurons for the continuous components (2 top scores), 6 for the recognized goals, 22 for the user actions; for the action space, 12 neurons are needed. So NI = 2+6+22+12 = 42. The output layer of the MLP contains one neuron (the value of the Q-function). The number of parameters is:

NI •NH 1 +(NH 1 +1)•1 = 42•8+9 = 345.
The parametrisation based on an MLP is interesting since even if the input space is bigger, the number of parameters needed to cor-rectly represent the function to estimate does not become huge. For example, if a discrete value taking N different values is added to the state space, the number of parameters is multiplied by N while with the neural network approach here, only NH 1 • N parameters are added to the previous parametrisation. In the case of a continuous variable, only one input neuron is added. This property can be used to increase the state space size and enrich the state representation. It will thus avoid losing some easily available information.

A continuous dimension is thus added by taking into account the third confidence score as well as a discrete dimension which is the user action associated with the second top confidence score. The new state space has now six components. The number of inputs is NI = 42 + 22 + 1 = 65 so the number of parameters is: 65 • 8 + 9 = 529. To compare, if a RBF approach was used, the number of parameters would be about (1 + 3 3 ) • 6 • 22 • 22 • 12 = 975.744, with only 3 Gaussians in each of the continuous dimensions.

The performance of the KTD approach in an environment with little noise (error recognitition rate set to 10%), with this non-linear parametrisation and either the initial state space or the new state space has been compared to the GPTD one in Fig. 2(a). The GPTD approach is used with the initial state space because of its unability to scale up. The results obtained with the KTD algorithm are better than the one got with GPTD considering that sufficient training data are provided.When an MLP is used, the curve steps because of the intrinsic property of the MLP: during the learning, the Q-function is either not approximated (when not enough training data are provided) or correctly approximated (after a sufficient number of data are provided). The difference when information is added to the state space is not obvious. Adding information when there is little noise is not very interesting since the speech and semantic analysers are confident with what they recognize. So the list of hypotheses they make is not very long and all the information is contained in the very top ones. In Fig. 2(b) are compared the frequencies of the actions returned by the DM while testing the three policies. The histograms are quite similar to those obtained in Fig. 1(b).

Adding information should be more interesting in noisy situations since the list of hypotheses should be longer and the confidence score associated should be more uniformly distributed among hypotheses. For that reason, a learning has been made in a very noisy situation (recognition rate sets to 50%). The average number of parameters in GPTD approach is about 700. This number which is the size of a dictionary built online, is bigger in noisy environments. This dictionary is larger in that case since a wider part of the state space is visited. The results are presented Fig. 3. While there was no remarkable difference between the runs when little noise was set, now a difference exists. In Fig. 3(a), the MLP approach with initial state space is still better than the GPTD approach. Now in the case where additional information is brought, the KTD approach with enriched state space gives better results: the average length of a dialogue is shorten by 2 turns. In Fig. 3(b), the frequencies of the actions proposed are presented. The trend between the GPTD and the KTD algorithms are the same than in the little noisy environment. But explicit requests are more frequent when less information is present.

CONCLUSION

In this paper, we proposed the use of a Kalman Temporal Differences based algorithm [START_REF] Geist | Kalman Temporal Differences[END_REF] to learn efficiently in an off-policy manner a strategy for a large scale dialogue system. A linear parametrisation has fisrt been used to represent the Q-function. Then, because the KTD framework is able to handle non-linear parametrisations, it has been associated to a compact value function approximator in the form of a Multi Layer Perceptron. Thanks to this compact representation, the dialogue state representation could be enriched to include additional information about the distribution of confidence scores over hypothesis. It is interesting since by taking more information into account, less modeling bias is introduced. This enriched state representation showed to outperform current algorithms like the Gaussian Process Temporal Differences algorithm and more robust dialogue strategies could be computed.

In the future, richer state representations will be tested since the increase in the number of parameters is not prohibitive in the case of a MLP-based value function approximation.

Fig. 1 .

 1 Fig. 1. GPTD and KTD with linear parametrisation comparison.

Fig. 2 .

 2 Fig. 2. GPTD and KTD (with non-linear parametrisation) comparison (10% recognition errors).

The authors want to thanks Steve Young, Milic ¸a Gašić and the Cambridge Dialogue Systems Group for their help in using the CamInfo system. This work is partly funded by the INTERREG IVa project ALLEGRO and the Région Lorraine (France).