Publications

Much has been discussed about how Large Language Models, Knowledge Graphs and
Search Engines can be combined in a synergistic manner. A dimension largely
absent from current academic discourse is the user perspective. In particular,
there remain many open questions regarding how best to address the diverse
information needs of users, incorporating varying facets and levels of
difficulty. This paper introduces a taxonomy of user information needs, which
guides us to study the pros, cons and possible synergies of Large Language
Models, Knowledge Graphs and Search Engines. From this study, we derive a
roadmap for future research.

This article presents the QUASAR system for question answering over
unstructured text, structured tables, and knowledge graphs, with unified
treatment of all sources. The system adopts a RAG-based architecture, with a
pipeline of evidence retrieval followed by answer generation, with the latter
powered by a moderate-sized language model. Additionally and uniquely, QUASAR
has components for question understanding, to derive crisper input for evidence
retrieval, and for re-ranking and filtering the retrieved evidence before
feeding the most informative pieces into the answer generation. Experiments
with three different benchmarks demonstrate the high answering quality of our
approach, being on par with or better than large GPT models, while keeping the
computational cost and energy consumption orders of magnitude lower.

General-domain knowledge bases (KB), in particular the "big three" --
Wikidata, Yago and DBpedia -- are the backbone of many intelligent
applications. While these three have seen steady development, comprehensive KB
construction at large has seen few fresh attempts. In this work, we propose to
build a large general-domain KB entirely from a large language model (LLM). We
demonstrate the feasibility of large-scale KB construction from LLMs, while
highlighting specific challenges arising around entity recognition, entity and
property canonicalization, and taxonomy construction. As a prototype, we use
GPT-4o-mini to construct GPTKB, which contains 105 million triples for more
than 2.9 million entities, at a cost 100x less than previous KBC projects. Our
work is a landmark for two fields: For NLP, for the first time, it provides
\textit{constructive} insights into the knowledge (or beliefs) of LLMs. For the
Semantic Web, it shows novel ways forward for the long-standing challenge of
general-domain KB construction. GPTKB is accessible at gptkb.org.

Question answering over knowledge graphs and other RDF data has been greatly
advanced, with a number of good systems providing crisp answers for natural
language questions or telegraphic queries. Some of these systems incorporate
textual sources as additional evidence for the answering process, but cannot
compute answers that are present in text alone. Conversely, systems from the IR
and NLP communities have addressed QA over text, but barely utilize semantic
data and knowledge. This paper presents the first QA system that can seamlessly
operate over RDF datasets and text corpora, or both together, in a unified
framework. Our method, called UNIQORN, builds a context graph on the fly, by
retrieving question-relevant triples from the RDF data and/or the text corpus,
where the latter case is handled by automatic information extraction. The
resulting graph is typically rich but highly noisy. UNIQORN copes with this
input by advanced graph algorithms for Group Steiner Trees, that identify the
best answer candidates in the context graph. Experimental results on several
benchmarks of complex questions with multiple entities and relations, show that
UNIQORN, an unsupervised method with only five parameters, produces results
comparable to the state-of-the-art on KGs, text corpora, and heterogeneous
sources. The graph-based methodology provides user-interpretable evidence for
the complete answering process.

Capturing fresh information in near real-time and using it to augment
existing large language models (LLMs) is essential to generate up-to-date,
grounded, and reliable output. This problem becomes particularly challenging
when LLMs are used for informational tasks in rapidly evolving fields, such as
Web search related to recent or unfolding events involving entities, where
generating temporally relevant responses requires access to up-to-the-hour news
sources. However, the information modeled by the parametric memory of LLMs is
often outdated, and Web results from prototypical retrieval systems may fail to
capture the latest relevant information and struggle to handle conflicting
reports in evolving news. To address this challenge, we present the NEON
framework, designed to extract emerging entity interactions -- such as events
or activities -- as described in news articles. NEON constructs an
entity-centric timestamped knowledge graph that captures such interactions,
thereby facilitating enhanced QA capabilities related to news events. Our
framework innovates by integrating open Information Extraction (openIE) style
tuples into LLMs to enable in-context retrieval-augmented generation. This
integration demonstrates substantial improvements in QA performance when
tackling temporal, entity-centric search queries. Through NEON, LLMs can
deliver more accurate, reliable, and up-to-date responses.

Methods for relation extraction from text mostly focus on high precision, at
the cost of limited recall. High recall is crucial, though, to populate long
lists of object entities that stand in a specific relation with a given
subject. Cues for relevant objects can be spread across many passages in long
texts. This poses the challenge of extracting long lists from long texts. We
present the L3X method which tackles the problem in two stages: (1)
recall-oriented generation using a large language model (LLM) with judicious
techniques for retrieval augmentation, and (2) precision-oriented
scrutinization to validate or prune candidates. Our L3X method outperforms
LLM-only generations by a substantial margin.

We examine the ability of large language models (LLMs) to generate salient
(interesting) negative statements about real-world entities; an emerging
research topic of the last few years. We probe the LLMs using zero- and k-shot
unconstrained probes, and compare with traditional methods for negation
generation, i.e., pattern-based textual extractions and knowledge-graph-based
inferences, as well as crowdsourced gold statements. We measure the correctness
and salience of the generated lists about subjects from different domains. Our
evaluation shows that guided probes do in fact improve the quality of generated
negatives, compared to the zero-shot variant. Nevertheless, using both prompts,
LLMs still struggle with the notion of factuality of negatives, frequently
generating many ambiguous statements, or statements with negative keywords but
a positive meaning.

Despite their impressive scale, knowledge bases (KBs), such as Wikidata,
still contain significant gaps. Language models (LMs) have been proposed as a
source for filling these gaps. However, prior works have focused on prominent
entities with rich coverage by LMs, neglecting the crucial case of long-tail
entities. In this paper, we present a novel method for LM-based-KB completion
that is specifically geared for facts about long-tail entities. The method
leverages two different LMs in two stages: for candidate retrieval and for
candidate verification and disambiguation. To evaluate our method and various
baselines, we introduce a novel dataset, called MALT, rooted in Wikidata. Our
method outperforms all baselines in F1, with major gains especially in recall.

Questions on class cardinality comparisons are quite tricky to answer and
come with its own challenges. They require some kind of reasoning since web
documents and knowledge bases, indispensable sources of information, rarely
store direct answers to questions, such as, ``Are there more astronauts or
Physics Nobel Laureates?'' We tackle questions on class cardinality comparison
by tapping into three sources for absolute cardinalities as well as the
cardinalities of orthogonal subgroups of the classes. We propose novel
techniques for aggregating signals with partial coverage for more reliable
estimates and evaluate them on a dataset of 4005 class pairs, achieving an
accuracy of 83.7%.

Large Language Models (LLMs) have taken Knowledge Representation -- and the
world -- by storm. This inflection point marks a shift from explicit knowledge
representation to a renewed focus on the hybrid representation of both explicit
knowledge and parametric knowledge. In this position paper, we will discuss
some of the common debate points within the community on LLMs (parametric
knowledge) and Knowledge Graphs (explicit knowledge) and speculate on
opportunities and visions that the renewed focus brings, as well as related
research topics and challenges.

General-purpose knowledge bases (KBs) are a cornerstone of knowledge-centric
AI. Many of them are constructed pragmatically from Web sources, and are thus
far from complete. This poses challenges for the consumption as well as the
curation of their content. While several surveys target the problem of
completing incomplete KBs, the first problem is arguably to know whether and
where the KB is incomplete in the first place, and to which degree.
In this survey we discuss how knowledge about completeness, recall, and
negation in KBs can be expressed, extracted, and inferred. We cover (i) the
logical foundations of knowledge representation and querying under partial
closed-world semantics; (ii) the estimation of this information via statistical
patterns; (iii) the extraction of information about recall from KBs and text;
(iv) the identification of interesting negative statements; and (v) relaxed
notions of relative recall.
This survey is targeted at two types of audiences: (1) practitioners who are
interested in tracking KB quality, focusing extraction efforts, and building
quality-aware downstream applications; and (2) data management, knowledge base
and semantic web researchers who wish to understand the state of the art of
knowledge bases beyond the open-world assumption. Consequently, our survey
presents both fundamental methodologies and their working, and gives
practice-oriented recommendations on how to choose between different approaches
for a problem at hand.

The widespread usage of latent language representations via pre-trained
language models (LMs) suggests that they are a promising source of structured
knowledge. However, existing methods focus only on a single object per
subject-relation pair, even though often multiple objects are correct. To
overcome this limitation, we analyze these representations for their potential
to yield materialized multi-object relational knowledge. We formulate the
problem as a rank-then-select task. For ranking candidate objects, we evaluate
existing prompting techniques and propose new ones incorporating domain
knowledge. Among the selection methods, we find that choosing objects with a
likelihood above a learned relation-specific threshold gives a 49.5% F1 score.
Our results highlight the difficulty of employing LMs for the multi-valued
slot-filling task and pave the way for further research on extracting
relational knowledge from latent language representations.

Questions on class cardinality comparisons are quite tricky to answer and
come with its own challenges. They require some kind of reasoning since web
documents and knowledge bases, indispensable sources of information, rarely
store direct answers to questions, such as, ``Are there more astronauts or
Physics Nobel Laureates?'' We tackle questions on class cardinality comparison
by tapping into three sources for absolute cardinalities as well as the
cardinalities of orthogonal subgroups of the classes. We propose novel
techniques for aggregating signals with partial coverage for more reliable
estimates and evaluate them on a dataset of 4005 class pairs, achieving an
accuracy of 83.7%.

Recommender systems are most successful for popular items and users with
ample interactions (likes, ratings etc.). This work addresses the difficult and
underexplored case of supporting users who have very sparse interactions but
post informative review texts. Our experimental studies address two book
communities with these characteristics. We design a framework with
Transformer-based representation learning, covering user-item interactions,
item content, and user-provided reviews. To overcome interaction sparseness, we
devise techniques for selecting the most informative cues to construct concise
user profiles. Comprehensive experiments, with datasets from Amazon and
Goodreads, show that judicious selection of text snippets achieves the best
performance, even in comparison to ChatGPT-generated user profiles.

Structured knowledge bases (KBs) are an asset for search engines and other
applications, but are inevitably incomplete. Language models (LMs) have been
proposed for unsupervised knowledge base completion (KBC), yet, their ability
to do this at scale and with high accuracy remains an open question. Prior
experimental studies mostly fall short because they only evaluate on popular
subjects, or sample already existing facts from KBs. In this work, we perform a
careful evaluation of GPT's potential to complete the largest public KB:
Wikidata. We find that, despite their size and capabilities, models like GPT-3,
ChatGPT and GPT-4 do not achieve fully convincing results on this task.
Nonetheless, they provide solid improvements over earlier approaches with
smaller LMs. In particular, we show that, with proper thresholding, GPT-3
enables to extend Wikidata by 27M facts at 90% precision.

