Christian Abbet, Meryem M’hamdi, Athanasios Giannakopoulos, Robert West, Andreea Hossmann, Michael Baeriswyl, Claudiu Musat. Proceedings of the 22nd Conference on Computational Natural Language Learning. 2018.

Keyphrase extraction is the task of automatically selecting a small set of phrases that best describe a given free text document.Supervised keyphrase extraction requires large amounts of labeled training data and generalizes very poorly outside the domain of the training data.At the same time, unsupervised systems have poor accuracy, and often do not generalize well, as they require the input document to belong to a larger corpus also given as input.Addressing these drawbacks, in this paper, we tackle keyphrase extraction from single documents with EmbedRank: a novel unsupervised method, that leverages sentence embeddings.EmbedRank achieves higher F-scores than graph-based state of the art systems on standard datasets and is suitable for real-time processing of large amounts of Web data.With EmbedRank, we also explicitly increase coverage and diversity among the selected keyphrases by introducing an embedding-based maximal marginal relevance (MMR) for new phrases.A user study including over 200 votes showed that, although reducing the phrases' semantic overlap leads to no gains in F-score, our high diversity selection is preferred by humans.

Spoken language understanding (SLU) systems, such as goal-oriented chatbots or personal assistants, rely on an initial natural language understanding (NLU) module to determine the intent and to extract the relevant information from the user queries they take as input. SLU systems usually help users to solve problems in relatively narrow domains and require a large amount of in-domain training data. This leads to significant data availability issues that inhibit the development of successful systems. To alleviate this problem, we propose a technique of data selection in the low-data regime that enables us to train with fewer labeled sentences, thus smaller labelling costs. We propose a submodularity-inspired data ranking function, the ratio-penalty marginal gain, for selecting data points to label based only on the information extracted from the textual embedding space. We show that the distances in the embedding space are a viable source of information that can be used for data selection. Our method outperforms two known active learning techniques and enables cost-efficient training of the NLU unit. Moreover, our proposed selection technique does not need the model to be retrained in between the selection steps, making it time efficient as well.

Goal-Oriented (GO) Dialogue Systems, colloquially known as goal oriented chatbots, help users achieve a predefined goal (e.g. book a movie ticket) within a closed domain. A first step is to understand the user's goal by using natural language understanding techniques. Once the goal is known, the bot must manage a dialogue to achieve that goal, which is conducted with respect to a learnt policy. The success of the dialogue system depends on the quality of the policy, which is in turn reliant on the availability of high-quality training data for the policy learning method, for instance Deep Reinforcement Learning. Due to the domain specificity, the amount of available data is typically too low to allow the training of good dialogue policies. In this paper we introduce a transfer learning method to mitigate the effects of the low in-domain data availability. Our transfer learning based approach improves the bot's success rate by 20% in relative terms for distant domains and we more than double it for close domains, compared to the model without transfer learning. Moreover, the transfer learning chatbots learn the policy up to 5 to 10 times faster. Finally, as the transfer learning approach is complementary to additional processing such as warm-starting, we show that their joint application gives the best outcomes.

Offloading traffic through opportunistic communications has been recently proposed as a way to relieve the current overload of cellular networks. Opportunistic communication can occur when mobile device users are (temporarily) in each other's proximity, such that the devices can establish a local peer-to-peer connection (e.g., via WLAN or Bluetooth). Since opportunistic communication is based on the spontaneous mobility of the participants, it is inherently unreliable. This poses a serious challenge to the design of any cellular offloading solutions, that must meet the applications' requirements. In this paper, we address this challenge from an optimization analysis perspective, in contrast to the existing heuristic solutions. We first model the dissemination of content (injected through the cellular interface) in an opportunistic network with heterogeneous node mobility. Then, based on this model, we derive the optimal content injection strategy, which minimizes the load of the cellular network while meeting the applications' constraints. Finally, we propose an adaptive algorithm based on control theory that implements this optimal strategy without requiring any data on the mobility patterns or the mobile nodes' contact rates. The proposed approach is extensively evaluated with both a heterogeneous mobility model as well as real-world contact traces, showing that it substantially outperforms previous approaches proposed in the literature.

