Being able to measure the success of online shopping interactions is crucial in order to evaluate and optimize the performance of e-commerce systems. It is especially challenging in the domain of voice shopping, typically supported by voice-based AI assistants. Unlike Web shopping, which offers a rich amount of behavioral signals such as clicks, in voice shopping a non-negligible amount of shopping interactions frequently ends without any immediate explicit or implicit user behavioral signal. Moreover, users may start their journey using a voice-enabled device, but complete it elsewhere, for example on their smartphone mobile app or a Web browser. We explore the challenge of measuring successful interactions in voice product search based on users’ behavior, and propose a medium-term reward metric named Extended ConVersion (ECVR). ECVR extends the notion of conversion beyond the usual purchase action, which serves as an undisputed measure of success in e-commerce. More specifically, it also captures purchase actions that occur at a later stage during a same shopping journey, and possibly on different channel than the one on which the interaction started. In this paper, we formally define the ECVR metric, describe multiple ways of evaluating the quality of a metric, and use these to explore different parameters for ECVR. After selecting the most appropriate parameters, we show that a ranking system optimized for ECVR, set up with these parameters, leads to improvements in long-term engagement and revenue, without compromising immediate conversion gains.

Implicit feedback from users behavior is a natural and scalable source for training and evaluating ranking models in human-interactive systems. However, inherent biases such as the position bias are key obstacles to its effective usage. This is further accentuated in cases of extreme bias, where behavioral feedback can be collected exclusively on the top ranked result. In fact, in such cases, state-of-art debiasing methods cannot be applied. A prominent use case of extreme position bias is the voice shopping medium, where only a small amount of information can be presented to the user during a single interaction, resulting in user behavioral signals that are almost exclusively limited to the top offer. There is no way to know how the user would have reacted to a different offer than the top one he was actually exposed to. Thus, any new ranker we wish to evaluate with respect to a behavioral metric, requires online experimentation. We propose a novel approach, based on anexternal estimator model, for accurately predicting offline the performance of a new ranker. The accuracy of our solution is proven theoretically, as well as demonstrated by a line of experiments. In these experiments, we focus on the use case of purchase prediction, and show that our estimator can accurately predict offline the purchase rate of different rankers over a segment of voice shopping traffic. Our prediction is validated online, as being compared to the actual performance obtained by each ranker when being exposed to users.

One emerging benefit of voice assistants is to facilitate product search experience, allowing users to express orally which products they seek, and taking actions on retrieved results such as adding them to their cart or sending the product details to their mobile phone for further examination. Looking at users' behavior in product search, supported by a digital voice assistant, we have observed an interesting phenomenon where users purchase or engage with search results that are objectively judged irrelevant to their queries.

Learning a ranking model in product search involves satisfying many requirements such as maximizing the relevance of retrieved products with respect to the user query, as well as maximizing the purchase likelihood of these products. Multi-Objective Ranking Optimization (MORO) is the task of learning a ranking model from training examples while optimizing multiple objectives simultaneously. Label aggregation is a popular solution approach for multi-objective optimization, which reduces the problem into a single objective optimization problem, by aggregating the multiple labels of the training examples, related to the different objectives, to a single label. In this work we explore several label aggregation methods for MORO in product search. We propose a novel stochastic label aggregation method which randomly selects a label per training example according to a given distribution over the labels. We provide a theoretical proof showing that stochastic label aggregation is superior to alternative aggregation approaches, in the sense that any optimal solution of the MORO problem can be generated by a proper parameter setting of the stochastic aggregation process. We experiment on three different datasets: two from the voice product search domain, and one publicly available dataset from the Web product search domain. We demonstrate empirically over these three datasets that MORO with stochastic label aggregation provides a family of ranking models that fully dominates the set of MORO models built using deterministic label aggregation.

Alexa is an intelligent personal assistant developed by Amazon, that can provide many services through voice interaction such as music playback, news, question-answering, and on-line shopping. The Alexa shopping research team in Amazon is a new emerging group of scientists who investigate revolutionary shopping experience through Alexa, while devising new search paradigms beyond traditional catalog search.

