Question Answering (QA) is a great way to test the natural language understanding of an artificial intelligence system. The recent advances in model architectures and large-scale datasets have led to the development of neural QA systems that surpass human performance on question answering. The reason behind the success of neural systems lies in their ability to directly learn features to extract answers from data. In contrast, symbolic systems encounter notable difficulties in scaling due to their restricted applicability to semi-structured or symbol-grounded data. Despite their reliance on structured data, symbolic systems demonstrate proficiency in executing deterministic operations and performing reasoning tasks. Conversely, neural systems exhibit limitations in reasoning, as they are (1) inconsistent, (2) unable to compose simple facts and perform complex reasoning, and (3) sensitive to changes in domain distribution. In this dissertation, we present a range of data intervention schemes that facilitate in building consistent, decomposable, and generalizable neural QA systems. First, we show that purely neural systems are inconsistent and biased because most training and data collection procedures for neural systems make the independence assumptions and we explore two ways to address this problem. Second, we introduce a compositional QA dataset and show that neural QA methods lack decomposability. We propose a method to break down the complex questions using generated data into simpler, more manageable sub-questions to improve few-shot performance. Finally, we dissect the complex interactions among questions, answers, and documents learned by a neural QA system to assess their effectiveness towards generalization under a range of different data distributions through a series of generated data interventions and dynamic task sampling. Overall, we demonstrate how data interventions can be utilized to induce characteristics of symbolic systems into neural QA systems.

Due to its strong predictive power, machine learning (ML) has increasingly shown considerable potential to disrupt a wide range of critical domains, such as medicine, healthcare, and finance. Along with this success, ML models have become more complex and parameter intensive. For instance, large language models (LLMs) pre-trained on massive amounts of internet text have become a default choice for many prediction problems. As a result, models are increasingly difficult to understand, establish trust in, and have become more data-intensive. To address the opaqueness of ML models, researchers have proposed explanation methods that help users understand why their models make predictions. Still, explanation methods often do not faithfully explain model predictions, and domain experts struggle to use them. As a result, it is important to understand how ML explanations fail, improve their robustness, and enhance their usability. Moreover, due to the increased data-intensiveness of many ML problems and the desire for widespread integration, there is a need for methods that achieve strong predictive performance more easily and cost-effectively.

In this dissertation, we address these problems in two main research thrusts: 1) We evaluate the shortcomings of explanation methods by developing adversarial attacks on such techniques, which provide insights into how these methods fall short. We propose novel explanation methods that are more robust to common issues these explanations suffer. 2) We develop language-based methods of interacting with explanations, enabling anyone to understand machine learning models. We extend these findings to a more general predictive setting where we improve model performance using natural language instructions to solve critical prediction tasks with only minimal training data.

First, we examine the limitations of explanation methods through the lens of adversarial attacks. We introduce adversarial attacks on two commonly used types of explanations: local post hoc explanations, and counterfactual explanations. Our methods reveal that it is possible to design ML models for whom explanations behave unfaithfully, demonstrating that they are not robust. We additionally analyze other limiting factors of explanations, such as their instability and inconsistency, and demonstrate how improved uncertainty quantification can alleviate these issues. To this end, we introduce two new explanation methods, including uncertainty estimates for explanations, BayesLIME and BayesSHAP, that overcome many of these robustness issues.

Second, we analyze the usability of current explanation methods and find that many subject matter experts, like healthcare workers or policy researchers, struggle to use them. To overcome these issues, we introduce TalkToModel: an interactive, natural language dialogue system for explaining ML models. Our real-world evaluations suggest TalkToModel dramatically helps improve the usability of ML explanations. Based on the finding that natural language is a highly useful interface between models and humans, we evaluate how well current LLMs utilize natural language instructions for solving tabular prediction tasks from instructions and introduce a benchmark of prediction tasks, TABLET, to this end. Taken together, these works offer new techniques for making ML models more accessible to end users through natural language.

In the past several years, the field of natural language processing has undergone a paradigm shift driven by a singular piece of technology: large language models. Large language models have emerged as fundamental tools in our field, significantly advancing the state of the art and enabling breakthroughs across a wide range of tasks. The capabilities of large language models are an emergent function of scale - they are trained on terabytes of text data scraped from all corners of the web. By virtue of this training, large language models capture a rough notion of the factual state of the world in their weights. Understanding how language models represent these facts and how these representations are used to generate text is vital given their increasing deployment in the world. In this dissertation, our goal is to provide tooling and technologies to probe and evaluate how language models leverage and generate facts and correct the cases where language models produce inaccurate factual statements.

This dissertation is split into three distinct parts. The first is concerned with evaluating the generations of large language models for correctness. Here, we develop metrics (i.e., LERC) for evaluating the outputs of language models. The second is concerned with characterizing how language models leverage different sources of facts and use them during generation. We develop benchmarks (i.e., AmbER and knowledge conflicts) for assessing the tendencies of language models to over-rely on information stored in their weights and connect this to their propensity to generate factually inaccurate statements. Our final part is concerned with correcting inaccuracies in language model generations. We develop methodologies for training models for correcting factual inaccuracies that language models generate (i.e., RARR and PURR) as well as concretely establish the task of editing for factuality by introducing new evaluation benchmarks and metrics.