Opportunistic or delay-tolerant networks (DTNs) may be used to enable communication in case of failure or lack of infrastructure (disaster, censorship, remote areas) and to complement existing wireless technologies (cellular, WiFi). Wireless peers communicate when in contact, forming an impromptu network, whose connectivity graph is highly dynamic and only partly connected. In this harsh environment, communication algorithms are mostly local search heuristics, choosing a solution among the locally available ones. Furthermore, they are routinely evaluated through simulations only, as they are hard to model analytically. Even when more insight is sought from models, these usually assume homogeneous node meeting rates, thereby ignoring the attested heterogeneity and nontrivial structure of human mobility. We propose DTN-Meteo, a new unified analytical model that maps an important class of DTN optimization problems over heterogeneous mobility/contact models into a Markov chain traversal over the relevant solution space. (Heterogeneous) meeting probabilities between different pairs of nodes dictate the chain's transition probabilities and determine neighboring solutions. Local optimization algorithms can accept/reject candidate transitions (deterministically or randomly), thus “modulating” the above transition probabilities. We apply our model to two example problems: routing and content placement. We predict the performance of state-of-the-art algorithms (SimBet, BubbleRap) in various real and synthetic mobility scenarios and show that surprising precision can be achieved against simulations, despite the complexity of the problems and diversity of settings. To our best knowledge, this is the first analytical work that can accurately predict performance for utility-based algorithms and heterogeneous node contact rates.

Opportunistic or Delay Tolerant Networks (DTNs) may be used to enable communication in case of failure or lack of infrastructure (disaster, censorship, remote areas) and to complement existing wireless technologies (cellular, WiFi). Wireless peers communicate when in contact, forming an impromptu network, whose connectivity graph is highly dynamic and only partly connected. In this harsh environment, communication algorithms are mostly greedy, choosing the best solution among the locally available ones. Furthermore, they are routinely evaluated through simulations only, as they are hard to model analytically. Even when more insight is sought from models, they usually assume homogeneous node meeting rates, thereby ignoring the attested heterogeneity and non-trivial structure of (human) mobility. We propose DTN-Meteo: a new unified analytical model that maps an important class of DTN optimization problems and the respective (greedy) algorithms into a Markov chain traversal over the relevant solution space. Fully heterogeneous node contact patterns and a range of algorithmic actions jointly (but separably) define transition probabilities. Thus, we provide closed-form solutions for crucial performance metrics under generic settings. While DTN-Meteo has wider applicability, in this paper, we focus on algorithms with explicitly controlled replication. We apply our model to two problems: routing and content placement. We predict the performance of state of the art algorithms (SimBet, BubbleRap) in various real and synthetic mobility scenarios and show that surprising precision can be achieved against simulations, despite the complexity of the problems and diversity of settings. To our best knowledge, this is the first analytical work that can accurately predict performance for utility-based algorithms and heterogeneous node contact rates.

Epidemic spreading is one of the most popular bio-inspired principles, which has made its way into computer networking. This principle naturally applies to Opportunistic or Delay Tolerant Networks (DTNs), where nodes probabilistically meet their neighbors thanks to mobility. Epidemic-based algorithms are often the only choice for DTN problems such as broadcast and unicast routing, distributed estimation etc. Existing analyses of epidemic spreading in various contexts only consider specific graph geometries (complete, random, regular etc) and/or homogeneous exponential node meeting rates. In addition, in wired networks, synchronous communication is usually assumed. In this paper, we relax these assumptions and provide a detailed analysis of epidemic spreading in DTNs with heterogeneous node meeting rates. We observe the special properties of a Markov model, describing the epidemic process and use them to derive bounds for the delay (expectation and distribution). We apply our analysis to epidemic-based DTN algorithms for routing and distributed estimation and validate the bounds against simulation results, using various real and synthetic mobility scenarios. Finally, we empirically show that the delay distribution is relatively concentrated, and that, depending on graph properties (communities, scale-freeness), the delay scales very well with network size.

Opportunistic or Delay Tolerant Networks (DTNs) are envisioned to complement existing wireless technologies (cellular, WiFi). Wireless peers communicate when in contact, forming a network "on the fly", whose connectivity graph is highly dynamic and only partly connected. Because of this stringent environment, solutions to common networking problems (routing, congestion control, etc.) in this context are greedy, choosing the best solution among the locally available ones. This shared trait motivates the common treatment of such greedy algorithms for DTNs and raises some interesting questions: Do they converge? How fast are they? Yet, existing models study individual solutions. Moreover, they often assume homogeneous node mobility. The study of real world traces reveals considerable heterogeneity and non-trivial structure in human mobility. While algorithms have been proposed, accounting for this heterogeneity, their analytical tractability is still a challenge. In this paper, we propose a new model for greedy DTN algorithms, supporting the full heterogeneity of node mobility. We provide closed form solutions for crucial performance metrics (delivery probability and delay) and prove necessary and sufficient conditions for algorithm convergence. For illustration, we apply our model to the content placement problem, a variant of distributed caching. We use real and synthetic mobility traces to validate our findings and examine the impact of mobility properties in depth.