We present KaaPa (Knowledge Aware Answers from Pdf Analysis), an integrated solution for machine reading comprehension over both text and tables extracted from PDFs. KaaPa enables interactive question refinement using facets generated from an automatically induced Knowledge Graph. In addition it provides a concise summary of the supporting evidence for the provided answers by aggregating information across multiple sources. KaaPa can be applied consistently to any collection of documents in English with zero domain adaptation effort. We showcase the use of KaaPa for QA on scientific literature using the COVID-19 Open Research Dataset.

We address the web table retrieval task, aiming to retrieve and rank web tables as whole answers to a given information need. To this end, we formally define web tables as multimodal objects. We then suggest a neural ranking model, termed MTR, which makes a novel use of Gated Multimodal Units (GMUs) to learn a joint-representation of the query and the different table modalities. We further enhance this model with a co-learning approach which utilizes automatically learned query-independent and query-dependent "helper'' labels. We evaluate the proposed solution using both ad hoc queries (WikiTables) and natural language questions (GNQtables). Overall, we demonstrate that our approach surpasses the performance of previously studied state-of-the-art baselines.

We propose Dual-CES – a novel unsupervised, query-focused, multi-document extractive summarizer. Dual-CES builds on top of the Cross Entropy Summarizer (CES) and is designed to better handle the tradeoff between saliency and focus in summarization. To this end, Dual-CES employs a two-step dual-cascade optimization approach with saliency-based pseudo-feedback distillation. Overall, Dual-CES significantly outperforms all other state-of-the-art unsupervised alternatives. Dual-CES is even shown to be able to outperform strong supervised summarizers.

Given a keyword query, the ad hoc table retrieval task aims at retrieving a ranked list of the top-k most relevant tables in a given table corpus. Previous works have primarily focused on designing table-centric lexical and semantic features, which could be utilized for learning-to-rank (LTR) tables. In this work, we make a novel use of intrinsic (passage-based) and extrinsic (manifold-based) table similarities for enhanced retrieval. Using the WikiTables benchmark, we study the merits of utilizing such similarities for this task. To this end, we combine both similarity types via a simple, yet an effective, cascade re-ranking approach. Overall, our proposed approach results in a significantly better table retrieval quality, which even transcends that of strong semantically-rich baselines.

We propose to demonstrate SummIt -- a tool for extractive summarization, discovery and analysis. The main goal of SummIt is to provide consumable summaries that are driven by users' information intents. To this end, SummIt discovers and analyzes potential intents that can be used for summarization. Given an intent, SummIt generates a summary based on a novel unsupervised, query-focused, extractive, multi-document summarization approach. Using visualization aids, SummIt further allows to analyze a given summary and explore both its narrow and broader context.

We present a novel unsupervised query-focused multi-document summarization approach. To this end, we generate a summary by extracting a subset of sentences using the Cross-Entropy (CE) Method. The proposed approach is generic and requires no domain knowledge. Using an evaluation over DUC 2005-2007 datasets with several other state-of-the-art baseline methods, we demonstrate that, our approach is both effective and efficient.

Indexable dictionaries, supporting rank and select queries, are used as building blocks for many algorithms. For a universe U = {0, ..., |U| - 1} and an ordered set S = {s0, ..., sn-1} ⊆ U, an indexable dictionary supports rank and select queries in addition to membership queries, Select(j) query is used to get the j'th ranked element, and Rank(x) is used to retrieve the rank of x among all elements in S. In this work, we give two time-linear, one-pass practical constructions of static succinct indexable dictionaries, both are deterministic in query time, but they differ by construction method and Rank(x) query time. The first supports Rank and Select queries in constant time and has expected linear construction time. The second supports Select queries in constant time, and Rank(x) queries in O(log log |U|/n) time, has worst-case linear construction time, and uses only o(n) additional bits during construction. The latter one is fully indexable dictionary supporting Rank(x) queries on arbitrary x. These indexable dictionaries can be used where construction bounds matter, as in a dynamic algorithm that uses them as a building block, we exemplify this by showing how to utilize them to improve the query time of a dynamic dictionary matching algorithm.

Jonathan Herzig, Guy Feigenblat, Michal Shmueli-Scheuer, David Konopnicki, Anat Rafaeli, Daniel Altman, David Spivak. Proceedings of the 17th Annual Meeting of the Special Interest Group on Discourse and Dialogue. 2016.

Providing customer support through social media channels is gaining popularity. In such a context, predicting customer satisfaction in an early stage of a service conversation is important. Such an analysis can help personalize agent assignment to maximize customer satisfaction, and prioritize conversations. In this paper, we show that affective features such as customer's and agent's personality traits and emotion expression improve prediction of customer satisfaction when added to more typical text based features. We only utilize information extracted from the first customer conversation turn and previous customer and agent social network activity. Thus, our customer satisfaction classifier outputs its prediction in an early stage of the conversation, before any interaction has taken place between the customer and an agent. Our model was trained and tested on a Twitter conversations dataset of two customer support services, and shows an improvement of 30% in F1-score for predicting dissatisfaction.

In this paper we introduce a general framework that exponentially improves the space, the degree of independence, and the time needed by min-wise based algorithms. The authors, in SODA 2011, we introduced an exponential time improvement for min-wise based algorithms by defining and constructing an almost k-min-wise independent family of hash functions. Here we develop an alternative approach that achieves both exponential time and exponential space improvement. The new approach relaxes the need for approximately min-wise hash functions, hence gets around the Omega(log(1/epsilon)) independence lower bound in [Patrascu 2010]. This is done by defining and constructing a d-k-min-wise independent family of hash functions. Surprisingly, for most cases only 8-wise independence is needed for the additional improvement. Moreover, as the degree of independence is a small constant, our function can be implemented efficiently. Informally, under this definition, all subsets of size d of any fixed set X have an equal probability to have hash values among the minimal k values in X, where the probability is over the random choice of hash function from the family. This property measures the randomness of the family, as choosing a truly random function, obviously, satisfies the definition for d=k=|X|. We define and give an efficient time and space construction of approximately d-k-min-wise independent family of hash functions for the case where d=2, as this is sufficient for the additional exponential improvement. We discuss how this construction can be used to improve many min-wise based algorithms. To our knowledge such definitions, for hash functions, were never studied and no construction was given before. As an example we show how to apply it for similarity and rarity estimation over data streams. Other min-wise based algorithms, can be adjusted in the same way.

In this paper we extend the notion of min-wise independent family of hash functions by defining a k-min-wise independent family of hash functions. Informally under this definition, all subsets of size k of any fixed set X have an equal chance to have the minimal hash values among all the elements in X, when the probability is over the random choice of hash function from the family. This property measures the randomness of the family as choosing a truly random function, obviously satisfies the definition for k = |X|. We define and give an efficient time and space construction of approximately k-min-wise independent family of hash functions by extending Indyk's construction of approximately min-wise independent [1]. The number of words needed to represent each function is , which is only suboptimal by a factor of , where ε ∊ (0, 1) is the desired error bound. This construction is the first applicable for sampling bottom-k sketches [2, 3] out of the universe. In addition, we introduce a general and novel technique that utilizes our construction, and can be used to improve many min-wise based algorithms, such as [4, 5, 6, 7, 3, 2, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]. As an example we show how to apply it for similarity estimation over data streams, and reduce exponentially the run time of the current known result [5]. In addition, we also discuss improvements of known algorithms for estimating rarity and entropy of random walk over graphs (from SODA07 [20]).