The constant growth of machine-generated mail, which today consists of more than 90% of non-spam mail traffic, is a major contributor toinformation overload in email, where users become overwhelmed with a flood of messages from commercial entities. A large part of this traffic is often junk mail that the user would prefer not to receive. Surprisingly, nearly 95% of this traffic is in fact solicited by the users themselves in the form of subscriptions to mailing services. These subscriptions are many times unintentional. Although unsubscription option from such services is enforced by commercial laws, it is hardly actually used by users. We perform a large scale study ofunsubscribable traffic, namely, messages that provide unsubscription option to users. We consider users behavior over such traffic in Yahoo Web mail service, and demonstrate a significant gap between users low interest in this traffic, and their lack of active behavior in decreasing its load. We conjecture that the cause of this gap is the lack of an efficient and easily accessible mechanism that would help users to unsubscribe. We validate our conjecture with an online large scale experiment, where we provide users with a novel mail feature for managing unsubscribable traffic, based on personalized recommendations. The experiment demonstrates the imminent need that exists for such a mechanism.

We introduce correlated randomized dependent rounding where, given multiple points y^1,...,y^n in some polytope P\subseteq [0,1]^k, the goal is to simultaneously round each y^i to some integral z^i in P while preserving both marginal values and expected distances between the points. In addition to being a natural question in its own right, the correlated randomized dependent rounding problem is motivated by multi-label classification applications that arise in machine learning, e.g., classification of web pages, semantic tagging of images, and functional genomics. The results of this work can be summarized as follows: (1) we present an algorithm for solving the correlated randomized dependent rounding problem in uniform matroids while losing only a factor of O(log{k}) in the distances (k is the size of the ground set); (2) we introduce a novel multi-label classification problem, the metric multi-labeling problem, which captures the above applications. We present a (true) O(log{k})-approximation for the general case of metric multi-labeling and a tight 2-approximation for the special case where there is no limit on the number of labels that can be assigned to an object.

Recent research studies on mail search have shown that the longer the query, the better the quality of results, yet a majority of mail queries remain very short and searchers struggle with formulating queries. A known mechanism to assist users in this task is query auto-completion, which has been highly successful in Web search, where it leverages huge logs of queries issued by hundreds of millions of users. This approach cannot be applied directly to mail search as personal query logs are small, mailboxes are not shared and other users' queries are not necessarily generalizable to all. We therefore propose here to leverage the mailbox content in order to generate suggestions, taking advantage of mail-specific features. We then compare this approach to a recent study that augments an individual user's mail search history with query logs from "similar users'', where the similarity is driven by demographics. Finally we show how combining both types of approaches allows for better suggestions quality but also increases the chance that the desired message be retrieved. We validate our claims via a manual qualitative evaluation and large scale quantitative experiments conducted on the query log of Yahoo Mail.

Web mail search is an emerging topic, which has not been the object of as many studies as traditional Web search. In particular, little is known about the characteristics of mail searchers and of the queries they issue. We study here the characteristics of Web mail searchers, and explore how demographic signals such as location, age, gender, and inferred income, influence their search behavior. We try to understand for instance, whether women exhibit different mail search patterns than men, or whether senior people formulate more precise queries than younger people. We compare our results, obtained from the analysis of a Yahoo Web mail search query log, to similar work conducted in Web and Twitter search. In addition, we demonstrate the value of the user's personal query log, as well as of the global query log and of the demographic signals, in a key search task: dynamic query auto-completion. We discuss how going beyond users' personal query logs (their search history) significantly improves the quality of suggestions, in spite of the fact that a user's mailbox is perceived as being highly personal. In particular, we note the striking value of demographic features for queries relating to companies/organizations, thus verifying our assumption that query completion benefits from leveraging queries issued by ``people like me". We believe that demographics and other such global features can be leveraged in other mail applications, and hope that this work is a first step in this direction.

