Game Theory and Natural Language: Origin, Evolution and Processing
Marcello Pelillo, Rocco Tripodi
Slides and code of the tutorial
Motivation
The development of game theory in the early 1940’s by John von Neumann was a reaction against the then dominant view that problems in economic theory can be formulated using standard methods from optimization theory. Indeed, most real-world economic problems involve conflicting interactions among decision-making agents that cannot be adequately captured by a single (global) objective function. The main idea behind game theory is to shift the emphasis from optimality criteria to equilibrium conditions. Game theory provides a framework to model complex scenarios, with applications in economics and social science but also in different fields of information technology. With the recent development of algorithmic game theory, it has been used to solve problems in computer vision, pattern recognition, machine learning and natural language processing.
Game-theoretic frameworks have been used in different ways to study language origin and evolution. Furthermore, the so-called game metaphor has been used by philosophers and linguists to explain how language evolved and how it works. Ludwig Wittgenstein, for example, famously introduced the concept of a language game to explain the conventional nature of language, and put forward the idea of the spontaneous formation of a common language that gradually emerges from the interactions among the speakers within a population.
This concept opens the way to the interpretation of language as a complex adaptive system composed of linguistic units and their interactions, which gives rise to the emergence of structural properties. It is the core part of many computational models of language that are based on classical game theory and evolutionary game theory. With the former it is possible to model how speakers form a signaling system in which the ambiguity of the symbols is minimized; with the latter it is possible to model how speakers coordinate their linguistic choices according to the satisfaction that they have about the outcome of a communication act, converging to a common language. In the same vein, many other attempts have been proposed to explain how other characteristics of language follow similar dynamics.
Game theory, and in particular evolutionary game theory, thanks to their ability to model interactive situations and to integrate information from multiple sources, have also been used to solve specific problems in natural language processing and information retrieval, such as language generation, word sense disambiguation and document and text clustering.
The goal of this tutorial is to offer an introduction to the basic concepts of game theory and to show its main applications in the study of language, from different perspectives. We shall assume no pre-existing knowledge of game theory by the audience, thereby making the tutorial self-contained and understandable by a non-expert.
Outline
1. Introduction to game theory
a. What is a game?
b. Mixed strategies, expected payoffs, Nash equilibria
c. Evolutionary stable strategies, correlated equilibria
d. Complexity and algorithmic issues
Coffee Break
2. Origin and evolution of language
a. Origin of language
b. Language evolution
3. Applications
a. Natural language generation
b. Word sense disambiguation
c. Document clustering
About the presenters
Marcello Pelillo is Full Professor of Computer Science at Ca’ Foscari University, where he directs the European Centre for Living Technology (ECLT). He held visiting research positions at Yale University, McGill University, the University of Vienna, York University (UK), the University College London, and the National ICT Australia (NICTA). He has published more than 200 technical papers in refereed journals, handbooks, and conference proceedings in the areas of machine learning, pattern recognition and computer vision. He has initiated several conference series, including EMMCVPR in 1997, IWCV in 2008, SIMBAD in 2011, and he chairs the EMMCVPR and SIMBAD steering committees. He serves (has served) on the Editorial Boards of the journals IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), IET Computer Vision, Pattern Recognition, Brain Informatics, and he serves on the Advisory Board of the International Journal of Machine Learning and Cybernetics. He has served (serves) as Guest Editor for various special issues of IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), Pattern Recognition, Pattern Recognition Letters. He is (or has been) scientific coordinator of several research projects, including SIMBAD, an EU-FP7 project devoted to similarity-based pattern analysis and recognition whose activity is described in a recently published Springer book, and he has recently won an award from the Samsung Global Research Outreach (GRO) program. Prof. Pelillo is a Fellow of the IEEE and a Fellow of the IAPR. He has recently been appointed IEEE SMC Distinguished Lecturer.
Rocco Tripodi is Post-doctoral researcher at European Centre for Living Technology (Ca’ Foscari University of Venice), where he is working on learning models based on game theoretic principles. He completed his PhD in Computer Science at Ca' Foscari University in 2015 with a thesis titled "Evolutionary Game Theoretic Models for Natural Language Processing". He was Research Assistant and Adjunct Professor at Ca' Foscari University in 2010, where he worked on ontological semantics and taught Corpus Linguistics and Natural Language Processing for Online Applications. In 2015, he was visiting researcher at Staffordshire University (UK). His research interests are in the areas of machine learning and natural language processing. He is particularly interested in classification problems on networked data, from a semantic perspective and on the design, learning and evolution of linguistic communication systems. At present, he is working on game theoretic learning models, with applications to the analysis of multi-modal signals from interacting agents and on group dynamics.