Structured knowledge bases (KBs) are a foundation of many intelligent
applications, yet are notoriously incomplete. Language models (LMs) have
recently been proposed for unsupervised knowledge base completion (KBC), yet,
despite encouraging initial results, questions regarding their suitability
remain open. Existing evaluations often fall short because they only evaluate
on popular subjects, or sample already existing facts from KBs. In this work,
we introduce a novel, more challenging benchmark dataset, and a methodology
tailored for a realistic assessment of the KBC potential of LMs. For automated
assessment, we curate a dataset called WD-KNOWN, which provides an unbiased
random sample of Wikidata, containing over 3.9 million facts. In a second step,
we perform a human evaluation on predictions that are not yet in the KB, as
only this provides real insights into the added value over existing KBs. Our
key finding is that biases in dataset conception of previous benchmarks lead to
a systematic overestimate of LM performance for KBC. However, our results also
reveal strong areas of LMs. We could, for example, perform a significant
completion of Wikidata on the relations nativeLanguage, by a factor of ~21
(from 260k to 5.8M) at 82% precision, usedLanguage, by a factor of ~2.1 (from
2.1M to 6.6M) at 82% precision, and citizenOf by a factor of ~0.3 (from 4.2M to
5.3M) at 90% precision. Moreover, we find that LMs possess surprisingly strong
generalization capabilities: even on relations where most facts were not
directly observed in LM training, prediction quality can be high.

Commonsense knowledge about everyday concepts is an important asset for AI
applications, such as question answering and chatbots. Recently, we have seen
an increasing interest in the construction of structured commonsense knowledge
bases (CSKBs). An important part of human commonsense is about properties that
do not apply to concepts, yet existing CSKBs only store positive statements.
Moreover, since CSKBs operate under the open-world assumption, absent
statements are considered to have unknown truth rather than being invalid. This
paper presents the UNCOMMONSENSE framework for materializing informative
negative commonsense statements. Given a target concept, comparable concepts
are identified in the CSKB, for which a local closed-world assumption is
postulated. This way, positive statements about comparable concepts that are
absent for the target concept become seeds for negative statement candidates.
The large set of candidates is then scrutinized, pruned and ranked by
informativeness. Intrinsic and extrinsic evaluations show that our method
significantly outperforms the state-of-the-art. A large dataset of informative
negations is released as a resource for future research.

Commonsense knowledge about everyday concepts is an important asset for AI
applications, such as question answering and chatbots. Recently, we have seen
an increasing interest in the construction of structured commonsense knowledge
bases (CSKBs). An important part of human commonsense is about properties that
do not apply to concepts, yet existing CSKBs only store positive statements.
Moreover, since CSKBs operate under the open-world assumption, absent
statements are considered to have unknown truth rather than being invalid. This
paper presents the UNCOMMONSENSE framework for materializing informative
negative commonsense statements. Given a target concept, comparable concepts
are identified in the CSKB, for which a local closed-world assumption is
postulated. This way, positive statements about comparable concepts that are
absent for the target concept become seeds for negative statement candidates.
The large set of candidates is then scrutinized, pruned and ranked by
informativeness. Intrinsic and extrinsic evaluations show that our method
significantly outperforms the state-of-the-art. A large dataset of informative
negations is released as a resource for future research.

Conversational question answering (ConvQA) tackles sequential information
needs where contexts in follow-up questions are left implicit. Current ConvQA
systems operate over homogeneous sources of information: either a knowledge
base (KB), or a text corpus, or a collection of tables. This paper addresses
the novel issue of jointly tapping into all of these together, this way
boosting answer coverage and confidence. We present CONVINSE, an end-to-end
pipeline for ConvQA over heterogeneous sources, operating in three stages: i)
learning an explicit structured representation of an incoming question and its
conversational context, ii) harnessing this frame-like representation to
uniformly capture relevant evidences from KB, text, and tables, and iii)
running a fusion-in-decoder model to generate the answer. We construct and
release the first benchmark, ConvMix, for ConvQA over heterogeneous sources,
comprising 3000 real-user conversations with 16000 questions, along with entity
annotations, completed question utterances, and question paraphrases.
Experiments demonstrate the viability and advantages of our method, compared to
state-of-the-art baselines.

Knowledge extraction from text is a key task in natural language processing, which involves many sub-tasks, such as taxonomy induction, named entity recognition and typing, relation extraction, knowledge canonicalization and so on. By constructing structured knowledge from natural language text, knowledge extraction becomes a key asset for search engines, question answering and other downstream applications. However, current knowledge extraction methods mostly focus on prominent real-world entities with Wikipedia and mainstream news articles as sources. The constructed knowledge bases, therefore, lack information about long-tail domains, with fiction and fantasy as archetypes. Fiction and fantasy are core parts of our human culture, spanning from literature to movies, TV series, comics and video games. With thousands of fictional universes which have been created, knowledge from fictional domains are subject of search-engine queries - by fans as well as cultural analysts. Unlike the real-world domain, knowledge extraction on such specific domains like fiction and fantasy has to tackle several key challenges: - Training data: Sources for fictional domains mostly come from books and fan-built content, which is sparse and noisy, and contains difficult structures of texts, such as dialogues and quotes. Training data for key tasks such as taxonomy induction, named entity typing or relation extraction are also not available. - Domain characteristics and diversity: Fictional universes can be highly sophisticated, containing entities, social structures and sometimes languages that are completely different from the real world. State-of-the-art methods for knowledge extraction make assumptions on entity-class, subclass and entity-entity relations that are often invalid for fictional domains. With different genres of fictional domains, another requirement is to transfer models across domains. - Long fictional texts: While state-of-the-art models have limitations on the input sequence length, it is essential to develop methods that are able to deal with very long texts (e.g. entire books), to capture multiple contexts and leverage widely spread cues. This dissertation addresses the above challenges, by developing new methodologies that advance the state of the art on knowledge extraction in fictional domains. - The first contribution is a method, called TiFi, for constructing type systems (taxonomy induction) for fictional domains. By tapping noisy fan-built content from online communities such as Wikia, TiFi induces taxonomies through three main steps: category cleaning, edge cleaning and top-level construction. Exploiting a variety of features from the original input, TiFi is able to construct taxonomies for a diverse range of fictional domains with high precision. - The second contribution is a comprehensive approach, called ENTYFI, for named entity recognition and typing in long fictional texts. Built on 205 automatically induced high-quality type systems for popular fictional domains, ENTYFI exploits the overlap and reuse of these fictional domains on unseen texts. By combining different typing modules with a consolidation stage, ENTYFI is able to do fine-grained entity typing in long fictional texts with high precision and recall. - The third contribution is an end-to-end system, called KnowFi, for extracting relations between entities in very long texts such as entire books. KnowFi leverages background knowledge from 142 popular fictional domains to identify interesting relations and to collect distant training samples. KnowFi devises a similarity-based ranking technique to reduce false positives in training samples and to select potential text passages that contain seed pairs of entities. By training a hierarchical neural network for all relations, KnowFi is able to infer relations between entity pairs across long fictional texts, and achieves gains over the best prior methods for relation extraction.

In this thesis we explore pattern mining and deep learning. Often seen as orthogonal, we show that these fields complement each other and propose to combine them to gain from each other’s strengths. We, first, show how to efficiently discover succinct and non-redundant sets of patterns that provide insight into data beyond conjunctive statements. We leverage the interpretability of such patterns to unveil how and which information flows through neural networks, as well as what characterizes their decisions. Conversely, we show how to combine continuous optimization with pattern discovery, proposing a neural network that directly encodes discrete patterns, which allows us to apply pattern mining at a scale orders of magnitude larger than previously possible. Large neural networks are, however, exceedingly expensive to train for which ‘lottery tickets’ – small, well-trainable sub-networks in randomly initialized neural networks – offer a remedy. We identify theoretical limitations of strong tickets and overcome them by equipping these tickets with the property of universal approximation. To analyze whether limitations in ticket sparsity are algorithmic or fundamental, we propose a framework to plant and hide lottery tickets. With novel ticket benchmarks we then conclude that the limitation is likely algorithmic, encouraging further developments for which our framework offers means to measure progress.

In this work we address the challenging case of answering count queries in
web search, such as ``number of songs by John Lennon''. Prior methods merely
answer these with a single, and sometimes puzzling number or return a ranked
list of text snippets with different numbers. This paper proposes a methodology
for answering count queries with inference, contextualization and explanatory
evidence. Unlike previous systems, our method infers final answers from
multiple observations, supports semantic qualifiers for the counts, and
provides evidence by enumerating representative instances. Experiments with a
wide variety of queries, including existing benchmark show the benefits of our
method, and the influence of specific parameter settings. Our code, data and an
interactive system demonstration are publicly available at
github.com/ghoshs/CoQEx and nlcounqer.mpi-inf.mpg.de.

Social media communities like Reddit and Twitter allow users to express their views on
topics of their interest, and to engage with other users who may share or oppose these views.
This can lead to productive discussions towards a consensus, or to contended debates, where
disagreements frequently arise.
Prior work on such settings has primarily focused on identifying notable instances of antisocial
behavior such as hate-speech and “trolling”, which represent possible threats to the health of
a community. These, however, are exceptionally severe phenomena, and do not encompass
controversies stemming from user debates, differences of opinions, and off-topic content, all
of which can naturally come up in a discussion without going so far as to compromise its
development.
This dissertation proposes a framework for the systematic analysis of social media discussions
that take place in the presence of controversial themes, disagreements, and mixed opinions from
participating users. For this, we develop a feature-based model to describe key elements of a
discussion, such as its salient topics, the level of activity from users, the sentiments it expresses,
and the user feedback it receives.
Initially, we build our feature model to characterize adversarial discussions surrounding
political campaigns on Twitter, with a focus on the factual and sentimental nature of their
topics and the role played by different users involved. We then extend our approach to Reddit
discussions, leveraging community feedback signals to define a new notion of controversy
and to highlight conversational archetypes that arise from frequent and interesting interaction
patterns. We use our feature model to build logistic regression classifiers that can predict future
instances of controversy in Reddit communities centered on politics, world news, sports, and
personal relationships. Finally, our model also provides the basis for a comparison of different
communities in the health domain, where topics and activity vary considerably despite their
shared overall focus. In each of these cases, our framework provides insight into how user
behavior can shape a community’s individual definition of controversy and its overall identity.

As machine learning (ML) is increasingly used for decision making in scenarios that impact humans, there is a growing awareness of its potential for unfairness. A large body of recent work has focused on proposing formal notions of fairness in ML, as well as approaches to mitigate unfairness. However, there is a growing disconnect between the ML fairness literature and the needs to operationalize fairness in practice. This thesis addresses the need for responsible ML by developing new models and methods to address challenges in operationalizing fairness in practice. Specifically, it makes the following contributions. First, we tackle a key assumption in the group fairness literature that sensitive demographic attributes such as race and gender are known upfront, and can be readily used in model training to mitigate unfairness. In practice, factors like privacy and regulation often prohibit ML models from collecting or using protected attributes in decision making. To address this challenge we introduce the novel notion of computationally-identifiable errors and propose Adversarially Reweighted Learning (ARL), an optimization method that seeks to improve the worst-case performance over unobserved groups, without requiring access to the protected attributes in the dataset. Second, we argue that while group fairness notions are a desirable fairness criterion, they are fundamentally limited as they reduce fairness to an average statistic over pre-identified protected groups. In practice, automated decisions are made at an individual level, and can adversely impact individual people irrespective of the group statistic. We advance the paradigm of individual fairness by proposing iFair (individually fair representations), an optimization approach for learning a low dimensional latent representation of the data with two goals: to encode the data as well as possible, while removing any information about protected attributes in the transformed representation. Third, we advance the individual fairness paradigm, which requires that similar individuals receive similar outcomes. However, similarity metrics computed over observed feature space can be brittle, and inherently limited in their ability to accurately capture similarity between individuals. To address this, we introduce a novel notion of fairness graphs, wherein pairs of individuals can be identified as deemed similar with respect to the ML objective. We cast the problem of individual fairness into graph embedding, and propose PFR (pairwise fair representations), a method to learn a unified pairwise fair representation of the data. Fourth, we tackle the challenge that production data after model deployment is constantly evolving. As a consequence, in spite of the best efforts in training a fair model, ML systems can be prone to failure risks due to a variety of unforeseen reasons. To ensure responsible model deployment, potential failure risks need to be predicted, and mitigation actions need to be devised, for example, deferring to a human expert when uncertain or collecting additional data to address model’s blind-spots. We propose Risk Advisor, a model-agnostic meta-learner to predict potential failure risks and to give guidance on the sources of uncertainty inducing the risks, by leveraging information theoretic notions of aleatoric and epistemic uncertainty. This dissertation brings ML fairness closer to real-world applications by developing methods that address key practical challenges. Extensive experiments on a variety of real-world and synthetic datasets show that our proposed methods are viable in practice.