Mail search has traditionally served time-ranked results, even if it has been shown that relevance ranking provides higher retrieval quality on average. Some Web mail services have recently started to provide relevance ranking options such as the relevance toggle in the search results page of Yahoo Mail, or the ``top results" section in Inbox by Gmail. Yet, ranking results by relevance is not accepted by all, either in mail search, or in in other domains such as social media, where it has even triggered some public outcry. Given the sensitivity of the topic, we propose here to investigate a mixed approach of promoting the most relevant results, to which we refer as ``heroes'', on top of time-ranked results. We argue that this approach represents a good compromise to mail searchers, supporting on one hand the time sorted paradigm they are familiar with, while being almost as effective as full relevance ranking view that Web mail users seem to be reluctant to adopt. We describe three hero-selection algorithms we have devised and the associated experiments we have conducted in Yahoo mail. We measure retrieval success via two metrics: MRR (Mean Reciprocal Rank) and [email protected], and verify agreement between these metrics and users' direct feedback. We demonstrate that supplementing time-sorted results with hero results leads to a higher MRR than the traditional time-sorted view. We additionally show that MRR better reflects users' perception of quality than [email protected] Finally, we report on online results following the successful launch of one of our hero-selection algorithms for all Yahoo enterprise mail users and a few million Yahoo Web mail users.

Several recent studies have presented different approaches for clustering and classifying machine-generated mail based on email headers. We propose to expand these approaches by considering email message bodies. We argue that our approach can help increase coverage and precision in several tasks, and is especially critical for mail extraction. We remind that mail extraction supports a variety of mail mining applications such as ad re-targeting, mail search, and mail summarization. We introduce new structural clustering methods that leverage the HTML structure that is common to messages generated by a same mass-sender script. We discuss how such structural clustering can be conducted at different levels of granularity, using either strict or flexible matching constraints, depending on the use cases.

With email traffic increasing, leading Web mail services have started to offer features that assist users in reading and processing their inboxes. One approach is to identify "important" messages, while a complementary one is to bundle messages, especially machine-generated ones, in pre-defined categories. We rather propose here to go back to the task at hand and consider what actions the users might conduct on received messages. We thoroughly studied, in a privacy-preserving manner, the actions of a large number of users in Yahoo mail, and found out that the most frequent actions are typically read, reply, delete and a sub-type of delete, delete-without-read. We devised a learning framework for predicting these four actions, for users with various levels of activity per action. Our framework leverages both vertical learning for personalization and horizontal learning for regularization purposes. In order to verify the quality of our predictions, we conducted a large-scale experiment involving users who had previously agreed to participate in such research studies. Our results show that, for recall values of 90%, we can predict important actions such as read or reply at precision levels up to 40% for active users, which we consider pretty encouraging for an assistance task. For less active users, we show that our regularization achieves an increase in AUC of close to 50%. To the best of our knowledge, our work is the first to provide a unified framework of this scale for predicting multiple actions on Web email, which hopefully provides a new ground for inventing new user experiences to help users process their inboxes.

We study the problem of k-anonymization of mail messages in the realistic scenario of auditing mail traffic in a major commercial Web mail service. Mail auditing is necessary in various Web mail debugging and quality assurance activities, such as anti-spam or the qualitative evaluation of novel mail features. It is conducted by trained professionals, often referred to as "auditors", who are shown messages that could expose personally identifiable information. We address here the challenge of k-anonymizing such messages, focusing on machine generated mail messages that represent more than 90% of today's mail traffic. We introduce a novel message signature Mail-Hash, specifically tailored to identifying structurally-similar messages, which allows us to put such messages in a same equivalence class. We then define a process that generates, for each class, masked mail samples that can be shown to auditors, while guaranteeing the k-anonymity of users. The productivity of auditors is measured by the amount of non-hidden mail content they can see every day, while considering normal working conditions, which set a limit to the number of mail samples they can review. In addition, we consider k-anonymity over time since, by definition of k-anonymity, every new release places additional constraints on the assignment of samples. We describe in details the results we obtained over actual Yahoo mail traffic, and thus demonstrate that our methods are feasible at Web mail scale. Given the constantly growing concern of users over their email being scanned by others, we argue that it is critical to devise such algorithms that guarantee k-anonymity, and implement associated processes in order to restore the trust of mail users.

