Novel Task Decomposition And Aggregation methods For Knowledge Discovery In Multi-agent systems

Open Access
Author:
Kurve, Aditya C
Graduate Program:
Electrical Engineering
Degree:
Doctor of Philosophy
Document Type:
Dissertation
Date of Defense:
October 25, 2013
Committee Members:
  • George Kesidis, Dissertation Advisor
  • Kultegin Aydin, Committee Chair
  • David Jonathan Miller, Committee Member
  • John F Doherty, Committee Member
  • Jason Ryder Morton, Committee Member
  • Christopher H Griffin, Committee Member
Keywords:
  • multi-agent systems
  • knowledge discovery
  • game theory
  • machine learning
  • Nash equilibrium
  • crowdsourcing
  • generative modeling
Abstract:
Multi-agent systems allow us to study and co-ordinate autonomous processes or agents for achieving macroscopic system-level goals. Agents are typically characterized by self-organizing behavior with heterogeneity in their individual goals, local information states or hypotheses. This thesis studies two domain specific problems in multi-agent systems: task decomposition and task aggregation. The former deals with suitably tasking the agents to achieve system level goals under the constraint that each agent has limited knowledge of the current state of the system. The latter studies the problem of combining the results of the agents’ tasks by taking into account the heterogeneity in agent-level parameters and their hypotheses or perceptions. The first part of this thesis deals with an agent-level decomposition of a task for optimizing clusters in super-peer based peer-to-peer(P2P) systems for efficient knowledge discovery via reduction in the average query resolution time. In this scenario, peers acting as independent agents are suitably incentivized in order to achieve this system-level objective. In particular, each peer chooses a super-peer using a game-theoretic cost function based on its limited “scope of view” and the communal goal is the minimization of average query resolution time. The resulting self-organizing system of peers attempts to “locally” solve a graph partitioning problem, thereby, leading to a guaranteed equilibrium state under the assumption of static network parameters, or at least, guaranteeing reduction in transitions without such an assumption. In the second part of this thesis, we study novel methods of aggregating agent-level decisions for a communal learning task in a crowdsourcing domain. Herein, agents are human annotators who expedite the annotation of large databases and make individual inferences on a subset of tasks assigned to them. In this case, the goal is to fuse or aggregate their responses in order to learn the ground truth values. We present two approaches to crowd aggregation in the case of multicategorical annotation tasks. Firstly, we present a stochastic generative model of a worker’s response to the annotation tasks that uses a novel comparative paradigm of the worker’s skill and the difficulty level of the task. Secondly, we propose a model-independent weighted plurality-based aggregation rule that uses novel weight energy constraints. Both these methods defeat the “tyranny of the masses”, i.e., they exploit the expertise of a minority subset of highly skilled workers in a crowd of mostly low-skilled workers. We also model both “naively” malicious as well as “strategic” adversarial agent behavior. The third and the final part of the thesis studies the detection of sybils in a peer-to-peer (P2P) system, which typically uses distributed reputation and referral mechanisms to enforce fair content distribution across peers. Each peer is limited in terms of the knowledge of the reputation scores of other peers and hence centralized graph-based search is not suitable. Under such constraints, we propose a distributed sparse-cut detection algorithm based on a novel hierarchical implementation of Karger’s min-cut algorithm on a trust (or reputation) graph along with a local “sparsity” metric that measures the confidence of presence of a sybil cluster.