Search Publications
Publications
2019 |
Aris Filos-Ratsikas, Yiannis Giannakopoulos ; Lazos, Philip The Pareto Frontier of Inefficiency in Mechanism Design Conference Forthcoming The 15th Conference on Web and Internet Economics (WINE 2019)., Springer, Forthcoming. @conference{Filos-Ratsikas2019b, title = {The Pareto Frontier of Inefficiency in Mechanism Design}, author = {Aris Filos-Ratsikas, Yiannis Giannakopoulos and Philip Lazos}, url = {https://arxiv.org/abs/1809.03454}, year = {2019}, date = {2019-12-10}, booktitle = {The 15th Conference on Web and Internet Economics (WINE 2019).}, publisher = {Springer}, abstract = {We study the trade-off between the Price of Anarchy (PoA) and the Price of Stability (PoS) in mechanism design, in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to the above metrics, and observe that two fundamental mechanisms, namely the First-Price (FP) and the Second-Price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely characterize the PoA/PoS Pareto frontier; we design a class of optimal mechanisms SPα that lie exactly on this frontier. In particular, these mechanisms range smoothly, with respect to parameter α≥1 across the frontier, between the First-Price (SP1) and Second-Price (SP∞) mechanisms. En route to these results, we also provide a definitive answer to an important question related to the scheduling problem, namely whether non-truthful mechanisms can provide better makespan guarantees in the equilibrium, compared to truthful ones. We answer this question in the negative, by proving that the Price of Anarchy of all scheduling mechanisms is at least n, where n is the number of machines.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } We study the trade-off between the Price of Anarchy (PoA) and the Price of Stability (PoS) in mechanism design, in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to the above metrics, and observe that two fundamental mechanisms, namely the First-Price (FP) and the Second-Price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely characterize the PoA/PoS Pareto frontier; we design a class of optimal mechanisms SPα that lie exactly on this frontier. In particular, these mechanisms range smoothly, with respect to parameter α≥1 across the frontier, between the First-Price (SP1) and Second-Price (SP∞) mechanisms. En route to these results, we also provide a definitive answer to an important question related to the scheduling problem, namely whether non-truthful mechanisms can provide better makespan guarantees in the equilibrium, compared to truthful ones. We answer this question in the negative, by proving that the Price of Anarchy of all scheduling mechanisms is at least n, where n is the number of machines. |
Antognini, Diego; Faltings, Boi Learning to Create Sentence Semantic Relation Graphs for Multi-Document Summarization Proceeding Hong Kong, China, 2019. @proceedings{antognini-faltings-2019-learning, title = {Learning to Create Sentence Semantic Relation Graphs for Multi-Document Summarization}, author = {Diego Antognini and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2019/11/D19-5404.pdf https://www.aclweb.org/anthology/D19-5404}, doi = {10.18653/v1/D19-5404}, year = {2019}, date = {2019-11-01}, booktitle = {Proceedings of the 2nd Workshop on New Frontiers in Summarization }, pages = {32--41}, address = {Hong Kong, China}, abstract = {Linking facts across documents is a challenging task, as the language used to express the same information in a sentence can vary significantly, which complicates the task of multi-document summarization. Consequently, existing approaches heavily rely on hand-crafted features, which are domain-dependent and hard to craft, or additional annotated data, which is costly to gather. To overcome these limitations, we present a novel method, which makes use of two types of sentence embeddings: universal embeddings, which are trained on a large unrelated corpus, and domain-specific embeddings, which are learned during training. To this end, we develop SemSentSum, a fully data-driven model able to leverage both types of sentence embeddings by building a sentence semantic relation graph. SemSentSum achieves competitive results on two types of summary, consisting of 665 bytes and 100 words. Unlike other state-of-the-art models, neither hand-crafted features nor additional annotated data are necessary, and the method is easily adaptable for other tasks. To our knowledge, we are the first to use multiple sentence embeddings for the task of multi-document summarization.}, keywords = {}, pubstate = {published}, tppubtype = {proceedings} } Linking facts across documents is a challenging task, as the language used to express the same information in a sentence can vary significantly, which complicates the task of multi-document summarization. Consequently, existing approaches heavily rely on hand-crafted features, which are domain-dependent and hard to craft, or additional annotated data, which is costly to gather. To overcome these limitations, we present a novel method, which makes use of two types of sentence embeddings: universal embeddings, which are trained on a large unrelated corpus, and domain-specific embeddings, which are learned during training. To this end, we develop SemSentSum, a fully data-driven model able to leverage both types of sentence embeddings by building a sentence semantic relation graph. SemSentSum achieves competitive results on two types of summary, consisting of 665 bytes and 100 words. Unlike other state-of-the-art models, neither hand-crafted features nor additional annotated data are necessary, and the method is easily adaptable for other tasks. To our knowledge, we are the first to use multiple sentence embeddings for the task of multi-document summarization. |
Aris Filos-Ratsikas, Evi Micha ; Voudouris, Alexandros A The Distortion of Distributed Voting Conference Forthcoming The 12th International Symposium on Algorithmic Game Theory, Springer, Forthcoming. @conference{Filos-Ratsikas2019c, title = {The Distortion of Distributed Voting}, author = {Aris Filos-Ratsikas, Evi Micha and Alexandros A. Voudouris}, url = {https://arxiv.org/pdf/1905.01882.pdf}, year = {2019}, date = {2019-09-30}, booktitle = {The 12th International Symposium on Algorithmic Game Theory}, publisher = {Springer}, abstract = {Voting can abstractly model any decision-making scenario and as such it has been extensively studied over the decades. Recently, the related literature has focused on quantifying the impact of utilizing only limited information in the voting process on the societal welfare for the outcome, by bounding the distortion of voting rules. Even though there has been significant progress towards this goal, all previous works have so far neglected the fact that in many scenarios (like presidential elections) voting is actually a distributed procedure. In this paper, we consider a setting in which the voters are partitioned into disjoint districts and vote locally therein to elect local winning alternatives using a voting rule; the final outcome is then chosen from the set of these alternatives. We prove tight bounds on the distortion of well-known voting rules for such distributed elections both from a worst-case perspective as well as from a best-case one. Our results indicate that the partition of voters into districts leads to considerably higher distortion, a phenomenon which we also experimentally showcase using real-world data.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } Voting can abstractly model any decision-making scenario and as such it has been extensively studied over the decades. Recently, the related literature has focused on quantifying the impact of utilizing only limited information in the voting process on the societal welfare for the outcome, by bounding the distortion of voting rules. Even though there has been significant progress towards this goal, all previous works have so far neglected the fact that in many scenarios (like presidential elections) voting is actually a distributed procedure. In this paper, we consider a setting in which the voters are partitioned into disjoint districts and vote locally therein to elect local winning alternatives using a voting rule; the final outcome is then chosen from the set of these alternatives. We prove tight bounds on the distortion of well-known voting rules for such distributed elections both from a worst-case perspective as well as from a best-case one. Our results indicate that the partition of voters into districts leads to considerably higher distortion, a phenomenon which we also experimentally showcase using real-world data. |
Panayiotis Danassis, Aris Filos-Ratsikas ; Faltings, Boi Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior Conference Forthcoming The 28th International Joint Conference on Artificial Intelligence (IJCAI '19), Forthcoming. @conference{Danassis2019, title = {Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior}, author = {Panayiotis Danassis, Aris Filos-Ratsikas and Boi Faltings}, url = {https://arxiv.org/pdf/1902.09359.pdf}, year = {2019}, date = {2019-08-15}, booktitle = {The 28th International Joint Conference on Artificial Intelligence (IJCAI '19)}, abstract = {We present a novel anytime heuristic (ALMA), inspired by the human principle of altruism, for solving the assignment problem. ALMA is decentralized, completely uncoupled, and requires no communication between the participants. We prove an upper bound on the convergence speed that is polynomial in the desired number of resources and competing agents per resource; crucially, in the realistic case where the aforementioned quantities are bounded independently of the total number of agents/resources, the convergence time remains constant as the total problem size increases. We have evaluated ALMA under three test cases: (i) an anti-coordination scenario where agents with similar preferences compete over the same set of actions, (ii) a resource allocation scenario in an urban environment, under a constant-time constraint, and finally, (iii) an on-line matching scenario using real passenger-taxi data. In all of the cases, ALMA was able to reach high social welfare, while being orders of magnitude faster than the centralized, optimal algorithm. The latter allows our algorithm to scale to realistic scenarios with hundreds of thousands of agents, e.g., vehicle coordination in urban environments.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } We present a novel anytime heuristic (ALMA), inspired by the human principle of altruism, for solving the assignment problem. ALMA is decentralized, completely uncoupled, and requires no communication between the participants. We prove an upper bound on the convergence speed that is polynomial in the desired number of resources and competing agents per resource; crucially, in the realistic case where the aforementioned quantities are bounded independently of the total number of agents/resources, the convergence time remains constant as the total problem size increases. We have evaluated ALMA under three test cases: (i) an anti-coordination scenario where agents with similar preferences compete over the same set of actions, (ii) a resource allocation scenario in an urban environment, under a constant-time constraint, and finally, (iii) an on-line matching scenario using real passenger-taxi data. In all of the cases, ALMA was able to reach high social welfare, while being orders of magnitude faster than the centralized, optimal algorithm. The latter allows our algorithm to scale to realistic scenarios with hundreds of thousands of agents, e.g., vehicle coordination in urban environments. |
Aleksei Triastcyn, Boi Faltings Federated Generative Privacy Workshop Forthcoming Proceedings of the IJCAI Workshop on Federated Machine Learning for User Privacy and Data Confidentiality (FML 2019), Forthcoming. @workshop{triastcyn2019federated, title = {Federated Generative Privacy}, author = {Aleksei Triastcyn, Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2019/07/fml_2019-1.pdf}, year = {2019}, date = {2019-08-12}, booktitle = {Proceedings of the IJCAI Workshop on Federated Machine Learning for User Privacy and Data Confidentiality (FML 2019)}, abstract = {In this paper, we propose FedGP, a framework for privacy-preserving data release in the federated learning setting. We use generative adversarial networks, generator components of which are trained by FedAvg algorithm, to draw privacy-preserving artificial data samples and empirically assess the risk of information disclosure. Our experiments show that FedGP is able to generate labelled data of high quality to successfully train and validate supervised models. Finally, we demonstrate that our approach significantly reduces vulnerability of such models to model inversion attacks.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {workshop} } In this paper, we propose FedGP, a framework for privacy-preserving data release in the federated learning setting. We use generative adversarial networks, generator components of which are trained by FedAvg algorithm, to draw privacy-preserving artificial data samples and empirically assess the risk of information disclosure. Our experiments show that FedGP is able to generate labelled data of high quality to successfully train and validate supervised models. Finally, we demonstrate that our approach significantly reduces vulnerability of such models to model inversion attacks. |
Adam Richardson, Aris Filos-Ratsikas ; Faltings, Boi Eliciting High-Quality Data via Influence for Linear Regression Workshop The 1st International Workshop on Federated Machine Learning for User Privacy and Data Confidentiality (FML 2019), 2019. @workshop{Richardson2019, title = {Eliciting High-Quality Data via Influence for Linear Regression}, author = {Adam Richardson, Aris Filos-Ratsikas and Boi Faltings}, url = {https://arxiv.org/pdf/1908.11598.pdf}, year = {2019}, date = {2019-08-12}, booktitle = {The 1st International Workshop on Federated Machine Learning for User Privacy and Data Confidentiality (FML 2019)}, abstract = {We consider a crowdsourcing data acquisition scenario, such as federated learning, where a Center collects data points from a set of rational Agents, with the aim of training a model. For linear regression models, we show how a payment structure can be designed to incentivize the agents to provide high-quality data as early as possible, based on a characterization of the influence that data points have on the loss function of the model. Our contributions can be summarized as follows: (a) we prove theoretically that this scheme ensures truthful data reporting as a game-theoretic equilibrium and further demonstrate its robustness against mixtures of truthful and heuristic data reports, (b) we design a procedure according to which the influence computation can be efficiently approximated and processed sequentially in batches over time, (c) we develop a theory that allows correcting the difference between the influence and the overall change in loss and (d) we evaluate our approach on real datasets, confirming our theoretical findings.}, keywords = {}, pubstate = {published}, tppubtype = {workshop} } We consider a crowdsourcing data acquisition scenario, such as federated learning, where a Center collects data points from a set of rational Agents, with the aim of training a model. For linear regression models, we show how a payment structure can be designed to incentivize the agents to provide high-quality data as early as possible, based on a characterization of the influence that data points have on the loss function of the model. Our contributions can be summarized as follows: (a) we prove theoretically that this scheme ensures truthful data reporting as a game-theoretic equilibrium and further demonstrate its robustness against mixtures of truthful and heuristic data reports, (b) we design a procedure according to which the influence computation can be efficiently approximated and processed sequentially in batches over time, (c) we develop a theory that allows correcting the difference between the influence and the overall change in loss and (d) we evaluate our approach on real datasets, confirming our theoretical findings. |
Goel, Naman; Faltings, Boi Personalized Peer Truth Serum for Eliciting Multi-Attribute Personal Data Conference 35th Conference on Uncertainty in Artificial Intelligence, Tel Aviv (UAI 2019), AUAI, 2019. @conference{Goel2019c, title = {Personalized Peer Truth Serum for Eliciting Multi-Attribute Personal Data}, author = {Naman Goel and Boi Faltings}, url = {https://lia.epfl.ch/~goel/upload/doc/papers/2019/goel_uai19.pdf}, year = {2019}, date = {2019-07-22}, booktitle = {35th Conference on Uncertainty in Artificial Intelligence, Tel Aviv (UAI 2019)}, publisher = {AUAI}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Balatsoukas-Stimming, Alexios; Filos-Ratsikas, Aris On the Computational Complexity of Blind Detection of Binary Linear Codes Conference Forthcoming 2019 IEEE International Symposium on Information Theory, IEEE, Forthcoming. @conference{Balatsoukas-Stimming2019, title = {On the Computational Complexity of Blind Detection of Binary Linear Codes}, author = {Alexios Balatsoukas-Stimming and Aris Filos-Ratsikas}, url = {https://arxiv.org/pdf/1806.01050.pdf}, year = {2019}, date = {2019-07-07}, booktitle = {2019 IEEE International Symposium on Information Theory}, publisher = {IEEE}, abstract = {In this work, we study the computational complexity of the Minimum Distance Code Detection problem. In this problem, we are given a set of noisy codeword observations and we wish to find a code in a set of linear codes C of a given dimension k, for which the sum of distances between the observations and the code is minimized. We prove that, for the practically relevant case when the set C only contains a fixed number of candidate linear codes, the detection problem is NP-hard and we identify a number of interesting open questions related to the code detection problem.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } In this work, we study the computational complexity of the Minimum Distance Code Detection problem. In this problem, we are given a set of noisy codeword observations and we wish to find a code in a set of linear codes C of a given dimension k, for which the sum of distances between the observations and the code is minimized. We prove that, for the practically relevant case when the set C only contains a fixed number of candidate linear codes, the detection problem is NP-hard and we identify a number of interesting open questions related to the code detection problem. |
Filos-Ratsikas, Aris; Goldberg, Paul W The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches Conference The 51st Annual ACM Symposium on the Theory of Computing (STOC 2019), ACM, 2019. @conference{Filos-Ratsikas2019, title = {The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches}, author = {Aris Filos-Ratsikas and Paul W. Goldberg}, url = {https://arxiv.org/abs/1805.12559}, year = {2019}, date = {2019-06-27}, booktitle = {The 51st Annual ACM Symposium on the Theory of Computing (STOC 2019)}, publisher = {ACM}, abstract = {We resolve the computational complexity of two problems known as NECKLACE-SPLITTING and DISCRETE HAM SANDWICH, showing that they are PPA-complete. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the necklace. We do this via a PPA-completeness result for an approximate version of the CONSENSUS-HALVING problem, strengthening our recent result that the problem is PPA-complete for inverse-exponential precision. At the heart of our construction is a smooth embedding of the high-dimensional Möbius strip in the CONSENSUS-HALVING problem. These results settle the status of PPA as a class that captures the complexity of "natural" problems whose definitions do not incorporate a circuit.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We resolve the computational complexity of two problems known as NECKLACE-SPLITTING and DISCRETE HAM SANDWICH, showing that they are PPA-complete. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the necklace. We do this via a PPA-completeness result for an approximate version of the CONSENSUS-HALVING problem, strengthening our recent result that the problem is PPA-complete for inverse-exponential precision. At the heart of our construction is a smooth embedding of the high-dimensional Möbius strip in the CONSENSUS-HALVING problem. These results settle the status of PPA as a class that captures the complexity of "natural" problems whose definitions do not incorporate a circuit. |
Ioannis Caragiannis Aris Filos-Ratsikas, Panagiotis Kanellopoulos ; Vaish, Rohit Stable Fractional Matchings Conference The 20th ACM conference on Economics and Computation (ACM EC '19), 2019. @conference{Caragiannis2019, title = {Stable Fractional Matchings}, author = {Ioannis Caragiannis, Aris Filos-Ratsikas, Panagiotis Kanellopoulos and Rohit Vaish}, url = {https://arxiv.org/pdf/1902.06698.pdf}, year = {2019}, date = {2019-06-24}, booktitle = {The 20th ACM conference on Economics and Computation (ACM EC '19)}, abstract = {We study a generalization of the classical stable matching problem that allows for cardinal preferences (as opposed to ordinal) and fractional matchings (as opposed to integral). After observing that, in this cardinal setting, stable fractional matchings can have much higher social welfare than stable integral ones, our goal is to understand the computational complexity of finding an optimal (i.e., welfare-maximizing) or nearly-optimal stable fractional matching. We present simple approximation algorithms for this problem with weak welfare guarantees and, rather unexpectedly, we furthermore show that achieving better approximations is hard. This computational hardness persists even for approximate stability. To the best of our knowledge, these are the first computational complexity results for stable fractional matchings. En route to these results, we provide a number of structural observations.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We study a generalization of the classical stable matching problem that allows for cardinal preferences (as opposed to ordinal) and fractional matchings (as opposed to integral). After observing that, in this cardinal setting, stable fractional matchings can have much higher social welfare than stable integral ones, our goal is to understand the computational complexity of finding an optimal (i.e., welfare-maximizing) or nearly-optimal stable fractional matching. We present simple approximation algorithms for this problem with weak welfare guarantees and, rather unexpectedly, we furthermore show that achieving better approximations is hard. This computational hardness persists even for approximate stability. To the best of our knowledge, these are the first computational complexity results for stable fractional matchings. En route to these results, we provide a number of structural observations. |
Mi, Fei; Huang, Minlie; Zhang, Jiyong; Faltings, Boi Meta-Learning for Low-resource Natural Language Generation in Task-oriented Dialogue Systems Conference Forthcoming The 28th International Joint Conference on Artificial Intelligence (IJCAI '19), Forthcoming. @conference{Mi2019, title = {Meta-Learning for Low-resource Natural Language Generation in Task-oriented Dialogue Systems}, author = {Fei Mi and Minlie Huang and Jiyong Zhang and Boi Faltings}, url = {https://arxiv.org/pdf/1905.05644.pdf}, year = {2019}, date = {2019-05-14}, booktitle = {The 28th International Joint Conference on Artificial Intelligence (IJCAI '19)}, abstract = {Natural language generation (NLG) is an essential component of task-oriented dialogue systems. Despite the recent success of neural approaches for NLG, they are typically developed for particular domains with rich annotated training examples. In this paper, we study NLG in a low-resource setting to generate sentences in new scenarios with handful training examples. We formulate the problem from a meta-learning perspective, and propose a generalized optimization-based approach (Meta-NLG) based on the well-recognized model-agnostic metalearning (MAML) algorithm. Meta-NLG defines a set of meta tasks, and directly incorporates the objective of adapting to new low-resource NLG tasks into the meta-learning optimization process. Extensive experiments are conducted on a large multidomain dataset (MultiWoz) with diverse linguistic variations. We show that Meta-NLG significantly outperforms other training procedures in various low-resource configurations. We analyze the results, and demonstrate that Meta-NLG adapts extremely fast and well to low-resource situations.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } Natural language generation (NLG) is an essential component of task-oriented dialogue systems. Despite the recent success of neural approaches for NLG, they are typically developed for particular domains with rich annotated training examples. In this paper, we study NLG in a low-resource setting to generate sentences in new scenarios with handful training examples. We formulate the problem from a meta-learning perspective, and propose a generalized optimization-based approach (Meta-NLG) based on the well-recognized model-agnostic metalearning (MAML) algorithm. Meta-NLG defines a set of meta tasks, and directly incorporates the objective of adapting to new low-resource NLG tasks into the meta-learning optimization process. Extensive experiments are conducted on a large multidomain dataset (MultiWoz) with diverse linguistic variations. We show that Meta-NLG significantly outperforms other training procedures in various low-resource configurations. We analyze the results, and demonstrate that Meta-NLG adapts extremely fast and well to low-resource situations. |
Panayiotis Danassis, Boi Faltings Courtesy As a Means to Coordinate Conference Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19 International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2019, ISBN: 978-1-4503-6309-9. @conference{danassisaamas2019, title = {Courtesy As a Means to Coordinate}, author = {Panayiotis Danassis, Boi Faltings}, url = {http://dl.acm.org/citation.cfm?id=3306127.3331754}, isbn = {978-1-4503-6309-9}, year = {2019}, date = {2019-05-13}, booktitle = {Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems}, pages = {665--673}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, address = {Richland, SC}, series = {AAMAS '19}, abstract = {We investigate the problem of multi-agent coordination under rationality constraints. Specifically, role allocation, task assignment, resource allocation, etc. Inspired by human behavior, we propose a framework (CA^3NONY) that enables fast convergence to efficient and fair allocations based on a simple convention of courtesy. We prove that following such convention induces a strategy which constitutes an epsilon-subgame-perfect equilibrium of the repeated allocation game with discounting. Simulation results highlight the effectiveness of CA^3NONY as compared to state-of-the-art bandit algorithms, since it achieves more than two orders of magnitude faster convergence, higher efficiency, fairness, and average payoff.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We investigate the problem of multi-agent coordination under rationality constraints. Specifically, role allocation, task assignment, resource allocation, etc. Inspired by human behavior, we propose a framework (CA^3NONY) that enables fast convergence to efficient and fair allocations based on a simple convention of courtesy. We prove that following such convention induces a strategy which constitutes an epsilon-subgame-perfect equilibrium of the repeated allocation game with discounting. Simulation results highlight the effectiveness of CA^3NONY as compared to state-of-the-art bandit algorithms, since it achieves more than two orders of magnitude faster convergence, higher efficiency, fairness, and average payoff. |
Aleksei Triastcyn, Boi Faltings Generating Artificial Data for Private Deep Learning Conference Proceedings of the PAL: Privacy-Enhancing Artificial Intelligence and Language Technologies, AAAI Spring Symposium Series, 2019. @conference{triastcyn2019generating, title = {Generating Artificial Data for Private Deep Learning}, author = {Aleksei Triastcyn, Boi Faltings}, url = {http://ceur-ws.org/Vol-2335/1st_PAL_paper_7.pdf}, year = {2019}, date = {2019-03-18}, booktitle = {Proceedings of the PAL: Privacy-Enhancing Artificial Intelligence and Language Technologies, AAAI Spring Symposium Series}, abstract = {In this paper, we propose generating artificial data that retain statistical properties of real data as the means of providing privacy for the original dataset. We use generative adversarial networks to draw privacy-preserving artificial data samples and derive an empirical method to assess the risk of information disclosure in a differential-privacy-like way. Our experiments show that we are able to generate labelled data of high quality and use it to successfully train and validate supervised models. Finally, we demonstrate that our approach significantly reduces vulnerability of such models to model inversion attacks.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } In this paper, we propose generating artificial data that retain statistical properties of real data as the means of providing privacy for the original dataset. We use generative adversarial networks to draw privacy-preserving artificial data samples and derive an empirical method to assess the risk of information disclosure in a differential-privacy-like way. Our experiments show that we are able to generate labelled data of high quality and use it to successfully train and validate supervised models. Finally, we demonstrate that our approach significantly reduces vulnerability of such models to model inversion attacks. |
Stephane Martin, Boi Faltings ; Schickel, Vincent Context-Tree Recommendation vs Matrix-Factorization: Algorithm Selection and Live Users Evaluation Conference Proceedings of the 31st AAAI Conference on Innovative Applications of AI, 31 , AAAI, 2019. @conference{Martin2019, title = {Context-Tree Recommendation vs Matrix-Factorization: Algorithm Selection and Live Users Evaluation}, author = {Stephane Martin, Boi Faltings and Vincent Schickel}, editor = { }, url = {https://lia.epfl.ch/wp-content/uploads/2018/11/paper_iaai-1.pdf}, year = {2019}, date = {2019-01-29}, booktitle = {Proceedings of the 31st AAAI Conference on Innovative Applications of AI}, volume = {31}, publisher = {AAAI}, abstract = {We describe the selection, implementation and online evaluation of two e-commerce recommender systems developed with our partner company, Prediggo. The first one is based on the novel method of Bayesian Variable-order Markov Modeling (BVMM). The second, SSAGD, is a novel variant of the Matrix-Factorization technique (MF), which is considered state-of-the-art in the recommender literature. We discuss the offline tests we carried out to select the best MF variant, and present the results of two A/B tests performed on live ecommerce websites after the deployment of the new algorithms. Comparing the new recommenders and Prediggo’s proprietary algorithm of Ontology Filtering, we show that the BVMM significantly outperforms the two others in terms of CTR and prediction speed, and leads to a strong increase in recommendation-mediated sales. Although MF exhibits reasonably good accuracy, the BVMM is still significantly more accurate and avoids the high memory requirements of MF. This scalability is essential for its application in online businesses.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We describe the selection, implementation and online evaluation of two e-commerce recommender systems developed with our partner company, Prediggo. The first one is based on the novel method of Bayesian Variable-order Markov Modeling (BVMM). The second, SSAGD, is a novel variant of the Matrix-Factorization technique (MF), which is considered state-of-the-art in the recommender literature. We discuss the offline tests we carried out to select the best MF variant, and present the results of two A/B tests performed on live ecommerce websites after the deployment of the new algorithms. Comparing the new recommenders and Prediggo’s proprietary algorithm of Ontology Filtering, we show that the BVMM significantly outperforms the two others in terms of CTR and prediction speed, and leads to a strong increase in recommendation-mediated sales. Although MF exhibits reasonably good accuracy, the BVMM is still significantly more accurate and avoids the high memory requirements of MF. This scalability is essential for its application in online businesses. |
Goel, Naman; Faltings, Boi Deep Bayesian Trust : A Dominant and Fair Incentive Mechanism for Crowd Conference 33rd AAAI Conference on Artificial Intelligence, 2019, AAAI, 2019. @conference{Goel2019, title = {Deep Bayesian Trust : A Dominant and Fair Incentive Mechanism for Crowd}, author = {Naman Goel and Boi Faltings}, url = {https://lia.epfl.ch/~goel/upload/doc/papers/2019/goel_aaai19.pdf}, year = {2019}, date = {2019-01-27}, booktitle = {33rd AAAI Conference on Artificial Intelligence, 2019}, publisher = {AAAI}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Goel, Naman; Faltings, Boi Crowdsourcing with Fairness, Diversity and Budget Constraints Conference Proceedings of the AAAI/ACM Conference on AI, Ethics and Society (AIES) 2019, AAAI/ACM, 2019. @conference{Goel2019b, title = {Crowdsourcing with Fairness, Diversity and Budget Constraints}, author = {Naman Goel and Boi Faltings}, url = {https://arxiv.org/abs/1810.13314}, year = {2019}, date = {2019-01-27}, booktitle = {Proceedings of the AAAI/ACM Conference on AI, Ethics and Society (AIES) 2019}, publisher = {AAAI/ACM}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Branzei, Simina; Filos-Ratsikas, Aris Walrasian Dynamics in Multi-unit Markets Conference The 33rd AAAI Conference on Artificial Intelligence (AAAI '19), AAAI AAAI Press, 2019. @conference{Branzei2019, title = {Walrasian Dynamics in Multi-unit Markets}, author = {Simina Branzei and Aris Filos-Ratsikas}, url = {https://arxiv.org/pdf/1712.08910.pdf}, year = {2019}, date = {2019-01-25}, booktitle = {The 33rd AAAI Conference on Artificial Intelligence (AAAI '19)}, publisher = {AAAI Press}, organization = {AAAI}, abstract = {In a multi-unit market, a seller brings multiple units of a good and tries to sell them to a set of buyers that have monetary endowments. While a Walrasian equilibrium does not always exist in this model, natural relaxations of the concept that retain its desirable fairness properties do exist. We study the dynamics of (Walrasian) envy-free pricing mechanisms in this environment, showing that for any such pricing mechanism, the best response dynamic starting from truth-telling converges to a pure Nash equilibrium with small loss in revenue and welfare. Moreover, we generalize these bounds to capture all the (reasonable) Nash equilibria for a large class of (monotone) pricing mechanisms. We also identify a natural mechanism, which selects the minimum Walrasian envy-free price, in which for n=2 buyers the best response dynamic con- verges from any starting profile. We conjecture convergence of the mechanism for any number of buyers and provide simulation results to support our conjecture.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } In a multi-unit market, a seller brings multiple units of a good and tries to sell them to a set of buyers that have monetary endowments. While a Walrasian equilibrium does not always exist in this model, natural relaxations of the concept that retain its desirable fairness properties do exist. We study the dynamics of (Walrasian) envy-free pricing mechanisms in this environment, showing that for any such pricing mechanism, the best response dynamic starting from truth-telling converges to a pure Nash equilibrium with small loss in revenue and welfare. Moreover, we generalize these bounds to capture all the (reasonable) Nash equilibria for a large class of (monotone) pricing mechanisms. We also identify a natural mechanism, which selects the minimum Walrasian envy-free price, in which for n=2 buyers the best response dynamic con- verges from any starting profile. We conjecture convergence of the mechanism for any number of buyers and provide simulation results to support our conjecture. |
2018 |
Chatzopoulos, Dimitris; Gujar, Sujit; Faltings, Boi; Hui, Pan Privacy Preserving and Cost Optimal Mobile Crowdsensing Using Smart Contracts on Blockchain Conference IEEE 15th International Conference on Mobile Ad Hoc and Sensor Systems (MASS), IEEE, 2018, ISSN: 2155-6814. @conference{Chatz2018, title = {Privacy Preserving and Cost Optimal Mobile Crowdsensing Using Smart Contracts on Blockchain}, author = {Dimitris Chatzopoulos and Sujit Gujar and Boi Faltings and Pan Hui}, url = {https://lia.epfl.ch/wp-content/uploads/2019/02/08567590.pdf}, doi = {10.1109/MASS.2018.00068}, issn = {2155-6814}, year = {2018}, date = {2018-10-09}, booktitle = {IEEE 15th International Conference on Mobile Ad Hoc and Sensor Systems (MASS)}, pages = {442-450}, publisher = {IEEE}, abstract = {The popularity and applicability of mobile crowdsensing applications are continuously increasing due to the widespread of mobile devices and their sensing and processing capabilities. However, we need to offer appropriate incentives to the mobile users who contribute their resources and preserve their privacy. Blockchain technologies enable semi-anonymous multi-party interactions and can be utilized in crowdsensing applications to maintain the privacy of the mobile users while ensuring first-rate crowdsensed data. In this work, we propose to use blockchain technologies and smart contracts to orchestrate the interactions between mobile crowdsensing providers and mobile users for the case of spatial crowdsensing, where mobile users need to be at specific locations to perform the tasks. Smart contracts, by operating as processes that are executed on the blockchain, are used to preserve users’ privacy and make payments. Furthermore, for the assignment of the crowdsensing tasks to the mobile users, we design a truthful, cost-optimal auction that minimizes the payments from the crowdsensing providers to the mobile users. Extensive experimental results show that the proposed privacy preserving auction outperforms state-of-the-art proposals regarding cost by ten times for high numbers of mobile users and tasks.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } The popularity and applicability of mobile crowdsensing applications are continuously increasing due to the widespread of mobile devices and their sensing and processing capabilities. However, we need to offer appropriate incentives to the mobile users who contribute their resources and preserve their privacy. Blockchain technologies enable semi-anonymous multi-party interactions and can be utilized in crowdsensing applications to maintain the privacy of the mobile users while ensuring first-rate crowdsensed data. In this work, we propose to use blockchain technologies and smart contracts to orchestrate the interactions between mobile crowdsensing providers and mobile users for the case of spatial crowdsensing, where mobile users need to be at specific locations to perform the tasks. Smart contracts, by operating as processes that are executed on the blockchain, are used to preserve users’ privacy and make payments. Furthermore, for the assignment of the crowdsensing tasks to the mobile users, we design a truthful, cost-optimal auction that minimizes the payments from the crowdsensing providers to the mobile users. Extensive experimental results show that the proposed privacy preserving auction outperforms state-of-the-art proposals regarding cost by ten times for high numbers of mobile users and tasks. |
Aris Filos-Ratsikas Soren Kristoffer Stiil Frederiksen, Paul. Goldberg W; Zhang, Jie Hardness Results for Consensus-Halving Conference 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), 117 , Leibniz International Proceedings in Informatics (LIPIcs) Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, ISBN: 978-3-95977-086-6. @conference{Filos-Ratsikas2018, title = {Hardness Results for Consensus-Halving}, author = {Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen, Paul. W Goldberg and Jie Zhang}, editor = {Igor Potapov, Paul Spirakis and James Worrell}, url = {https://arxiv.org/pdf/1609.05136.pdf}, doi = {10.4230/LIPIcs.MFCS.2018.24}, isbn = {978-3-95977-086-6}, year = {2018}, date = {2018-08-27}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, volume = {117}, pages = {24:1 - 24:16}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, abstract = {The Consensus-halving problem is the problem of dividing an object into two portions, such that each of n agents has equal valuation for the two portions. We study the epsilon-approximate version, which allows each agent to have an epsilon discrepancy on the values of the portions. It was recently proven in that the problem of computing an epsilon-approximate consensus-halving solution (for n agents and n cuts) is PPA-complete when epsilon is inverse-exponential. In this paper, we prove that when epsilon is constant, the problem is PPAD-hard and the problem remains PPAD-hard when we allow a constant number of additional cuts. Additionally, we prove that deciding whether a solution with n − 1 cuts exists for the problem is NP-hard.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } The Consensus-halving problem is the problem of dividing an object into two portions, such that each of n agents has equal valuation for the two portions. We study the epsilon-approximate version, which allows each agent to have an epsilon discrepancy on the values of the portions. It was recently proven in that the problem of computing an epsilon-approximate consensus-halving solution (for n agents and n cuts) is PPA-complete when epsilon is inverse-exponential. In this paper, we prove that when epsilon is constant, the problem is PPAD-hard and the problem remains PPAD-hard when we allow a constant number of additional cuts. Additionally, we prove that deciding whether a solution with n − 1 cuts exists for the problem is NP-hard. |
Stephane Martin, Boi Faltings ; Schickel, Vincent Enhancing Session-Based Recommendations through Sequential Modeling Conference 32nd ACM Conference on User Modeling, Adaptation and Personalization, 32 , ACM, 2018. @conference{Martin2018, title = {Enhancing Session-Based Recommendations through Sequential Modeling}, author = {Stephane Martin, Boi Faltings and Vincent Schickel}, url = {https://lia.epfl.ch/wp-content/uploads/2018/11/umap_extended_abstract_with_abstract-1.pdf}, year = {2018}, date = {2018-07-08}, booktitle = {32nd ACM Conference on User Modeling, Adaptation and Personalization}, volume = {32}, publisher = {ACM}, abstract = {Recommender systems typically determine the items they should recommend by learning models of user-preferences. Most often, those preferences are modeled as static and independent of context. In real life however, users consider items in sequence: TV series are watched episode by episode and accessories are chosen after the main appliance. Unfortunately, since sequences are more complex to model, they are often not taken into account. We developed an efficient sequence-modeling approach based on Bayesian Variable-order Markov Models and combined it with an existing content-based system, the Ontology Filtering. We tested this approach through live evaluations on two e-commerce sites. It dramatically increased performance, more than doubling the CTR and strongly increasing recommendation-mediated sales. These tests also confirm that the technique works efficiently and reliably in a production setting.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Recommender systems typically determine the items they should recommend by learning models of user-preferences. Most often, those preferences are modeled as static and independent of context. In real life however, users consider items in sequence: TV series are watched episode by episode and accessories are chosen after the main appliance. Unfortunately, since sequences are more complex to model, they are often not taken into account. We developed an efficient sequence-modeling approach based on Bayesian Variable-order Markov Models and combined it with an existing content-based system, the Ontology Filtering. We tested this approach through live evaluations on two e-commerce sites. It dramatically increased performance, more than doubling the CTR and strongly increasing recommendation-mediated sales. These tests also confirm that the technique works efficiently and reliably in a production setting. |
Goel, Naman; Yaghini, Mohammad; Faltings, Boi Non-Discriminatory Machine Learning through Convex Fairness Criteria Conference Thirty-Second AAAI Conference on Artificial Intelligence, 2018, AAAI, 2018. @conference{Goel2018, title = {Non-Discriminatory Machine Learning through Convex Fairness Criteria}, author = {Naman Goel and Mohammad Yaghini and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/publications/Goel_Naman_AAAI.pdf}, year = {2018}, date = {2018-02-07}, booktitle = {Thirty-Second AAAI Conference on Artificial Intelligence, 2018}, publisher = {AAAI}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Goran Radanovic, Boi Faltings Partial Truthfulness in Minimal Peer Prediction Mechanisms with Limited Knowledge Proceeding 32nd AAAI Conference on Artificial Intelligence 2018. @proceedings{radanovic2018a, title = {Partial Truthfulness in Minimal Peer Prediction Mechanisms with Limited Knowledge}, author = {Goran Radanovic, Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2018/01/Radanovic.pdf}, year = {2018}, date = {2018-02-04}, organization = {32nd AAAI Conference on Artificial Intelligence}, keywords = {}, pubstate = {published}, tppubtype = {proceedings} } |
Goran Radanovic Adish Singla, Andreas Krause Boi Faltings Information Gathering with Peers: Submodular Optimization with Peer-Prediction Constraints Inproceedings Proceedings of the 32nd Conference of the AAAI, 2018. @inproceedings{Radanovic2018b, title = {Information Gathering with Peers: Submodular Optimization with Peer-Prediction Constraints}, author = {Goran Radanovic, Adish Singla, Andreas Krause, Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2018/01/Radanovic-Singla.pdf }, year = {2018}, date = {2018-02-04}, booktitle = {Proceedings of the 32nd Conference of the AAAI}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
Kulev, Igor; Pu, Pearl; Faltings, Boi A Bayesian Approach to Intervention-Based Clustering Journal Article ACM Trans. Intell. Syst. Technol., 9 (4), pp. 44:1–44:23, 2018, ISSN: 2157-6904. @article{Kulev:2018:BAI:3183892.3156683, title = {A Bayesian Approach to Intervention-Based Clustering}, author = {Igor Kulev and Pearl Pu and Boi Faltings}, url = {http://doi.acm.org/10.1145/3156683 https://dl.acm.org/authorize?N677410}, doi = {10.1145/3156683}, issn = {2157-6904}, year = {2018}, date = {2018-01-01}, journal = {ACM Trans. Intell. Syst. Technol.}, volume = {9}, number = {4}, pages = {44:1--44:23}, publisher = {ACM}, address = {New York, NY, USA}, keywords = {}, pubstate = {published}, tppubtype = {article} } |
2017 |
Giannakopoulos, Athanasios; Antognini, Diego; Musat, Claudiu; Hossmann, Andreea; Baeriswyl, Michael Dataset Construction via Attention for Aspect Term Extraction with Distant Supervision Proceeding Forthcoming 7th ICDM Workshop on Sentiment Elicitation from Natural Text for Information Retrieval and Extraction (SENTIRE), Forthcoming. @proceedings{giannakopoulos2017b, title = {Dataset Construction via Attention for Aspect Term Extraction with Distant Supervision}, author = {Athanasios Giannakopoulos and Diego Antognini and Claudiu Musat and Andreea Hossmann and Michael Baeriswyl}, url = {https://lia.epfl.ch/wp-content/uploads/publications/Giannakopoulos2017b.pdf}, year = {2017}, date = {2017-11-18}, publisher = {7th ICDM Workshop on Sentiment Elicitation from Natural Text for Information Retrieval and Extraction (SENTIRE)}, abstract = {Aspect Term Extraction (ATE) detects opinionated aspect terms in sentences or text spans, with the end goal of performing aspect-based sentiment analysis. The small amount of available datasets for supervised ATE and the fact that they cover only a few domains raise the need for exploiting other data sources in new and creative ways. Publicly available review corpora contain a plethora of opinionated aspect terms and cover a larger domain spectrum. In this paper, we first propose a method for using such review corpora for creating a new dataset for ATE. Our method relies on an attention mechanism to select sentences that have a high likelihood of containing actual opinionated aspects. We thus improve the quality of the extracted aspects. We then use the constructed dataset to train a model and perform ATE with distant supervision. By evaluating on human annotated datasets, we prove that our method achieves a significantly improved performance over various unsupervised and supervised baselines. Finally, we prove that sentence selection matters when it comes to creating new datasets for ATE. Specifically, we show that, using a set of selected sentences leads to higher ATE performance compared to using the whole sentence set.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {proceedings} } Aspect Term Extraction (ATE) detects opinionated aspect terms in sentences or text spans, with the end goal of performing aspect-based sentiment analysis. The small amount of available datasets for supervised ATE and the fact that they cover only a few domains raise the need for exploiting other data sources in new and creative ways. Publicly available review corpora contain a plethora of opinionated aspect terms and cover a larger domain spectrum. In this paper, we first propose a method for using such review corpora for creating a new dataset for ATE. Our method relies on an attention mechanism to select sentences that have a high likelihood of containing actual opinionated aspects. We thus improve the quality of the extracted aspects. We then use the constructed dataset to train a model and perform ATE with distant supervision. By evaluating on human annotated datasets, we prove that our method achieves a significantly improved performance over various unsupervised and supervised baselines. Finally, we prove that sentence selection matters when it comes to creating new datasets for ATE. Specifically, we show that, using a set of selected sentences leads to higher ATE performance compared to using the whole sentence set. |