In total, the work presented in this dissertation provides a concrete way to evaluate the facts language models generate, characterize how language models leverage different sources of facts and use them during generation, and correct the facts language models generate.

Linear algebra is the foundation of machine learning, especially for handling big data. We want to extract useful information that can represent the behavior of the data. For data with underlying known structures, it is straightforward to apply algorithms that maintain that structure. For instance, the generalized singular value decomposition, tensor decomposition, is the crux of model estimation for tensors. However, not all data has a trivial structure. Multi-modality data that contains information from different sources can be complex and hard to extract the structure. A data-independent randomized algorithm, such as sketching, is the solution for this case. Under both scenarios, the information extraction process may be statistically challenging as the problems are non-convex optimization problems. More importantly, the large size and the high-dimensionality of the data have been significant obstacles in discovering hidden variables and summarizing them. Thus, how to improve high-dimensional data computation efficiency is vitally important.

This thesis contains the theoretical analysis for learning the underlying information from high-dimensional structured or non-structured data via tensor operations such as tensor decomposition and tensor sketching. It is easy to consider tensors as multi-dimensional vectors or matrices and apply vector/matrix-based algorithms to find the solution. However, these methods omit multi-dimensionality of the data and can be computational inefficient than considering the tensor as a whole. We show the superiority of our approximation algorithms over these methods from computation and memory efficiency point of views. This thesis also discusses optimizing tensor operation computations from the high-performance computing aspect. Conventional methods treat tensors as flattened matrices or vectors. Operations between tensors may require lots of permutations and reshapes. We propose new tensor algebra computation routines that avoid the prepossessing as much as possible.

Hierarchical structures arise in many real world applications and domains. For example, in social networks people’s relationships and the groups to which they belong form a hierarchy. In natural language and computer programs, parse trees (which have a hierarchical structure) are used to represent the compositionality of expressions. These hierarchies strongly affect the statistics and the behavior of the data. Hence, it is important to develop algorithms that take these structures into account when modeling such data. Apart from these hierarchical structures, some datasets are best explained with hierarchical models even though there is no apparent hierarchy in the data itself. For instance when modeling the occurrence of words in a document, it is more realistic to assume that the words are drawn in a hierarchical manner from a topic distribution rather than independently from a single topic. In this dissertation, we focus on capturing these hierarchies and leveraging them for modeling high dimensional datasets.

Hierarchical structures underlying the data are either observed or latent. For example in the context of computer programs, the syntax tree is inherent to the program and is therefore observed. On the other hand, the statistical dependence of a social network’s users is latent. In this dissertation, we study both types of hierarchies and develop models under both struc- tures because they both arise in many applications and are equally important. Nevertheless, capturing latent hierarchical structures is more challenging. We develop novel probabilistic models to capture latent hierarchies and present statistically efficient and provably consistent parameter learning algorithms for them. When capturing observed hierarchical structures we develop deep learning models that learn low-dimensional continuous representations for the discrete symbols and variables.

Matrix factorization is a popular machine learning technique, with applications in variety of domains, such as recommendation systems [16, 28], natural language processing [26], and computer vision [10]. Due to this widespread use of these models, there has been considerable theoretical analysis of the various properties of low-rank approximations of real-valued matrices, including approximation rank [1, 5] and sample complexity [2].

Rather than assume real-valued data, a number of studies (particularly ones on practical applications) focus on more specific data types, such as binary data [23], integer data [17], and ordinal data [12, 30]. For such matrices, existing approaches have used different link functions, applied in an element-wise manner to the low-rank representation [21], i.e. the output Y is ψ(U^TV) instead of the conventional U^TV. These link functions have been justified from a probabilistic point of view [4, 27], and have provided considerable success in empirical settings. However, theoretical results for linear factorization do not apply here, and thus the expressive power of the factorization models with non-linear link functions is not clear, and neither is the relation of the rank of a matrix to the link function used.

In this work, we first define a generalized notion of rank based on the link function ψ, as the rank of a latent matrix before the link function is applied. We focus on a link function that applies to factorization of integer-valued matrices: the generalized round function (GRF), and define the corresponding generalized round-rank (GRR). After providing background on GRR, we show that there are many low-GRR matrices that are full rank [1]. Moreover, we also study the approximation limitations of linear rank, by showing, for example, that low GRR matrices often cannot be approximated by low-rank linear matrices. We define uniqueness for GRR-based matrix completion, and derive its necessary and sufficient conditions. These properties demonstrate that many full linear-rank matrices can be factorized using low-rank matrices if an appropriate link function is used.

We also present an empirical evaluation of factorization with different link functions for matrix reconstruction and completion. We show that using link functions is efficient compared to linear rank, in that gradient-based optimization approach learns more accurate reconstructions using a lower rank representation and fewer training samples. We also perform experiments on matrix completion on two recommendation datasets, and demonstrate that appropriate link function outperform linear factorization, thus can play a crucial role in accurate matrix completion.