With Web mail services offering larger and larger storage capacity, most users do not feel the need to systematically delete messages anymore and inboxes keep growing. It is quite surprising that in spite of the huge progress of relevance ranking in Web Search, mail search results are still typically ranked by date. This can probably be explained by the fact that users demand perfect recall in order to "re-find" a previously seen message, and would not trust relevance ranking. Yet mail search is still considered a difficult and frustrating task, especially when trying to locate older messages. In this paper, we study the current search traffic of Yahoo mail, a major Web commercial mail service, and discuss the limitations of ranking search results by date. We argue that this sort-by-date paradigm needs to be revisited in order to account for the specific structure and nature of mail messages, as well as the high-recall needs of users. We describe a two-phase ranking approach, in which the first phase is geared towards maximizing recall and the second phase follows a learning-to-rank approach that considers a rich set of mail-specific features to maintain precision. We present our results obtained on real mail search query traffic, for three different datasets, via manual as well as automatic evaluation. We demonstrate that the default time-driven ranking can be significantly improved in terms of both recall and precision, by taking into consideration time recency and textual similarity to the query, as well as mail-specific signals such as users' actions.

Network Function Virtualization (NFV) is a new networking paradigm where network functions are executed on commodity servers located in small cloud nodes distributed across the network, and where software defined mechanisms are used to control the network flows. This paradigm is a major turning point in the evolution of networking, as it introduces high expectations for enhanced economical network services, as well as major technical challenges. In this paper, we address one of the main technical challenges in this domain: the actual placement of the virtual functions within the physical network. This placement has a critical impact on the performance of the network, as well as on its reliability and operation cost. We perform a thorough study of the NFV location problem, show that it introduces a new type of optimization problems, and provide near optimal approximation algorithms guaranteeing a placement with theoretically proven performance. The performance of the solution is evaluated with respect to two measures: the distance cost between the clients and the virtual functions by which they are served, as well as the setup costs of these functions. We provide bi-criteria solutions reaching constant approximation factors with respect to the overall performance, and adhering to the capacity constraints of the networking infrastructure by a constant factor as well. Finally, using extensive simulations, we show that the proposed algorithms perform well in many realistic scenarios.

Software Defined Networks (SDNs) are becoming the leading technology behind many traffic engineering solutions, both for backbone and data-center networks, since it allows a central controller to globally plan the path of the flows according to the operator's objective. Nevertheless, networking devices' forwarding table is a limited and expensive resource (e.g., TCAM-based switches) which should thus be considered upon configuring the network. In this paper, we concentrate on satisfying global network objectives, such as maximum flow, in environments where the size of the forwarding table in network devices is limited. We formulate this problem as an (NP-hard) optimization problem and present approximation algorithms for it. We show through extensive simulations that practical use of our algorithms (both in Data Center and backbone scenarios) result in a significant reduction (factor 3) in forwarding table size, while having a small effect on the global objective (maximum flow).

The recent growing popularity of cloud-based solutions and the variety of new applications present new challenges for cloud management and resource utilization. In this paper we concentrate on the networking aspect and consider the placement problem of virtual machines (VMs) of applications with intense bandwidth requirements. Optimizing the available network bandwidth is far more complex than optimizing resources like memory or CPU, since every network link may be used by many physical hosts and thus by the VMs residing in these hosts. We focus on maximizing the benefit from the overall communication sent by the VMs to a single designated point in the data center (called the root). This is the typical case when considering a storage area network of applications with intense storage requirements. We formulate a bandwidth-constrained VM placement optimization problem that models this setting. This problem is NP hard, and we present a polynomial-time constant approximation algorithm for its most general version, in which hosts are connected to the root by a general network graph. For more practical cases, in which the network topology is a tree and the revenue is a simple function of the allocated bandwidth, we present improved approximation algorithms that are more efficient in terms of running time. We evaluate the expected performance of our proposed algorithms through a simulation study over traces from a real production data center, providing strong indications to the superiority of our proposed solutions.

Publish/subscribe based communication systems have become very popular in recent years. Such systems are becoming larger and more complex, and thus require a smart management framework. An important challenge in this context is to efficiently disseminate the data flows sent from the publishers to the subscribers. To this aim, multicast dissemination is often used, requiring a smart mapping of data flows to multicast groups. Most existing publish/subscribe systems use static configuration and thus do not efficiently handle dynamic changes in the publish/subscribe system. In this work, we present a self-managed and self-optimized publish/subscribe system that efficiently adapts to changes in run time. A key element in the solution is a smart mapping algorithm that computes efficient routes for the data flows based on the current conditions in the system. The mapping algorithm takes into account various costs and constraints that are associated with the transition from one mapping to another during run time. The solution we present maintains the publish/subscribe system optimized while at the same time ensuring the stability of the system. We complement our work with a comprehensive simulation study in which we evaluate the suggested solution. The results clearly demonstrate the advantages of a dynamic self-optimized system over a static system.