Automated methods have been widely used to identify and analyze mental health
conditions (e.g., depression) from various sources of information, including
social media. Yet, deployment of such models in real-world healthcare
applications faces challenges including poor out-of-domain generalization and
lack of trust in black box models. In this work, we propose approaches for
depression detection that are constrained to different degrees by the presence
of symptoms described in PHQ9, a questionnaire used by clinicians in the
depression screening process. In dataset-transfer experiments on three social
media datasets, we find that grounding the model in PHQ9's symptoms
substantially improves its ability to generalize to out-of-distribution data
compared to a standard BERT-based approach. Furthermore, this approach can
still perform competitively on in-domain data. These results and our
qualitative analyses suggest that grounding model predictions in
clinically-relevant symptoms can improve generalizability while producing a
model that is easier to inspect.

Structured knowledge is important for many AI applications. Commonsense
knowledge, which is crucial for robust human-centric AI, is covered by a small
number of structured knowledge projects. However, they lack knowledge about
human traits and behaviors conditioned on socio-cultural contexts, which is
crucial for situative AI. This paper presents CANDLE, an end-to-end methodology
for extracting high-quality cultural commonsense knowledge (CCSK) at scale.
CANDLE extracts CCSK assertions from a huge web corpus and organizes them into
coherent clusters, for 3 domains of subjects (geography, religion, occupation)
and several cultural facets (food, drinks, clothing, traditions, rituals,
behaviors). CANDLE includes judicious techniques for classification-based
filtering and scoring of interestingness. Experimental evaluations show the
superiority of the CANDLE CCSK collection over prior works, and an extrinsic
use case demonstrates the benefits of CCSK for the GPT-3 language model. Code
and data can be accessed at cultural-csk.herokuapp.com.

Compiling comprehensive repositories of commonsense knowledge is a
long-standing problem in AI. Many concerns revolve around the issue of
reporting bias, i.e., that frequency in text sources is not a good proxy for
relevance or truth. This paper explores whether children's texts hold the key
to commonsense knowledge compilation, based on the hypothesis that such content
makes fewer assumptions on the reader's knowledge, and therefore spells out
commonsense more explicitly. An analysis with several corpora shows that
children's texts indeed contain much more, and more typical commonsense
assertions. Moreover, experiments show that this advantage can be leveraged in
popular language-model-based commonsense knowledge extraction settings, where
task-unspecific fine-tuning on small amounts of children texts (childBERT)
already yields significant improvements. This provides a refreshing perspective
different from the common trend of deriving progress from ever larger models
and corpora.

Personal knowledge is a versatile resource that is valuable for a wide range of downstream applications. Background facts about users can allow chatbot assistants to produce more topical and empathic replies. In the context of recommendation and retrieval models, personal facts can be used to customize the ranking results for individual users. A Personal Knowledge Base, populated with personal facts, such as demographic information, interests and interpersonal relationships, is a unique endpoint for storing and querying personal knowledge. Such knowledge bases are easily interpretable and can provide users with full control over their own personal knowledge, including revising stored facts and managing access by downstream services for personalization purposes. To alleviate users from extensive manual effort to build such personal knowledge base, we can leverage automated extraction methods applied to the textual content of the users, such as dialogue transcripts or social media posts. Mainstream extraction methods specialize on well-structured data, such as biographical texts or encyclopedic articles, which are rare for most people. In turn, conversational data is abundant but challenging to process and requires specialized methods for extraction of personal facts. In this dissertation we address the acquisition of personal knowledge from conversational data. We propose several novel deep learning models for inferring speakers’ personal attributes: • Demographic attributes, age, gender, profession and family status, are inferred by HAMs - hierarchical neural classifiers with attention mechanism. Trained HAMs can be transferred between different types of conversational data and provide interpretable predictions. • Long-tailed personal attributes, hobby and profession, are predicted with CHARM - a zero-shot learning model, overcoming the lack of labeled training samples for rare attribute values. By linking conversational utterances to external sources, CHARM is able to predict attribute values which it never saw during training. • Interpersonal relationships are inferred with PRIDE - a hierarchical transformer-based model. To accurately predict fine-grained relationships, PRIDE leverages personal traits of the speakers and the style of conversational utterances. Experiments with various conversational texts, including Reddit discussions and movie scripts, demonstrate the viability of our methods and their superior performance compared to state-of-the-art baselines.

Commonsense knowledge (CSK) about concepts and their properties is useful for AI applications such as robust chatbots. Prior works like ConceptNet, TupleKB and others compiled large CSK collections, but are restricted in their expressiveness to subject-predicate-object (SPO) triples with simple concepts for S and monolithic strings for P and O. Also, these projects have either prioritized precision or recall, but hardly reconcile these complementary goals. This thesis presents a methodology, called Ascent, to automatically build a large-scale knowledge base (KB) of CSK assertions, with advanced expressiveness and both better precision and recall than prior works. Ascent goes beyond triples by capturing composite concepts with subgroups and aspects, and by refining assertions with semantic facets. The latter are important to express temporal and spatial validity of assertions and further qualifiers. Ascent combines open information extraction with judicious cleaning using language models. Intrinsic evaluation shows the superior size and quality of the Ascent KB, and an extrinsic evaluation for QA-support tasks underlines the benefits of Ascent.

Answering complex questions over knowledge bases (KB-QA) faces huge input
data with billions of facts, involving millions of entities and thousands of
predicates. For efficiency, QA systems first reduce the answer search space by
identifying a set of facts that is likely to contain all answers and relevant
cues. The most common technique or doing this is to apply named entity
disambiguation (NED) systems to the question, and retrieve KB facts for the
disambiguated entities. This work presents CLOCQ, an efficient method that
prunes irrelevant parts of the search space using KB-aware signals. CLOCQ uses
a top-k query processor over score-ordered lists of KB items that combine
signals about lexical matching, relevance to the question, coherence among
candidate items, and connectivity in the KB graph. Experiments with two recent
QA benchmarks for complex questions demonstrate the superiority of CLOCQ over
state-of-the-art baselines with respect to answer presence, size of the search
space, and runtimes.

Commonsense knowledge (CSK) about concepts and their properties is useful for AI applications such as robust chatbots. Prior works like ConceptNet, TupleKB and others compiled large CSK collections, but are restricted in their expressiveness to subject-predicate-object (SPO) triples with simple concepts for S and monolithic strings for P and O. Also, these projects have either prioritized precision or recall, but hardly reconcile these complementary goals. This thesis presents a methodology, called Ascent, to automatically build a large-scale knowledge base (KB) of CSK assertions, with advanced expressiveness and both better precision and recall than prior works. Ascent goes beyond triples by capturing composite concepts with subgroups and aspects, and by refining assertions with semantic facets. The latter are important to express temporal and spatial validity of assertions and further qualifiers. Ascent combines open information extraction with judicious cleaning using language models. Intrinsic evaluation shows the superior size and quality of the Ascent KB, and an extrinsic evaluation for QA-support tasks underlines the benefits of Ascent.

The strong lottery ticket hypothesis holds the promise that pruning randomly
initialized deep neural networks could offer a computationally efficient
alternative to deep learning with stochastic gradient descent. Common parameter
initialization schemes and existence proofs, however, are focused on networks
with zero biases, thus foregoing the potential universal approximation property
of pruning. To fill this gap, we extend multiple initialization schemes and
existence proofs to non-zero biases, including explicit 'looks-linear'
approaches for ReLU activation functions. These do not only enable truly
orthogonal parameter initialization but also reduce potential pruning errors.
In experiments on standard benchmark data sets, we further highlight the
practical benefits of non-zero bias initialization schemes, and present
theoretically inspired extensions for state-of-the-art strong lottery ticket
pruning.

Knowledge Graphs (KGs) have applications in many domains such as Finance, Manufacturing, and Healthcare. While recent efforts have created large KGs, their content is far from complete and sometimes includes invalid statements. Therefore, it is crucial to refine the constructed KGs to enhance their coverage and accuracy via KG completion and KG validation. It is also vital to provide human-comprehensible explanations for such refinements, so that humans have trust in the KG quality. Enabling KG exploration, by search and browsing, is also essential for users to understand the KG value and limitations towards down-stream applications. However, the large size of KGs makes KG exploration very challenging. While the type taxonomy of KGs is a useful asset along these lines, it remains insufficient for deep exploration. In this dissertation we tackle the aforementioned challenges of KG refinement and KG exploration by combining logical reasoning over the KG with other techniques such as KG embedding models and text mining. Through such combination, we introduce methods that provide human-understandable output. Concretely, we introduce methods to tackle KG incompleteness by learning exception-aware rules over the existing KG. Learned rules are then used in inferring missing links in the KG accurately. Furthermore, we propose a framework for constructing human-comprehensible explanations for candidate facts from both KG and text. Extracted explanations are used to insure the validity of KG facts. Finally, to facilitate KG exploration, we introduce a method that combines KG embeddings with rule mining to compute informative entity clusters with explanations.

Our increasing reliance on complex algorithms for recommendations calls for models and methods for explainable, scrutable, and trustworthy AI. While explainability is required for understanding the relationships between model inputs and outputs, a scrutable system allows us to modify its behavior as desired. These properties help bridge the gap between our expectations and the algorithm’s behavior and accordingly boost our trust in AI. Aiming to cope with information overload, recommender systems play a crucial role in filtering content (such as products, news, songs, and movies) and shaping a personalized experience for their users. Consequently, there has been a growing demand from the information consumers to receive proper explanations for their personalized recommendations. These explanations aim at helping users understand why certain items are recommended to them and how their previous inputs to the system relate to the generation of such recommendations. Besides, in the event of receiving undesirable content, explanations could possibly contain valuable information as to how the system’s behavior can be modified accordingly. In this thesis, we present our contributions towards explainability and scrutability of recommender systems: • We introduce a user-centric framework, FAIRY, for discovering and ranking post-hoc explanations for the social feeds generated by black-box platforms. These explanations reveal relationships between users’ profiles and their feed items and are extracted from the local interaction graphs of users. FAIRY employs a learning-to-rank (LTR) method to score candidate explanations based on their relevance and surprisal. • We propose a method, PRINCE, to facilitate provider-side explainability in graph-based recommender systems that use personalized PageRank at their core. PRINCE explanations are comprehensible for users, because they present subsets of the user’s prior actions responsible for the received recommendations. PRINCE operates in a counterfactual setup and builds on a polynomial-time algorithm for finding the smallest counterfactual explanations. • We propose a human-in-the-loop framework, ELIXIR, for enhancing scrutability and subsequently the recommendation models by leveraging user feedback on explanations. ELIXIR enables recommender systems to collect user feedback on pairs of recommendations and explanations. The feedback is incorporated into the model by imposing a soft constraint for learning user-specific item representations. We evaluate all proposed models and methods with real user studies and demonstrate their benefits at achieving explainability and scrutability in recommender systems.