Sequentially making-decision abounds in real-world problems ranging from robots needing to interact with humans to companies aiming to provide reasonable services to their customers. It is as diverse as self-driving cars, health-care, agriculture, robotics, manufacturing, drug discovery, and aerospace. Reinforcement Learning (RL), as the study of sequential decision-making under uncertainty, represents a core aspect challenges in real-world applications.

While most of the practical application of interests in RL are high dimensions, we study RL problems from theory to practice in high dimensional, structured, and partially observable settings. We show how statistically develop efficient RL algorithm for a variety of RL problems, from recommendation systems to robotics and games. We theoretically study these problems from their first principles to provide RL agents which efficiently interact with their surrounding environment and learn the desired behavior while minimizing their regrets.

We study linear bandit problems where we propose Projected Stochastic Linear Bandit (PSLB), upper confidence bound based algorithm in linear bandit which exploit the intrinsic structure of the decision-making problem to significantly enhance the performance of RL agents.

We study the problem of RL in Markov Decision Process (MDP) where we propose the first sample efficient model-free algorithm for the general continuous state and action space MDPs. We further investigate safe RL setting and introduce a safe RL algorithm to avoid catastrophic mistakes that can be made by an RL agent. We extensively study tree-based methods, a well-popularized method in RL which is also the core to Alpha-Go, a technique to beat the masters of board games such as Go game.

We extend our study to partially observable environments, such as partially observable Markov decision processes (POMDP) where we propose the first regret analysis for the class of memoryless policies. We continue this study to a class of problems known as rich observable Markov decision processes (ROMPD) and propose the first regret bound with no dependency in the ambient dimension in the dominating terms.

We empirically study the significance of all these theoretically guaranteed methods and show their value in practice.

Deep neural networks that dominate NLP rely on an immense amount of parameters and require large text corpora for training. As these models are increasingly being deployed in the real world, there is an accompanying need to characterize potential failure modes of such models to avoid harms. In particular, it is now widely appreciated that training such models over large corpora commonly introduces biases into model predictions and other undesirable behaviors. Moreover, many of the training datasets are collected automatically or via crowdsourcing, and exhibit systematic biases or annotation artifacts. Considering the current trend in NLP, which relies on ever-growing models' and datasets' size, identifying the origin of an issue when we encounter a problematic behavior is becoming extremely challenging. To recognize any issue, traditionally, one might rely on explaining the model prediction using a variety of attribution methods. Although these methods demonstrate tremendous success in explaining models' predictions, the fragile nature of their explanations hinders their adoption in practice. In addition to looking into models' inner mechanism to identify the source of any issue, one can also try to follow breadcrumb trails into the training process, which is generally very expensive and time-consuming. In this dissertation, we turn toward training data to systematically identify the root of errors. After providing the necessary background in the second chapter, introducing a novel interpretability method for the knowledge graph completion (KGC) task, in the third chapter, we propose an automatic approach to extract mislabeled instances. In the fourth chapter, identifying several shortcomings in the current evaluation setting of KGC, we propose an alternative benchmark for the knowledge graph completion task and demonstrate the poor performance of state-of-the-art models in our benchmark. Shifting toward textual data, in the fifth chapter, we establish reliable and efficient instance attribution methods for explaining large language models. Finally, in the sixth chapter, we incorporate different attribution methods to discover existing artifacts in commonly used NLP benchmarks.

Determining the knowledge captured by pretrained language models is an important challenge, and is commonly tackled by probing model representations using classifiers. However, it is difficult to design probes for semantic knowledge such as facts. Reformulating these semantic tasks as cloze tests (i.e., fill-in-the-blank problems) is a promising method for probing such knowledge, but, it requires manually crafting textual prompts that elicit the desired knowledge, thus limiting its use. In this paper, we develop an automated, task-agnostic method to create cloze prompts for any classification task based on a gradient-guided search. Applying our technique, we find prompts that demonstrate MLMs have an inherent capability to perform fact retrieval and relation extraction. We show that our prompts elicit more accurate factual knowledge from MLMs compared to manual prompts, and further, MLMs can be used as relation extractors out of the box, when prompted with suitable prompts, more effectively than recent supervised RE models.

A knowledge graph represents factual information in the form of graphs, where nodes repre- sent real-world entities such as people, places and movies, and edges represent the relation- ships between these entities. Existing knowledge graphs are far from complete. Knowledge graph completion or link prediction refers to the task of predicting new relations (links) between entities by deriving information from the existing relations. A number of link pre- diction model have been proposed, several of which make probabilistic predictions about new links. These models can be rule-based methods derived from observed edges, latent represen- tation based embedding methods, or a combination of both. These methods must capture different kinds of relational patterns in the data, such as symmetry or inversion patterns to fully model the data. Rule-based methods explicitly learn these patterns, and provide an interpretable approach to predict new edges. With embedding based models, however, due to the nature of latent embeddings, it is difficult to understand what is being captured by these models. In this work, we explore the logical inference capabilities of knowledge graph embedding models. We experiment with various knowledge graph embedding models on syn- thetic datasets to identify specific properties of each model. The objective is to empirically validate the suitability of these models to learning different relational patterns that exist in real-world knowledge graphs.