Department of Computer Science and Automation

Indian Institute of Science, Bangalore, India

Academic Projects

Scaling Approximate Inference over Graphs [in-progress]

Advisor: Wolfgang Gatterbauer, Carnegie Mellon Univ.
Abstract:   Multi-relational graphs are a convenient and intuitive representation of most real-world data and they can grow to the order of millions of nodes with billions of edges. Being able to run inference algorithms, like belief-propagation, over such large graphs with potentially several loops is a non-trivial task. Current scalable algorithms such as linearized belief propagation, exist only for pairwise markov random fields (MRFs).
We are currently exploring approximate inference algorithms for higher-order potential MRFs where energy functions are defined over clusters (or groups) of nodes. Specifically, I am looking into the trade-off between tensor based algorithms and conversion of higher-ordered potentials to their pairwise counterparts.

Budgeted Multi-armed Bandits with Dynamic Rewards [in-progress]

Advisor: Partha Talukdar, IISc
Abstract:   Multi-armed bandit (MAB) problem has been extensively studied for settings where reward distributions do not change over epochs. The vanila stochastic-MAB problem is best described by the example of gambler who plays one of K arms at each epoch, defined by an unknown reward distribution. Rewards are observed only for the chosen arm and that too after it is played. The gambler's objective is to maximize the cummulative rewards by exploring information about unseen arms and optimizing immediate rewards (exploitation). The budgeted variant of this stochastic-MAB has been studied and Knapsack based solutions are proposed.
In this work, we study the impact of dynamic (continuously changing) rewards in scenarios with faster budget depletion. I am currently looking into the most relaxed budgeted variant of adversarial bandits with solutions inspired from Exp3 and Sliding-window algorithms.

Allen AI Science Challenge

Advisor: Partha Talukdar, IISc
Our MALL lab participated in the Allen AI Science Challenge 2016 that aimed at building an automated answering system for 8th-grade multiple choice science questions. We stood 10th among 170 participating teams on global leaderboard. Try our demo!
Our model was a double-logistic ensemble over the below modules:

  • M1: Information retrieval
  • M2: Representation learning over question-answering trained DNNs
  • M3: Edge retrieval from Knowledge Graphs constructed by OpenIE over large unstructured web data
  • M4: Inference over constructed knowledge graphs for reasoning
  • M5: Pointwise Mutual Information statistics
  • M6: Textual Entailment
I was responsible for M4 and contributed to M3 and M1. For M4, we came up with "path-ranking-algorithm" (PRA) based classifiers for commonly occurring reason-type verbs such as cause, effect etc. We could learn interesting patterns such as photosynthesis causes life, heat effects temperature.
Description of the entire model can be found here.

KGEval: Estimating Knowledge Graph Accuracy

Advisor: Partha Talukdar, IISc
Abstract:   Automatic construction of large knowledge graphs (KG) by mining web-scale text datasets has received considerable attention over the last few years, resulting in several KGs such as NELL, Google Knowledge Vault, etc. These KGs consist of thousands of predicate-relations (e.g., isPerson, isMayorOf ) and millions of their instances called beliefs (e.g., (Bill de Blasio, isMayorOf, New York City)). Estimating accuracy of such automatically constructed KGs, especially under limited budget, is a challenging problem due to their size and diversity. This important problem has not been addressed in previous research we fill this gap and propose KGEval in this work.
KGEval is an instance of a novel crowdsourcing paradigm where dependencies among tasks posted to the crowd workers are exploited. We demonstrate that the objective optimized by KGEval is in fact NP-Hard and submodular, and hence allowing for the application of greedy algorithms with approximation guarantees. We demonstrate KGEval's effectiveness through extensive comparisons against multiple competitive baselines on real-world datasets. We have made all the code and data used in this work publicly available [Link].

Temporally extended actions in reinforcement learning

Advisor: Vani M, NITK
Abstract:   AI agents (robots) can learn much faster if they abstract lower level fine details of their environment and combine several primitive actions into one large abstracted Option. Given a state-space, humans can easily point out a few special states which carry more importance than other states, like hallway region in a building which connects several rooms.
In this work, we aim to identify a few bottleneck states within the state-space which should form termination states for Options framework. To identify important states, we block a certain state and gauge the impact on its neighboring states. We observed that blocking an important state would drastically reduce the cumulative rewards of its neighbors as when compared to blocking a non-important state. We further looked into developing approximation algorithm for computational efficiency and storing auxiliary data fields that helped in calculations without actually blocking the states.

Intelligent Tutoring System

Advisor: Carolyn P Rosé, IPTSE'13, CMU
Abstract:   Intelligent Tutoring Systems (ITS) which are socially aware and more human-like in their behavior, have always been at the heart of automated learning tools. Collborative platforms, where students are engaged in active learning process, need to model online conversations which can capture real-world semantics and identify appropriate intervention point. In this work, we study how academic-conversations can be modelled using state-transition diagrams and learn when/how an automated agent can intervene in collaborative learning conversations. We propose a two-pass method, filter pass and trigger pass. To identify deviations from central topic, the filter pass uses frequency of domain specific jargons and categorizes dialouges into attributes like Proposal, Question, Doubt, Comment, Clarification and Consensus/Agreement. Depending on the trend of Confusion versus Consensus in the conversation, the automated tutor steps in appropriately. We analyze the group conversation on High school Biology class dataset, Undergrad Thermodynamics class dataset and Graduate Chemistry dataset to understand problems such as rushed conclusion, responsive by asking elaborations, to only ask questions etc.

Course Work

Graduate Level courses @ IISc Bangalore

Undergraduate B.Tech curriculum @ NITK Surathkal:

AI and Algorithms:
  • Artificial Intelligence and Expert Systems
  • Distributed Algorithms
  • Design and Analysis of Algorithms
  • Advanced Data Structure and Algorithms
  • Data Structure and Algorithms
Mathematics Based Courses:
  • Linear Algebra
  • Discrete Mathematical Structures (Probability, Graph Theory, Combinatorics)
  • Concrete Mathematics
  • Number Theory and Cryptography
  • Engineering Mathematics I (Real Analysis and Multivariate Calculus)
  • Engineering Mathematics II
Computer Science Core Courses:
  • Thesis project - I and II
  • Theory of Computation
  • Operating Systems (+lab)
  • Database Systems (+lab)
  • System Programming
  • Computer Networks (+lab)
  • Advanced Topics in Networks and Distributed Computing
  • Computer Organisation and Architecture
  • Microprocessors and Interfacing (+lab)
  • Software Engineering / Object Technology
  • Computer Graphics