Clustering, the partitioning of objects with respect to a similarity measure, has been extensively studied as a global optimization problem. We investigate clustering from a game theoretic approach, and consider the class of hedonic clustering games. Here, a self organized clustering is obtained via decisions made by independent players, corresponding to the elements clustered. Being a hedonic setting, the utility of each player is determined by the identity of the other members of her cluster. This class of games seems to be quite robust, as it fits with rather different, yet commonly used, clustering criteria. Specifically, we investigate hedonic clustering games in two different models: fixed clustering, which subdivides into k-median and k-center, and correlation clustering. We provide a thorough and non-trivial analysis of these games, characterizing Nash equilibria, and proving upper and lower bounds on the price of anarchy and price of stability. For fixed clustering we focus on the existence of a Nash equilibrium, as it is a rather non-trivial issue in this setting. We study it both for general metrics and special cases, such as line and tree metrics. In the correlation clustering model, we study both minimization and maximization variants, and provide almost tight bounds on both price of anarchy and price of stability.

A major problem in wireless networks is coping with limited resources, such as bandwidth and energy. These issues become a major algorithmic challenge in view of the dynamic nature of the wireless domain. We consider in this paper the single-transmitter power assignment problem under time-varying channels, with the objective of maximizing the data throughput. It is assumed that the transmitter has a limited power budget, to be sequentially divided during the lifetime of the battery. We deviate from the classic work in this area, which leads to explicit “water-filling” solutions, by considering a realistic scenario where the channel state quality changes arbitrarily from one transmission to the other. The problem is accordingly tackled within the framework of competitive analysis, which allows for worst-case performance guarantees in setups with arbitrarily varying channel conditions. We address both a “discrete” case, where the transmitter can transmit only at a fixed power level, and a “continuous” case, where the transmitter can choose any power level out of a bounded interval. For both cases, we propose online power-allocation algorithms with proven worst-case performance bounds. In addition, we establish lower bounds on the worst-case performance of any online algorithm and show that our proposed algorithms are optimal.

We consider the power control problem in a time-slotted wireless channel, shared by a finite number of mobiles that transmit to a common base station. The channel between each mobile and the base station is time varying, and the system objective is to maximize the overall data throughput. It is assumed that each transmitter has a limited power budget, to be sequentially divided during the lifetime of the battery. We deviate from the classic work in this area, by considering a realistic scenario where the channel quality of each mobile changes arbitrarily from one transmission to the other. Assuming first that each mobile is aware of the channel quality of all other mobiles, we propose an online power-allocation algorithm, and prove its optimality under mild assumptions. We then indicate how to implement the algorithm when only local state information is available, requiring minimal communication overhead. Notably, the competitive ratio of our algorithm (nearly) matches the one we previously obtained for the (much simpler) single-transmitter case [BLMNO09], albeit requiring significantly different algorithmic solutions.

A major problem in wireless networks is coping with limited resources, such as bandwidth and energy. These issues become a major algorithmic challenge in view of the dynamic nature of the wireless domain. We consider in this paper the single-transmitter power assignment problem under time-varying channels, with the objective of maximizing the data throughput. It is assumed that the transmitter has a limited power budget, to be sequentially divided during the lifetime of the battery. We deviate from the classic work in this area, which leads to explicit "water-filling" solutions, by considering a realistic scenario where the channel state quality changes arbitrarily from one transmission to the other. The problem is accordingly tackled within the framework of competitive analysis, which allows for worst case performance guarantees in setups with arbitrarily varying channel conditions. We address both a "discrete" case, where the transmitter can transmit only at a fixed power level, and a "continuous" case, where the transmitter can choose any power level out of a bounded interval. For both cases, we propose online power-allocation algorithms with proven worst-case performance bounds. In addition, we establish lower bounds on the worst-case performance of any online algorithm, and show that our proposed algorithms are optimal.