System-provided explanations for recommendations are an important component
towards transparent and trustworthy AI. In state-of-the-art research, this is a
one-way signal, though, to improve user acceptance. In this paper, we turn the
role of explanations around and investigate how they can contribute to
enhancing the quality of generated recommendations themselves. We devise a
human-in-the-loop framework, called ELIXIR, where user feedback on explanations
is leveraged for pairwise learning of user preferences. ELIXIR leverages
feedback on pairs of recommendations and explanations to learn user-specific
latent preference vectors, overcoming sparseness by label propagation with
item-similarity-based neighborhoods. Our framework is instantiated using
generalized graph recommendation via Random Walk with Restart. Insightful
experiments with a real user study show significant improvements in movie and
book recommendations over item-level feedback.

State-of-the-art deep learning methods achieve human-like performance on many
tasks, but make errors nevertheless. Characterizing these errors in easily
interpretable terms gives insight into whether a model is prone to making
systematic errors, but also gives a way to act and improve the model. In this
paper we propose a method that allows us to do so for arbitrary classifiers by
mining a small set of patterns that together succinctly describe the input data
that is partitioned according to correctness of prediction. We show this is an
instance of the more general label description problem, which we formulate in
terms of the Minimum Description Length principle. To discover good pattern
sets we propose the efficient and hyperparameter-free Premise algorithm, which
through an extensive set of experiments we show on both synthetic and
real-world data performs very well in practice; unlike existing solutions it
ably recovers ground truth patterns, even on highly imbalanced data over many
unique items, or where patterns are only weakly associated to labels. Through
two real-world case studies we confirm that Premise gives clear and actionable
insight into the systematic errors made by modern NLP classifiers.

Low-dimensional embedding techniques such as tSNE and UMAP allow visualizing
high-dimensional data and therewith facilitate the discovery of interesting
structure. Although they are widely used, they visualize data as is, rather
than in light of the background knowledge we have about the data. What we
already know, however, strongly determines what is novel and hence interesting.
In this paper we propose two methods for factoring out prior knowledge in the
form of distance matrices from low-dimensional embeddings. To factor out prior
knowledge from tSNE embeddings, we propose JEDI that adapts the tSNE objective
in a principled way using Jensen-Shannon divergence. To factor out prior
knowledge from any downstream embedding approach, we propose CONFETTI, in which
we directly operate on the input distance matrices. Extensive experiments on
both synthetic and real world data show that both methods work well, providing
embeddings that exhibit meaningful structure that would otherwise remain
hidden.

Preference judgments have been demonstrated as a better alternative to graded
judgments to assess the relevance of documents relative to queries. Existing
work has verified transitivity among preference judgments when collected from
trained judges, which reduced the number of judgments dramatically. Moreover,
strict preference judgments and weak preference judgments, where the latter
additionally allow judges to state that two documents are equally relevant for
a given query, are both widely used in literature. However, whether
transitivity still holds when collected from crowdsourcing, i.e., whether the
two kinds of preference judgments behave similarly remains unclear. In this
work, we collect judgments from multiple judges using a crowdsourcing platform
and aggregate them to compare the two kinds of preference judgments in terms of
transitivity, time consumption, and quality. That is, we look into whether
aggregated judgments are transitive, how long it takes judges to make them, and
whether judges agree with each other and with judgments from TREC. Our key
findings are that only strict preference judgments are transitive. Meanwhile,
weak preference judgments behave differently in terms of transitivity, time
consumption, as well as of quality of judgment.

Question answering over knowledge graphs (KG-QA) is a vital topic in IR.
Questions with temporal intent are a special class of practical importance, but
have not received much attention in research. This work presents EXAQT, the
first end-to-end system for answering complex temporal questions that have
multiple entities and predicates, and associated temporal conditions. EXAQT
answers natural language questions over KGs in two stages, one geared towards
high recall, the other towards precision at top ranks. The first step computes
question-relevant compact subgraphs within the KG, and judiciously enhances
them with pertinent temporal facts, using Group Steiner Trees and fine-tuned
BERT models. The second step constructs relational graph convolutional networks
(R-GCNs) from the first step's output, and enhances the R-GCNs with time-aware
entity embeddings and attention over temporal relations. We evaluate EXAQT on
TimeQuestions, a large dataset of 16k temporal questions we compiled from a
variety of general purpose KG-QA benchmarks. Results show that EXAQT
outperforms three state-of-the-art systems for answering complex questions over
KGs, thereby justifying specialized treatment of temporal QA.

The rise of personal assistants has made conversational question answering
(ConvQA) a very popular mechanism for user-system interaction. State-of-the-art
methods for ConvQA over knowledge graphs (KGs) can only learn from crisp
question-answer pairs found in popular benchmarks. In reality, however, such
training data is hard to come by: users would rarely mark answers explicitly as
correct or wrong. In this work, we take a step towards a more natural learning
paradigm - from noisy and implicit feedback via question reformulations. A
reformulation is likely to be triggered by an incorrect system response,
whereas a new follow-up question could be a positive signal on the previous
turn's answer. We present a reinforcement learning model, termed CONQUER, that
can learn from a conversational stream of questions and reformulations. CONQUER
models the answering process as multiple agents walking in parallel on the KG,
where the walks are determined by actions sampled using a policy network. This
policy network takes the question along with the conversational context as
inputs and is trained via noisy rewards obtained from the reformulation
likelihood. To evaluate CONQUER, we create and release ConvRef, a benchmark
with about 11k natural conversations containing around 205k reformulations.
Experiments show that CONQUER successfully learns to answer conversational
questions from noisy reward signals, significantly improving over a
state-of-the-art baseline.

Federated learning allows multiple parties to collaboratively train a joint
model without sharing local data. This enables applications of machine learning
in settings of inherently distributed, undisclosable data such as in the
medical domain. In practice, joint training is usually achieved by aggregating
local models, for which local training objectives have to be in expectation
similar to the joint (global) objective. Often, however, local datasets are so
small that local objectives differ greatly from the global objective, resulting
in federated learning to fail. We propose a novel approach that intertwines
model aggregations with permutations of local models. The permutations expose
each local model to a daisy chain of local datasets resulting in more efficient
training in data-sparse domains. This enables training on extremely small local
datasets, such as patient data across hospitals, while retaining the training
efficiency and privacy benefits of federated learning.

Reliably predicting potential failure risks of machine learning (ML) systems
when deployed with production data is a crucial aspect of trustworthy AI. This
paper introduces Risk Advisor, a novel post-hoc meta-learner for estimating
failure risks and predictive uncertainties of any already-trained black-box
classification model. In addition to providing a risk score, the Risk Advisor
decomposes the uncertainty estimates into aleatoric and epistemic uncertainty
components, thus giving informative insights into the sources of uncertainty
inducing the failures. Consequently, Risk Advisor can distinguish between
failures caused by data variability, data shifts and model limitations and
advise on mitigation actions (e.g., collecting more data to counter data
shift). Extensive experiments on various families of black-box classification
models and on real-world and synthetic datasets covering common ML failure
scenarios show that the Risk Advisor reliably predicts deployment-time failure
risks in all the scenarios, and outperforms strong baselines.

Managing the data for Information Retrieval (IR) experiments can be
challenging. Dataset documentation is scattered across the Internet and once
one obtains a copy of the data, there are numerous different data formats to
work with. Even basic formats can have subtle dataset-specific nuances that
need to be considered for proper use. To help mitigate these challenges, we
introduce a new robust and lightweight tool (ir_datasets) for acquiring,
managing, and performing typical operations over datasets used in IR. We
primarily focus on textual datasets used for ad-hoc search. This tool provides
both a Python and command line interface to numerous IR datasets and
benchmarks. To our knowledge, this is the most extensive tool of its kind.
Integrations with popular IR indexing and experimentation toolkits demonstrate
the tool's utility. We also provide documentation of these datasets through the
ir_datasets catalog: ir-datasets.com. The catalog acts as a hub for
information on datasets used in IR, providing core information about what data
each benchmark provides as well as links to more detailed information. We
welcome community contributions and intend to continue to maintain and grow
this tool.

Deep Learning Hard (DL-HARD) is a new annotated dataset designed to more
effectively evaluate neural ranking models on complex topics. It builds on TREC
Deep Learning (DL) topics by extensively annotating them with question intent
categories, answer types, wikified entities, topic categories, and result type
metadata from a commercial web search engine. Based on this data, we introduce
a framework for identifying challenging queries. DL-HARD contains fifty topics
from the official DL 2019/2020 evaluation benchmark, half of which are newly
and independently assessed. We perform experiments using the official submitted
runs to DL on DL-HARD and find substantial differences in metrics and the
ranking of participating systems. Overall, DL-HARD is a new resource that
promotes research on neural ranking methods by focusing on challenging and
complex topics.

One of the core assumptions in causal discovery is the faithfulness
assumption---i.e. assuming that independencies found in the data are due to
separations in the true causal graph. This assumption can, however, be violated
in many ways, including xor connections, deterministic functions or cancelling
paths. In this work, we propose a weaker assumption that we call 2-adjacency
faithfulness. In contrast to adjacency faithfulness, which assumes that there
is no conditional independence between each pair of variables that are
connected in the causal graph, we only require no conditional independence
between a node and a subset of its Markov blanket that can contain up to two
nodes. Equivalently, we adapt orientation faithfulness to this setting. We
further propose a sound orientation rule for causal discovery that applies
under weaker assumptions. As a proof of concept, we derive a modified Grow and
Shrink algorithm that recovers the Markov blanket of a target node and prove
its correctness under strictly weaker assumptions than the standard
faithfulness assumption.

Estimating mutual information (MI) between two continuous random variables
$X$ and $Y$ allows to capture non-linear dependencies between them,
non-parametrically. As such, MI estimation lies at the core of many data
science applications. Yet, robustly estimating MI for high-dimensional $X$ and
$Y$ is still an open research question.
In this paper, we formulate this problem through the lens of manifold
learning. That is, we leverage the common assumption that the information of
$X$ and $Y$ is captured by a low-dimensional manifold embedded in the observed
high-dimensional space and transfer it to MI estimation. As an extension to
state-of-the-art $k$NN estimators, we propose to determine the $k$-nearest
neighbours via geodesic distances on this manifold rather than form the ambient
space, which allows us to estimate MI even in the high-dimensional setting. An
empirical evaluation of our method, G-KSG, against the state-of-the-art shows
that it yields good estimations of the MI in classical benchmark, and manifold
tasks, even for high dimensional datasets, which none of the existing methods
can provide.