Routing traffic so as to maximize the lifetime of a transmission is a major problem in wireless networks. We address a two-way multicast problem, where a root wishes to transmit data to a subset of nodes, as well as receive data from them. In addition, we consider the anycast problem, wherethere is a subset of nodes that wish to communicate with each other. We consider both a per-hop multi-recipients environment, where over each hop, the transmission is received by all nodes within range, and a per-hop single-recipient environment, where over each hop the transmission is received by a single recipient. For both environments, our work consists of two parts. In the first part we focus on system optimization perspectives of the lifetime maximization problem, while in the second part we investigate the game-theoretic perspective of the respective problems.We first note that, for the per-hop multi-recipients environment, an optimal solution can be computed in polynomial time. Nevertheless, for the per-hop single-recipient environment, we observe that computing an optimal solution is NP-hard. Accordingly, we provide a polynomial time algorithm that finds a 2-approximate solution for the case of uniform transmission power levels. For different transmission power levels, we provide an O(log2n) approximation algorithm for the general problem, and an O(log n) approximation algorithm for the special case where the set of terminals equals the set of all nodes, whose size equals n.For each environment, we consider the corresponding noncooperative game scenario, and prove that by following the natural game course users converge to a Nash equilibrium. For the per-hop multi-recipients environment, we show that if the players join the game sequentially, the Nash equilibrium is (networkwide) optimal. For the per-hop single-recipient environment, we show that the price of anarchy is unbounded. On the other hand, we show that for both environments, the price of stability, where the best Nash equilibrium is considered, is 1; hence, optimal (networkwide) performance can be achieved if the initial configuration can be imposed on the players.

We consider a multicast game with selfish non- cooperative players. There is a special source node and each player is interested in connecting to the source by making a routing decision that minimizes its payment. The mutual influence of the players is determined by a cost sharing mechanism, which in our case evenly splits the cost of an edge among the players using it. We consider two different models: an integral model, where each player connects to the source by choosing a single path, and a fractional model, where a player is allowed to split the flow it receives from the source between several paths. In both models we explore the overhead incurred in network cost due to the selfish behavior of the users, as well as the computational complexity of finding a Nash equilibrium. The existence of a Nash equilibrium for the integral model was previously established by the means of a potential function. We prove that finding a Nash equilibrium that minimizes the potential function is NP-hard. We focus on the price of anarchy of a Nash equilibrium resulting from the best-response dynamics of a game course, where the players join the game sequentially. For a game with in players, we establish an upper bound of O(radicnlog2n) on the price of anarchy, and a lower bound of Omega(log n/log log n). For the fractional model, we prove the existence of a Nash equilibrium via a potential function and give a polynomial time algorithm for computing an equilibrium that minimizes the potential function. Finally, we consider a weighted extension of the multicast game, and prove that in the fractional model, the game always has a Nash equilibrium.

We consider a multicast game with selfish non-cooperative players. There is a special source node and each player is interested in connecting to the source by making a routing decision that minimizes its payment. The mutual influence of the players is determined by a cost sharing mechanism, which in our case evenly splits the cost of an edge among the players using it. We consider two different models: an integral model, where each player connects to the source by choosing a single path, and a fractional model, where a player is allowed to split the flow it receives from the source between several paths. In both models we explore the overhead incurred in network cost due to the selfish behavior of the users, as well as the computational complexity of finding a Nash equilibrium.The existence of a Nash equilibrium for the integral model was previously established by the means of a potential function. We prove that finding a Nash equilibrium that minimizes the potential function is NP-hard. We focus on the price of anarchy of a Nash equilibrium resulting from the best-response dynamics of a game course, where the players join the game sequentially. For a game with n players, we establish an upper bound of O(√n log2n) on the price of anarchy, and a lower bound of Ω(log n/ log log n). For the fractional model, we prove the existence of a Nash equilibrium via a potential function and give a polynomial time algorithm for computing an equilibrium that minimizes the potential function. Finally, we consider a weighted extension of the multicast game, and prove that in the fractional model, the game always has a Nash equilibrium.