Text and images are the two most common data modalities found on the Internet. Understanding the synergy between text and images, that is, seamlessly analyzing information from these modalities may be trivial for humans, but is challenging for software systems. In this dissertation we study problems where deciphering text-image synergy is crucial for finding solutions. We propose methods and ideas that establish semantic connections between text and images in multimodal contents, and empirically show their effectiveness in four interconnected problems: Image Retrieval, Image Tag Refinement, Image-Text Alignment, and Image Captioning. Our promising results and observations open up interesting scopes for future research involving text-image data understanding.Text and images are the two most common data modalities found on the Internet. Understanding the synergy between text and images, that is, seamlessly analyzing information from these modalities may be trivial for humans, but is challenging for software systems. In this dissertation we study problems where deciphering text-image synergy is crucial for finding solutions. We propose methods and ideas that establish semantic connections between text and images in multimodal contents, and empirically show their effectiveness in four interconnected problems: Image Retrieval, Image Tag Refinement, Image-Text Alignment, and Image Captioning. Our promising results and observations open up interesting scopes for future research involving text-image data understanding.

In this work we leverage recent advances in context-sensitive language models
to improve the task of query expansion. Contextualized word representation
models, such as ELMo and BERT, are rapidly replacing static embedding models.
We propose a new model, Contextualized Embeddings for Query Expansion (CEQE),
that utilizes query-focused contextualized embedding vectors. We study the
behavior of contextual representations generated for query expansion in ad-hoc
document retrieval. We conduct our experiments on probabilistic retrieval
models as well as in combination with neural ranking models. We evaluate CEQE
on two standard TREC collections: Robust and Deep Learning. We find that CEQE
outperforms static embedding-based expansion methods on multiple collections
(by up to 18% on Robust and 31% on Deep Learning on average precision) and also
improves over proven probabilistic pseudo-relevance feedback (PRF) models. We
further find that multiple passes of expansion and reranking result in
continued gains in effectiveness with CEQE-based approaches outperforming other
approaches. The final model incorporating neural and CEQE-based expansion score
achieves gains of up to 5% in P@20 and 2% in AP on Robust over the
state-of-the-art transformer-based re-ranking model, Birch.

ASCENT is a fully automated methodology for extracting and consolidating
commonsense assertions from web contents (Nguyen et al., WWW 2021). It advances
traditional triple-based commonsense knowledge representation by capturing
semantic facets like locations and purposes, and composite concepts, i.e.,
subgroups and related aspects of subjects. In this demo, we present a web
portal that allows users to understand its construction process, explore its
content, and observe its impact in the use case of question answering. The demo
website and an introductory video are both available online.

Pre-trained language models (LMs) have recently gained attention for their
potential as an alternative to (or proxy for) explicit knowledge bases (KBs).
In this position paper, we examine this hypothesis, identify strengths and
limitations of both LMs and KBs, and discuss the complementary nature of the
two paradigms. In particular, we offer qualitative arguments that latent LMs
are not suitable as a substitute for explicit KBs, but could play a major role
for augmenting and curating KBs.

Compiling commonsense knowledge is traditionally an AI topic approached by
manual labor. Recent advances in web data processing have enabled automated
approaches. In this demonstration we will showcase three systems for automated
commonsense knowledge base construction, highlighting each time one aspect of
specific interest to the data management community. (i) We use Quasimodo to
illustrate knowledge extraction systems engineering, (ii) Dice to illustrate
the role that schema constraints play in cleaning fuzzy commonsense knowledge,
and (iii) Ascent to illustrate the relevance of conceptual modelling. The demos
are available online at quasimodo.r2.enst.fr,
dice.mpi-inf.mpg.de and ascent.mpi-inf.mpg.de.

This paper presents a new task of predicting the coverage of a text document
for relation extraction (RE): does the document contain many relational tuples
for a given entity? Coverage predictions are useful in selecting the best
documents for knowledge base construction with large input corpora. To study
this problem, we present a dataset of 31,366 diverse documents for 520
entities. We analyze the correlation of document coverage with features like
length, entity mention frequency, Alexa rank, language complexity and
information retrieval scores. Each of these features has only moderate
predictive power. We employ methods combining features with statistical models
like TF-IDF and language models like BERT. The model combining features and
BERT, HERB, achieves an F1 score of up to 46%. We demonstrate the utility of
coverage predictions on two use cases: KB construction and claim refutation.

Prior work on personalized recommendations has focused on exploiting explicit
signals from user-specific queries, clicks, likes, and ratings. This paper
investigates tapping into a different source of implicit signals of interests
and tastes: online chats between users. The paper develops an expressive model
and effective methods for personalizing search-based entity recommendations.
User models derived from chats augment different methods for re-ranking entity
answers for medium-grained queries. The paper presents specific techniques to
enhance the user models by capturing domain-specific vocabularies and by
entity-based expansion. Experiments are based on a collection of online chats
from a controlled user study covering three domains: books, travel, food. We
evaluate different configurations and compare chat-based user models against
concise user profiles from questionnaires. Overall, these two variants perform
on par in terms of NCDG@20, but each has advantages in certain domains.

Prior work on personalizing web search results has focused on considering
query-and-click logs to capture users individual interests. For product search,
extensive user histories about purchases and ratings have been exploited.
However, for general entity search, such as for books on specific topics or
travel destinations with certain features, personalization is largely
underexplored. In this paper, we address personalization of book search, as an
exemplary case of entity search, by exploiting sparse user profiles obtained
through online questionnaires. We devise and compare a variety of re-ranking
methods based on language models or neural learning. Our experiments show that
even very sparse information about individuals can enhance the effectiveness of
the search results.

Understanding why specific items are recommended to users can significantly
increase their trust and satisfaction in the system. While neural recommenders
have become the state-of-the-art in recent years, the complexity of deep models
still makes the generation of tangible explanations for end users a challenging
problem. Existing methods are usually based on attention distributions over a
variety of features, which are still questionable regarding their suitability
as explanations, and rather unwieldy to grasp for an end user. Counterfactual
explanations based on a small set of the user's own actions have been shown to
be an acceptable solution to the tangibility problem. However, current work on
such counterfactuals cannot be readily applied to neural models. In this work,
we propose ACCENT, the first general framework for finding counterfactual
explanations for neural recommenders. It extends recently-proposed influence
functions for identifying training points most relevant to a recommendation,
from a single to a pair of items, while deducing a counterfactual set in an
iterative process. We use ACCENT to generate counterfactual explanations for
two popular neural models, Neural Collaborative Filtering (NCF) and Relational
Collaborative Filtering (RCF), and demonstrate its feasibility on a sample of
the popular MovieLens 100K dataset.

Knowledge bases (KBs), pragmatic collections of knowledge about notable
entities, are an important asset in applications such as search, question
answering and dialogue. Rooted in a long tradition in knowledge representation,
all popular KBs only store positive information, while they abstain from taking
any stance towards statements not contained in them.
In this paper, we make the case for explicitly stating interesting statements
which are not true. Negative statements would be important to overcome current
limitations of question answering, yet due to their potential abundance, any
effort towards compiling them needs a tight coupling with ranking. We introduce
two approaches towards compiling negative statements. (i) In peer-based
statistical inferences, we compare entities with highly related entities in
order to derive potential negative statements, which we then rank using
supervised and unsupervised features. (ii) In query-log-based text extraction,
we use a pattern-based approach for harvesting search engine query logs.
Experimental results show that both approaches hold promising and complementary
potential. Along with this paper, we publish the first datasets on interesting
negative information, containing over 1.1M statements for 100K popular Wikidata
entities.

The global infrastructure of the Web, designed as an open and transparent
system, has a significant impact on our society. However, algorithmic systems
of corporate entities that neglect those principles increasingly populated the
Web. Typical representatives of these algorithmic systems are recommender
systems that influence our society both on a scale of global politics and
during mundane shopping decisions. Recently, such recommender systems have come
under critique for how they may strengthen existing or even generate new kinds
of biases. To this end, designers and engineers are increasingly urged to make
the functioning and purpose of recommender systems more transparent. Our
research relates to the discourse of algorithm awareness, that reconsiders the
role of algorithm visibility in interface design. We conducted online
experiments with 105 participants using MTurk for the recommender system
Recoin, a gadget for Wikidata. In these experiments, we presented users with
one of a set of three different designs of Recoin's user interface, each of
them exhibiting a varying degree of explainability and interactivity. Our
findings include a positive correlation between comprehension of and trust in
an algorithmic system in our interactive redesign. However, our results are not
conclusive yet, and suggest that the measures of comprehension, fairness,
accuracy and trust are not yet exhaustive for the empirical study of algorithm
awareness. Our qualitative insights provide a first indication for further
measures. Our study participants, for example, were less concerned with the
details of understanding an algorithmic calculation than with who or what is
judging the result of the algorithm.

Translating verbose information needs into crisp search queries is a
phenomenon that is ubiquitous but hardly understood. Insights into this process
could be valuable in several applications, including synthesizing large
privacy-friendly query logs from public Web sources which are readily available
to the academic research community. In this work, we take a step towards
understanding query formulation by tapping into the rich potential of community
question answering (CQA) forums. Specifically, we sample natural language (NL)
questions spanning diverse themes from the Stack Exchange platform, and conduct
a large-scale conversion experiment where crowdworkers submit search queries
they would use when looking for equivalent information. We provide a careful
analysis of this data, accounting for possible sources of bias during
conversion, along with insights into user-specific linguistic patterns and
search behaviors. We release a dataset of 7,000 question-query pairs from this
study to facilitate further research on query understanding.

Counting answers to a query is an operation supported by virtually all
database management systems. In this paper we focus on counting answers over a
Knowledge Base (KB), which may be viewed as a database enriched with background
knowledge about the domain under consideration. In particular, we place our
work in the context of Ontology-Mediated Query Answering/Ontology-based Data
Access (OMQA/OBDA), where the language used for the ontology is a member of the
DL-Lite family and the data is a (usually virtual) set of assertions. We study
the data complexity of query answering, for different members of the DL-Lite
family that include number restrictions, and for variants of conjunctive
queries with counting that differ with respect to their shape (connected,
branching, rooted). We improve upon existing results by providing a PTIME and
coNP lower bounds, and upper bounds in PTIME and LOGSPACE. For the latter case,
we define a novel query rewriting technique into first-order logic with
counting.

Counting answers to a query is an operation supported by virtually all
database management systems. In this paper we focus on counting answers over a
Knowledge Base (KB), which may be viewed as a database enriched with background
knowledge about the domain under consideration. In particular, we place our
work in the context of Ontology-Mediated Query Answering/Ontology-based Data
Access (OMQA/OBDA), where the language used for the ontology is a member of the
DL-Lite family and the data is a (usually virtual) set of assertions. We study
the data complexity of query answering, for different members of the DL-Lite
family that include number restrictions, and for variants of conjunctive
queries with counting that differ with respect to their shape (connected,
branching, rooted). We improve upon existing results by providing a PTIME and
coNP lower bounds, and upper bounds in PTIME and LOGSPACE. For the latter case,
we define a novel query rewriting technique into first-order logic with
counting.

Commonsense knowledge (CSK) supports a variety of AI applications, from
visual understanding to chatbots. Prior works on acquiring CSK, such as
ConceptNet, have compiled statements that associate concepts, like everyday
objects or activities, with properties that hold for most or some instances of
the concept. Each concept is treated in isolation from other concepts, and the
only quantitative measure (or ranking) of properties is a confidence score that
the statement is valid. This paper aims to overcome these limitations by
introducing a multi-faceted model of CSK statements and methods for joint
reasoning over sets of inter-related statements. Our model captures four
different dimensions of CSK statements: plausibility, typicality, remarkability
and salience, with scoring and ranking along each dimension. For example,
hyenas drinking water is typical but not salient, whereas hyenas eating
carcasses is salient. For reasoning and ranking, we develop a method with soft
constraints, to couple the inference over concepts that are related in in a
taxonomic hierarchy. The reasoning is cast into an integer linear programming
(ILP), and we leverage the theory of reduction costs of a relaxed LP to compute
informative rankings. This methodology is applied to several large CSK
collections. Our evaluation shows that we can consolidate these inputs into
much cleaner and more expressive knowledge. Results are available at
dice.mpi-inf.mpg.de.

Predicate constraints of general-purpose knowledge bases (KBs) like Wikidata,
DBpedia and Freebase are often limited to subproperty, domain and range
constraints. In this demo we showcase CounQER, a system that illustrates the
alignment of counting predicates, like staffSize, and enumerating predicates,
like workInstitution^{-1} . In the demonstration session, attendees can inspect
these alignments, and will learn about the importance of these alignments for
KB question answering and curation. CounQER is available at
counqer.mpi-inf.mpg.de/spo.

Knowledge Bases (KBs) contain a wealth of structured information about
entities and predicates. This paper focuses on set-valued predicates, i.e., the
relationship between an entity and a set of entities. In KBs, this information
is often represented in two formats: (i) via counting predicates such as
numberOfChildren and staffSize, that store aggregated integers, and (ii) via
enumerating predicates such as parentOf and worksFor, that store individual set
memberships. Both formats are typically complementary: unlike enumerating
predicates, counting predicates do not give away individuals, but are more
likely informative towards the true set size, thus this coexistence could
enable interesting applications in question answering and KB curation.
In this paper we aim at uncovering this hidden knowledge. We proceed in two
steps. (i) We identify set-valued predicates from a given KB predicates via
statistical and embedding-based features. (ii) We link counting predicates and
enumerating predicates by a combination of co-occurrence, correlation and
textual relatedness metrics. We analyze the prevalence of count information in
four prominent knowledge bases, and show that our linking method achieves up to
0.55 F1 score in set predicate identification versus 0.40 F1 score of a random
selection, and normalized discounted gains of up to 0.84 at position 1 and 0.75
at position 3 in relevant predicate alignments. Our predicate alignments are
showcased in a demonstration system available at
counqer.mpi-inf.mpg.de/spo.

Question answering (QA) over text passages is a problem of long-standing
interest in information retrieval. Recently, the conversational setting has
attracted attention, where a user asks a sequence of questions to satisfy her
information needs around a topic. While this setup is a natural one and similar
to humans conversing with each other, it introduces two key research
challenges: understanding the context left implicit by the user in follow-up
questions, and dealing with ad hoc question formulations. In this work, we
demonstrate CROWN (Conversational passage ranking by Reasoning Over Word
Networks): an unsupervised yet effective system for conversational QA with
passage responses, that supports several modes of context propagation over
multiple turns. To this end, CROWN first builds a word proximity network (WPN)
from large corpora to store statistically significant term co-occurrences. At
answering time, passages are ranked by a combination of their similarity to the
question, and coherence of query terms within: these factors are measured by
reading off node and edge weights from the WPN. CROWN provides an interface
that is both intuitive for end-users, and insightful for experts for
reconfiguration to individual setups. CROWN was evaluated on TREC CAsT data,
where it achieved above-median performance in a pool of neural methods.

We present PARADE, an end-to-end Transformer-based model that considers
document-level context for document reranking. PARADE leverages passage-level
relevance representations to predict a document relevance score, overcoming the
limitations of previous approaches that perform inference on passages
independently. Experiments on two ad-hoc retrieval benchmarks demonstrate
PARADE's effectiveness over such methods. We conduct extensive analyses on
PARADE's efficiency, highlighting several strategies for improving it. When
combined with knowledge distillation, a PARADE model with 72\% fewer parameters
achieves effectiveness competitive with previous approaches using BERT-Base.
Our code is available at \url{https://github.com/canjiali/PARADE}.

The goal of text ranking is to generate an ordered list of texts retrieved
from a corpus in response to a query. Although the most common formulation of
text ranking is search, instances of the task can also be found in many natural
language processing applications. This survey provides an overview of text
ranking with neural network architectures known as transformers, of which BERT
is the best-known example. The combination of transformers and self-supervised
pretraining has, without exaggeration, revolutionized the fields of natural
language processing (NLP), information retrieval (IR), and beyond. In this
survey, we provide a synthesis of existing work as a single point of entry for
practitioners who wish to gain a better understanding of how to apply
transformers to text ranking problems and researchers who wish to pursue work
in this area. We cover a wide range of modern techniques, grouped into two
high-level categories: transformer models that perform reranking in multi-stage
ranking architectures and learned dense representations that attempt to perform
ranking directly. There are two themes that pervade our survey: techniques for
handling long documents, beyond the typical sentence-by-sentence processing
approaches used in NLP, and techniques for addressing the tradeoff between
effectiveness (result quality) and efficiency (query latency). Although
transformer architectures and pretraining techniques are recent innovations,
many aspects of how they are applied to text ranking are relatively well
understood and represent mature techniques. However, there remain many open
research questions, and thus in addition to laying out the foundations of
pretrained transformers for text ranking, this survey also attempts to
prognosticate where the field is heading.

Commonsense knowledge (CSK) about concepts and their properties is useful for AI applications such as robust chatbots. Prior works like ConceptNet, TupleKB and others compiled large CSK collections, but are restricted in their expressiveness to subject-predicate-object (SPO) triples with simple concepts for S and monolithic strings for P and O. Also, these projects have either prioritized precision or recall, but hardly reconcile these complementary goals. This thesis presents a methodology, called Ascent, to automatically build a large-scale knowledge base (KB) of CSK assertions, with advanced expressiveness and both better precision and recall than prior works. Ascent goes beyond triples by capturing composite concepts with subgroups and aspects, and by refining assertions with semantic facets. The latter are important to express temporal and spatial validity of assertions and further qualifiers. Ascent combines open information extraction with judicious cleaning using language models. Intrinsic evaluation shows the superior size and quality of the Ascent KB, and an extrinsic evaluation for QA-support tasks underlines the benefits of Ascent.

Commonsense knowledge (CSK) about concepts and their properties is useful for
AI applications such as robust chatbots. Prior works like ConceptNet, TupleKB
and others compiled large CSK collections, but are restricted in their
expressiveness to subject-predicate-object (SPO) triples with simple concepts
for S and monolithic strings for P and O. Also, these projects have either
prioritized precision or recall, but hardly reconcile these complementary
goals. This paper presents a methodology, called Ascent, to automatically build
a large-scale knowledge base (KB) of CSK assertions, with advanced
expressiveness and both better precision and recall than prior works. Ascent
goes beyond triples by capturing composite concepts with subgroups and aspects,
and by refining assertions with semantic facets. The latter are important to
express temporal and spatial validity of assertions and further qualifiers.
Ascent combines open information extraction with judicious cleaning using
language models. Intrinsic evaluation shows the superior size and quality of
the Ascent KB, and an extrinsic evaluation for QA-support tasks underlines the
benefits of Ascent.

Structured world knowledge is at the foundation of knowledge-centric AI applications. Despite considerable research on knowledge base construction, beyond mere statement counts, little is known about the progress of KBs, in particular concerning their coverage, and one may wonder whether there is constant progress, or diminishing returns. In this paper we employ question answering and entity summarization as extrinsic use cases for a longitudinal study of the progress of KB coverage. Our analysis shows a near-continuous improvement of two popular KBs, DBpedia and Wikidata, over the last 19 years, with little signs of flattening out or leveling off.

Structured world knowledge is at the foundation of knowledge-centric AI applications. Despite considerable research on knowledge base construction, beyond mere statement counts, little is known about the progress of KBs, in particular concerning their coverage, and one may wonder whether there is constant progress, or diminishing returns. In this paper we employ question answering and entity summarization as extrinsic use cases for a longitudinal study of the progress of KB coverage. Our analysis shows a near-continuous improvement of two popular KBs, DBpedia and Wikidata, over the last 19 years, with little signs of flattening out or leveling off.

The last few years have seen an explosion of research on the topic of
automated question answering (QA), spanning the communities of information
retrieval, natural language processing, and artificial intelligence. This
tutorial would cover the highlights of this really active period of growth for
QA to give the audience a grasp over the families of algorithms that are
currently being used. We partition research contributions by the underlying
source from where answers are retrieved: curated knowledge graphs, unstructured
text, or hybrid corpora. We choose this dimension of partitioning as it is the
most discriminative when it comes to algorithm design. Other key dimensions are
covered within each sub-topic: like the complexity of questions addressed, and
degrees of explainability and interactivity introduced in the systems. We would
conclude the tutorial with the most promising emerging trends in the expanse of
QA, that would help new entrants into this field make the best decisions to
take the community forward. Much has changed in the community since the last
tutorial on QA in SIGIR 2016, and we believe that this timely overview will
indeed benefit a large number of conference participants.

As news and social media exhibit an increasing amount of manipulative
polarized content, detecting such propaganda has received attention as a new
task for content analysis. Prior work has focused on supervised learning with
training data from the same domain. However, as propaganda can be subtle and
keeps evolving, manual identification and proper labeling are very demanding.
As a consequence, training data is a major bottleneck. In this paper, we tackle
this bottleneck and present an approach to leverage cross-domain learning,
based on labeled documents and sentences from news and tweets, as well as
political speeches with a clear difference in their degrees of being
propagandistic. We devise informative features and build various classifiers
for propaganda labeling, using cross-domain learning. Our experiments
demonstrate the usefulness of this approach, and identify difficulties and
limitations in various configurations of sources and targets for the transfer
step. We further analyze the influence of various features, and characterize
salient indicators of propaganda.

Equipping machines with comprehensive knowledge of the world's entities and
their relationships has been a long-standing goal of AI. Over the last decade,
large-scale knowledge bases, also known as knowledge graphs, have been
automatically constructed from web contents and text sources, and have become a
key asset for search engines. This machine knowledge can be harnessed to
semantically interpret textual phrases in news, social media and web tables,
and contributes to question answering, natural language processing and data
analytics. This article surveys fundamental concepts and practical methods for
creating and curating large knowledge bases. It covers models and methods for
discovering and canonicalizing entities and their semantic types and organizing
them into clean taxonomies. On top of this, the article discusses the automatic
extraction of entity-centric properties. To support the long-term life-cycle
and the quality assurance of machine knowledge, the article presents methods
for constructing open schemas and for knowledge curation. Case studies on
academic projects and industrial knowledge graphs complement the survey of
concepts and methods.

Structured world knowledge is at the foundation of knowledge-centric AI applications. Despite considerable research on knowledge base construction, beyond mere statement counts, little is known about the progress of KBs, in particular concerning their coverage, and one may wonder whether there is constant progress, or diminishing returns. In this paper we employ question answering and entity summarization as extrinsic use cases for a longitudinal study of the progress of KB coverage. Our analysis shows a near-continuous improvement of two popular KBs, DBpedia and Wikidata, over the last 19 years, with little signs of flattening out or leveling off.

Query expansion aims to mitigate the mismatch between the language used in a
query and in a document. However, query expansion methods can suffer from
introducing non-relevant information when expanding the query. To bridge this
gap, inspired by recent advances in applying contextualized models like BERT to
the document retrieval task, this paper proposes a novel query expansion model
that leverages the strength of the BERT model to select relevant document
chunks for expansion. In evaluation on the standard TREC Robust04 and GOV2 test
collections, the proposed BERT-QE model significantly outperforms BERT-Large
models.

Automatic text alignment is an important problem in natural language processing. It
can be used to create the data needed to train different language models. Most research
about automatic summarization revolves around summarizing news articles or scientific
papers, which are somewhat small texts with simple and clear structure. The bigger the
difference in size between the summary and the original text, the harder the problem will
be since important information will be sparser and identifying them can be more difficult.
Therefore, creating datasets from larger texts can help improve automatic summarization.
In this project, we try to develop an algorithm which can automatically create a
dataset for abstractive automatic summarization for bigger narrative text bodies such
as movie scripts. To this end, we chose sentences as summary text units and scenes
as script text units and developed an algorithm which uses some of the latest natural
language processing techniques to align scenes and sentences based on the similarity in
their meanings.
Solving this alignment problem can provide us with important information about how
to evaluate the meaning of a text, which can help us create better abstractive summariza-
tion models. We developed a method which uses different similarity scoring techniques
(embedding similarity, word inclusion and entity inclusion) to align script scenes and sum-
mary sentences which achieved an F1 score of 0.39. Analyzing our results showed that
the bigger the differences in the number of text units being aligned, the more difficult the
alignment problem is. We also critiqued of our own similarity scoring techniques and dif-
ferent alignment algorithms based on integer linear programming and local optimization
and showed their limitations and discussed ideas to improve them.

Answering complex natural language questions with crisp answers is crucial towards satisfying the information needs of advanced users. With the rapid growth of knowledge bases (KBs) such as Yago and Freebase, this goal has become attainable by translating questions into formal queries like SPARQL queries. Such queries can then be evaluated over knowledge bases to retrieve crisp answers. To this end, three research issues arise: (i) how to develop methods that are robust to lexical and syntactic variations in questions and can handle complex questions, (ii) how to design and curate datasets to advance research in question answering, and (iii) how to efficiently identify named entities in questions. In this dissertation, we make the following five contributions in the areas of question answering (QA) and named entity recognition (NER). For issue (i), we make the following contributions: We present QUINT, an approach for answering natural language questions over knowledge bases using automatically learned templates. Templates are an important asset for QA over KBs, simplifying the semantic parsing of input questions and generating formal queries for interpretable answers. QUINT is capable of answering both simple and compositional questions. We introduce NEQA, a framework for continuous learning for QA over KBs. NEQA starts with a small seed of training examples in the form of question-answer pairs, and improves its performance over time. NEQA combines both syntax, through template-based answering, and semantics, via a semantic similarity function. %when templates fail to do so. Moreover, it adapts to the language used after deployment by periodically retraining its underlying models. For issues (i) and (ii), we present TEQUILA, a framework for answering complex questions with explicit and implicit temporal conditions over KBs. TEQUILA is built on a rule-based framework that detects and decomposes temporal questions into simpler sub-questions that can be answered by standard KB-QA systems. TEQUILA reconciles the results of sub-questions into final answers. TEQUILA is accompanied with a dataset called TempQuestions, which consists of 1,271 temporal questions with gold-standard answers over Freebase. This collection is derived by judiciously selecting time-related questions from existing QA datasets. For issue (ii), we publish ComQA, a large-scale manually-curated dataset for QA. ComQA contains questions that represent real information needs and exhibit a wide range of difficulties such as the need for temporal reasoning, comparison, and compositionality. ComQA contains paraphrase clusters of semantically-equivalent questions that can be exploited by QA systems. We harness a combination of community question-answering platforms and crowdsourcing to construct the ComQA dataset.
For issue (iii), we introduce a neural network model based on subword units for named entity recognition. The model learns word representations using a combination of characters, bytes and phonemes. While achieving comparable performance with word-level based models, our model has an order-of-magnitude smaller vocabulary size and lower memory requirements, and it handles out-of-vocabulary words.

We consider algorithm selection in the context of ad-hoc information
retrieval. Given a query and a pair of retrieval methods, we propose a
meta-learner that predicts how to combine the methods' relevance scores into an
overall relevance score. Inspired by neural models' different properties with
regard to IR axioms, these predictions are based on features that quantify
axiom-related properties of the query and its top ranked documents. We conduct
an evaluation on TREC Web Track data and find that the meta-learner often
significantly improves over the individual methods. Finally, we conduct feature
and query weight analyses to investigate the meta-learner's behavior.

Following a period of expedited progress in the capabilities of digital systems, the society begins to realize that systems designed to assist people in various tasks can also harm individuals and society. Mediating access to information and explicitly or implicitly ranking people in increasingly many applications, search systems have a substantial potential to contribute to such unwanted outcomes. Since they collect vast amounts of data about both searchers and search subjects, they have the potential to violate the privacy of both of these groups of users. Moreover, in applications where rankings influence people's economic livelihood outside of the platform, such as sharing economy or hiring support websites, search engines have an immense economic power over their users in that they control user exposure in ranked results. This thesis develops new models and methods broadly covering different aspects of privacy and fairness in search systems for both searchers and search subjects. Specifically, it makes the following contributions: (1) We propose a model for computing individually fair rankings where search subjects get exposure proportional to their relevance. The exposure is amortized over time using constrained optimization to overcome searcher attention biases while preserving ranking utility. (2) We propose a model for computing sensitive search exposure where each subject gets to know the sensitive queries that lead to her profile in the top-k search results. The problem of finding exposing queries is technically modeled as reverse nearest neighbor search, followed by a weekly-supervised learning to rank model ordering the queries by privacy-sensitivity. (3) We propose a model for quantifying privacy risks from textual data in online communities. The method builds on a topic model where each topic is annotated by a crowdsourced sensitivity score, and privacy risks are associated with a user's relevance to sensitive topics. We propose relevance measures capturing different dimensions of user interest in a topic and show how they correlate with human risk perceptions. (4) We propose a model for privacy-preserving personalized search where search queries of different users are split and merged into synthetic profiles. The model mediates the privacy-utility trade-off by keeping semantically coherent fragments of search histories within individual profiles, while trying to minimize the similarity of any of the synthetic profiles to the original user profiles. The models are evaluated using information retrieval techniques and user studies over a variety of datasets, ranging from query logs, through social media and community question answering postings, to item listings from sharing economy platforms.

Fact-centric information needs are rarely one-shot; users typically ask
follow-up questions to explore a topic. In such a conversational setting, the
user's inputs are often incomplete, with entities or predicates left out, and
ungrammatical phrases. This poses a huge challenge to question answering (QA)
systems that typically rely on cues in full-fledged interrogative sentences. As
a solution, we develop CONVEX: an unsupervised method that can answer
incomplete questions over a knowledge graph (KG) by maintaining conversation
context using entities and predicates seen so far and automatically inferring
missing or ambiguous pieces for follow-up questions. The core of our method is
a graph exploration algorithm that judiciously expands a frontier to find
candidate answers for the current question. To evaluate CONVEX, we release
ConvQuestions, a crowdsourced benchmark with 11,200 distinct conversations from
five different domains. We show that CONVEX: (i) adds conversational support to
any stand-alone QA system, and (ii) outperforms state-of-the-art baselines and
question completion strategies.

Taxonomies are important building blocks of structured knowledge bases, and
their construction from text sources and Wikipedia has received much attention.
In this paper we focus on the construction of taxonomies for fictional domains,
using noisy category systems from fan wikis or text extraction as input. Such
fictional domains are archetypes of entity universes that are poorly covered by
Wikipedia, such as also enterprise-specific knowledge bases or highly
specialized verticals. Our fiction-targeted approach, called TiFi, consists of
three phases: (i) category cleaning, by identifying candidate categories that
truly represent classes in the domain of interest, (ii) edge cleaning, by
selecting subcategory relationships that correspond to class subsumption, and
(iii) top-level construction, by mapping classes onto a subset of high-level
WordNet categories. A comprehensive evaluation shows that TiFi is able to
construct taxonomies for a diverse range of fictional domains such as Lord of
the Rings, The Simpsons or Greek Mythology with very high precision and that it
outperforms state-of-the-art baselines for taxonomy induction by a substantial
margin.

Users increasingly rely on social media feeds for consuming daily
information. The items in a feed, such as news, questions, songs, etc., usually
result from the complex interplay of a user's social contacts, her interests
and her actions on the platform. The relationship of the user's own behavior
and the received feed is often puzzling, and many users would like to have a
clear explanation on why certain items were shown to them. Transparency and
explainability are key concerns in the modern world of cognitive overload,
filter bubbles, user tracking, and privacy risks. This paper presents FAIRY, a
framework that systematically discovers, ranks, and explains relationships
between users' actions and items in their social media feeds. We model the
user's local neighborhood on the platform as an interaction graph, a form of
heterogeneous information network constructed solely from information that is
easily accessible to the concerned user. We posit that paths in this
interaction graph connecting the user and her feed items can act as pertinent
explanations for the user. These paths are scored with a learning-to-rank model
that captures relevance and surprisal. User studies on two social platforms
demonstrate the practical viability and user benefits of the FAIRY method.

Interpretable explanations for recommender systems and other machine learning
models are crucial to gain user trust. Prior works that have focused on paths
connecting users and items in a heterogeneous network have several limitations,
such as discovering relationships rather than true explanations, or
disregarding other users' privacy. In this work, we take a fresh perspective,
and present PRINCE: a provider-side mechanism to produce tangible explanations
for end-users, where an explanation is defined to be a set of minimal actions
performed by the user that, if removed, changes the recommendation to a
different item. Given a recommendation, PRINCE uses a polynomial-time optimal
algorithm for finding this minimal set of a user's actions from an exponential
search space, based on random walks over dynamic graphs. Experiments on two
real-world datasets show that PRINCE provides more compact explanations than
intuitive baselines, and insights from a crowdsourced user-study demonstrate
the viability of such action-based explanations. We thus posit that PRINCE
produces scrutable, actionable, and concise explanations, owing to its use of
counterfactual evidence, a user's own actions, and minimal sets, respectively.

Search systems help users locate relevant information in the form of text documents for keyword queries. Using text alone, it is often difficult to satisfy the user's information need. To discern the user's intent behind queries, we turn to semantic annotations (e.g., named entities and temporal expressions) that natural language processing tools can now deliver with great accuracy. This thesis develops methods and an infrastructure that leverage semantic annotations to efficiently and effectively search large document collections. This thesis makes contributions in three areas: indexing, querying, and mining of semantically annotated document collections. First, we describe an indexing infrastructure for semantically annotated document collections. The indexing infrastructure can support knowledge-centric tasks such as information extraction, relationship extraction, question answering, fact spotting and semantic search at scale across millions of documents. Second, we propose methods for exploring large document collections by suggesting semantic aspects for queries. These semantic aspects are generated by considering annotations in the form of temporal expressions, geographic locations, and other named entities. The generated aspects help guide the user to relevant documents without the need to read their contents. Third and finally, we present methods that can generate events, structured tables, and insightful visualizations from semantically annotated document collections.

Search systems help users locate relevant information in the form of text documents for keyword queries. Using text alone, it is often difficult to satisfy the user's information need. To discern the user's intent behind queries, we turn to semantic annotations (e.g., named entities and temporal expressions) that natural language processing tools can now deliver with great accuracy. This thesis develops methods and an infrastructure that leverage semantic annotations to efficiently and effectively search large document collections. This thesis makes contributions in three areas: indexing, querying, and mining of semantically annotated document collections. First, we describe an indexing infrastructure for semantically annotated document collections. The indexing infrastructure can support knowledge-centric tasks such as information extraction, relationship extraction, question answering, fact spotting and semantic search at scale across millions of documents. Second, we propose methods for exploring large document collections by suggesting semantic aspects for queries. These semantic aspects are generated by considering annotations in the form of temporal expressions, geographic locations, and other named entities. The generated aspects help guide the user to relevant documents without the need to read their contents. Third and finally, we present methods that can generate events, structured tables, and insightful visualizations from semantically annotated document collections.

Popular word embedding methods such as word2vec and GloVe assign a single
vector representation to each word, even if a word has multiple distinct
meanings. Multi-sense embeddings instead provide different vectors for each
sense of a word. However, they typically cannot serve as a drop-in replacement
for conventional single-sense embeddings, because the correct sense vector
needs to be selected for each word. In this work, we study the effect of
multi-sense embeddings on the task of reverse dictionaries. We propose a
technique to easily integrate them into an existing neural network architecture
using an attention mechanism. Our experiments demonstrate that large
improvements can be obtained when employing multi-sense embeddings both in the
input sequence as well as for the target representation. An analysis of the
sense distributions and of the learned attention is provided as well.

There is a wealth of schema-free tables on the web. The text accompanying these tables explains and qualifies the numerical quantities given in the tables. Despite this ubiquity of tabular data, there is little research that harnesses this wealth of data by semantically understanding the information that is conveyed rather ambiguously in these tables. This information can be disambiguated only by the help of the accompanying text. In the process of understanding quantity mentions in tables and text, we are faced with the following challenges; First, there is no comprehensive knowledge base for anchoring quantity mentions. Second, tables are created ad-hoc without a standard schema and with ambiguous header names; also table cells usually contain abbreviations. Third, quantities can be written in multiple forms and units of measures. Fourth, the text usually refers to the quantities in tables using aggregation, approximation, and different scales. In this thesis, we target these challenges through the following contributions: - We present the Quantity Knowledge Base (QKB), a knowledge base for representing Quantity mentions. We construct the QKB by importing information from Freebase, Wikipedia, and other online sources. - We propose Equity: a system for automatically canonicalizing header names and cell values onto concepts, classes, entities, and uniquely represented quantities registered in a knowledge base. We devise a probabilistic graphical model that captures coherence dependencies between cells in tables and candidate items in the space of concepts, entities, and quantities. Then, we cast the inference problem into an efficient algorithm based on random walks over weighted graphs. baselines. - We introduce the quantity alignment problem: computing bidirectional links between textual mentions of quantities and the corresponding table cells. We propose BriQ: a system for computing such alignments. BriQ copes with the specific challenges of approximate quantities, aggregated quantities, and calculated quantities. - We design ExQuisiTe: a web application that identifies mentions of quantities in text and tables, aligns quantity mentions in the text with related quantity mentions in tables, and generates salient suggestions for extractive text summarization systems.

Question answering over knowledge bases (KB-QA) poses challenges in handling
complex questions that need to be decomposed into sub-questions. An important
case, addressed here, is that of temporal questions, where cues for temporal
relations need to be discovered and handled. We present TEQUILA, an enabler
method for temporal QA that can run on top of any KB-QA engine. TEQUILA has
four stages. It detects if a question has temporal intent. It decomposes and
rewrites the question into non-temporal sub-questions and temporal constraints.
Answers to sub-questions are then retrieved from the underlying KB-QA engine.
Finally, TEQUILA uses constraint reasoning on temporal intervals to compute
final answers to the full question. Comparisons against state-of-the-art
baselines show the viability of our method.

Information needs around a topic cannot be satisfied in a single turn; users
typically ask follow-up questions referring to the same theme and a system must
be capable of understanding the conversational context of a request to retrieve
correct answers. In this paper, we present our submission to the TREC
Conversational Assistance Track 2019, in which such a conversational setting is
explored. We propose a simple unsupervised method for conversational passage
ranking by formulating the passage score for a query as a combination of
similarity and coherence. To be specific, passages are preferred that contain
words semantically similar to the words used in the question, and where such
words appear close by. We built a word-proximity network (WPN) from a large
corpus, where words are nodes and there is an edge between two nodes if they
co-occur in the same passages in a statistically significant way, within a
context window. Our approach, named CROWN, improved nDCG scores over a provided
Indri baseline on the CAsT training data. On the evaluation data for CAsT, our
best run submission achieved above-average performance with respect to AP@5 and
nDCG@1000.

Given data over variables $(X_1,...,X_m, Y)$ we consider the problem of
finding out whether $X$ jointly causes $Y$ or whether they are all confounded
by an unobserved latent variable $Z$. To do so, we take an
information-theoretic approach based on Kolmogorov complexity. In a nutshell,
we follow the postulate that first encoding the true cause, and then the
effects given that cause, results in a shorter description than any other
encoding of the observed variables.
The ideal score is not computable, and hence we have to approximate it. We
propose to do so using the Minimum Description Length (MDL) principle. We
compare the MDL scores under the models where $X$ causes $Y$ and where there
exists a latent variables $Z$ confounding both $X$ and $Y$ and show our scores
are consistent. To find potential confounders we propose using latent factor
modeling, in particular, probabilistic PCA (PPCA).
Empirical evaluation on both synthetic and real-world data shows that our
method, CoCa, performs very well -- even when the true generating process of
the data is far from the assumptions made by the models we use. Moreover, it is
robust as its accuracy goes hand in hand with its confidence.

Matrix factorizations are an important tool in data mining, and they have been used extensively for finding latent patterns in the data. They often allow to separate structure from noise, as well as to considerably reduce the dimensionality of the input matrix. While classical matrix decomposition methods, such as nonnegative matrix factorization (NMF) and singular value decomposition (SVD), proved to be very useful in data analysis, they are limited by the underlying algebraic structure. NMF, in particular, tends to break patterns into smaller bits, often mixing them with each other. This happens because overlapping patterns interfere with each other, making it harder to tell them apart. In this thesis we study matrix factorization over algebraic structures known as dioids, which are characterized by the lack of additive inverse (“negative numbers”) and the idempotency of addition (a + a = a). Using dioids makes it easier to separate overlapping features, and, in particular, it allows to better deal with the above mentioned pattern breaking problem. We consider different types of dioids, that range from continuous (subtropical and tropical algebras) to discrete (Boolean algebra). Among these, the Boolean algebra is perhaps the most well known, and there exist methods that allow one to obtain high quality Boolean matrix factorizations in terms of the reconstruction error. In this work, however, a different objective function is used – the description length of the data, which enables us to obtain compact and highly interpretable results. The tropical and subtropical algebras, on the other hand, are much less known in the data mining field. While they find applications in areas such as job scheduling and discrete event systems, they are virtually unknown in the context of data analysis. We will use them to obtain idempotent nonnegative factorizations that are similar to NMF, but are better at separating the most prominent features of the data.

We revisit the notion of individual fairness proposed by Dwork et al. A
central challenge in operationalizing their approach is the difficulty in
eliciting a human specification of a similarity metric. In this paper, we
propose an operationalization of individual fairness that does not rely on a
human specification of a distance metric. Instead, we propose novel approaches
to elicit and leverage side-information on equally deserving individuals to
counter subordination between social groups. We model this knowledge as a
fairness graph, and learn a unified Pairwise Fair Representation(PFR) of the
data that captures both data-driven similarity between individuals and the
pairwise side-information in fairness graph. We elicit fairness judgments from
a variety of sources, including humans judgments for two real-world datasets on
recidivism prediction (COMPAS) and violent neighborhood prediction (Crime &
Communities). Our experiments show that the PFR model for operationalizing
individual fairness is practically viable.

Direct answering of questions that involve multiple entities and relations is
a challenge for text-based QA. This problem is most pronounced when answers can
be found only by joining evidence from multiple documents. Curated knowledge
graphs (KGs) may yield good answers, but are limited by their inherent
incompleteness and potential staleness. This paper presents QUEST, a method
that can answer complex questions directly from textual sources on-the-fly, by
computing similarity joins over partial results from different documents. Our
method is completely unsupervised, avoiding training-data bottlenecks and being
able to cope with rapidly evolving ad hoc topics and formulation style in user
questions. QUEST builds a noisy quasi KG with node and edge weights, consisting
of dynamically retrieved entity names and relational phrases. It augments this
graph with types and semantic alignments, and computes the best answers by an
algorithm for Group Steiner Trees. We evaluate QUEST on benchmarks of complex
questions, and show that it substantially outperforms state-of-the-art
baselines.

One challenge with neural ranking is the need for a large amount of
manually-labeled relevance judgments for training. In contrast with prior work,
we examine the use of weak supervision sources for training that yield pseudo
query-document pairs that already exhibit relevance (e.g., newswire
headline-content pairs and encyclopedic heading-paragraph pairs). We also
propose filtering techniques to eliminate training samples that are too far out
of domain using two techniques: a heuristic-based approach and novel supervised
filter that re-purposes a neural ranker. Using several leading neural ranking
architectures and multiple weak supervision datasets, we show that these
sources of training pairs are effective on their own (outperforming prior weak
supervision techniques), and that filtering can further improve performance.

Although considerable attention has been given to neural ranking
architectures recently, far less attention has been paid to the term
representations that are used as input to these models. In this work, we
investigate how two pretrained contextualized language modes (ELMo and BERT)
can be utilized for ad-hoc document ranking. Through experiments on TREC
benchmarks, we find that several existing neural ranking architectures can
benefit from the additional context provided by contextualized language models.
Furthermore, we propose a joint approach that incorporates BERT's
classification vector into existing neural models and show that it outperforms
state-of-the-art ad-hoc ranking baselines. We call this joint approach CEDR
(Contextualized Embeddings for Document Ranking). We also address practical
challenges in using these models for ranking, including the maximum input
length imposed by BERT and runtime performance impacts of contextualized
language models.

In many scientific tasks we are interested in discovering whether there exist
any correlations in our data. This raises many questions, such as how to
reliably and interpretably measure correlation between a multivariate set of
attributes, how to do so without having to make assumptions on distribution of
the data or the type of correlation, and, how to efficiently discover the
top-most reliably correlated attribute sets from data. In this paper we answer
these questions for discovery tasks in categorical data.
In particular, we propose a corrected-for-chance, consistent, and efficient
estimator for normalized total correlation, by which we obtain a reliable,
naturally interpretable, non-parametric measure for correlation over
multivariate sets. For the discovery of the top-k correlated sets, we derive an
effective algorithmic framework based on a tight bounding function. This
framework offers exact, approximate, and heuristic search. Empirical evaluation
shows that already for small sample sizes the estimator leads to low-regret
optimization outcomes, while the algorithms are shown to be highly effective
for both large and high-dimensional data. Through two case studies we confirm
that our discovery framework identifies interesting and meaningful
correlations.

Testing for conditional independence is a core aspect of constraint-based
causal discovery. Although commonly used tests are perfect in theory, they
often fail to reject independence in practice, especially when conditioning on
multiple variables.
We focus on discrete data and propose a new test based on the notion of
algorithmic independence that we instantiate using stochastic complexity.
Amongst others, we show that our proposed test, SCI, is an asymptotically
unbiased as well as $L_2$ consistent estimator for conditional mutual
information (CMI). Further, we show that SCI can be reformulated to find a
sensible threshold for CMI that works well on limited samples. Empirical
evaluation shows that SCI has a lower type II error than commonly used tests.
As a result, we obtain a higher recall when we use SCI in causal discovery
algorithms, without compromising the precision.