Abstract

The phrase coined by Clive Humby in 2006 has proven to be true in the research community where state-of-the-art has been progressively achieved with advent of sophisticated models as a result of new datasets. Current state-of-the-art models like Transformer-based BERT requires a lot of data to train but gives higher benchmark results for several tasks. This is good when the problem at hand already has a dataset defined. It becomes challenging when we are addressing a problem for which there exists no dataset. These problems mostly lie in a specific domain. In this thesis, we explore two such domainspecific problems and propose approach to address the problems even when less or no data exists for those problems. First problem we look at is Automatic Summarization of Financial Annual reports. Financial reports filed by various companies discuss compliance, risks, and future plans, such as goals and new projects, which directly impact their stock price. Quick consumption of such information is critical for financial analysts and investors to make stock buy/sell decisions and for equity evaluations. Hence, we study the problem of extractive summarization of 10-K reports. Recently, Transformer-based summarization models have become very popular. However, lack of in-domain labeled summarization data is a major roadblock to train such finance-specific summarization models. We also show that zero-shot inference on such pre-trained models is not as effective either. We address this challenge by modeling 10-K report summarization using a goal-directed setting where we leverage summaries with labeled goal-related data for the stock buy/sell classification goal. Further, we provide improvements by considering a multi-task learning method with an industry classification auxiliary task. We also show how idiosyncratic factors within a company can be incorporated into the summaries by using the proposed framework. Intrinsic evaluation as well as extrinsic evaluation for the stock buy/sell classification and portfolio construction tasks shows that our proposed method significantly outperforms strong baselines. Second problem we look at is the Automatic Question Generation from technical text. Asking questions about a subject has been an integral part to test candidates for subject knowledge and understanding. These questions generally require higher order reasoning and thinking. The answers or reasoning of such questions can span across paragraphs or even documents. Generating such questions has mostly been ignored in current research. We propose fully automated answer unaware question generation for technical text used for evaluating candidate’s understanding. It follows unsupervised learning paradigm and does not need labeled training data. It constructs a concept graph (CG) by automatically extract ing concepts and inter-concept relations from input text. It then exploits the concept graph to generate questions. Concept graph is used in order to address the issue of inter-sentence question generation. We evaluate the question acceptability using the well-established criteria laid down by Heilman et. al. [23] and show that the proposed approach consistently outperforms the classic linguistics based method as well as state-of-the-art Deep Learning and Transformer based question generation systems. We also propose a ranking mechanism for questions which further increases the number of acceptable questions. To summarize, we make use of other existing data which is related to the problem but not addresses the exact problem to approach the problem in a novel way by still leveraging the complexity of stateto-the-art data hungry models. We also make use of linguistic clues and other pre-trained models to address the data scarcity issue.

Abstract

With the growing use of natural language processing tools (NLP) in wide-ranging applications, it becomes imperative to understand why NLP models are as successful as they are. In particular, it is essential to understand what mathematical structures precisely underpin these models. To investigate the mathematical models of NLP knowledge representations, we focus on the setting of unsupervised word embeddings, due to the presence of robust models, and a seemingly simple mathematical structure. We find that even in this restricted setting, there are subtle, cross-cutting concerns as to how the model learns — beginning from the high level description of learning a “vector”, to the low level details of implementations of these algorithms, including initialization and gradient calculation. We build a theory of knowledge representations for word embeddings, inspired by two seemingly unrelated ideas (a) Montague semantics [25], a linguistic theory of meaning which ascribes set-theoretic meaning to language, and (b) abstract interpretation, a mathematical theory of creating computable approximations to uncomputable semantics of programs. We find that synthesizing these ideas provide a way to extract fuzzy-set embeddings from existing word-embeddings, which provides the full range of set-theoretic operations (union, intersection, and others), along with probabilistic operations (KL divergence, entropy) which are used to perform polysemy detection and word sense disambiguation, while retaining performance on regular word embeddings tasks such as similarity. Next, we turn our attention to generalizing the word embedding training regime by extracting the geometry which is currently held implicit. This leads us to formulate a general theory of learning word representations on Lie groups. In summary, we provide insight into the mathematical structure of word representations.

Abstract

News is an essential component of the information we consume, and it plays a pivotal role in shaping our worldview. With the advent of technology, traditional distribution channels for news are increasingly being replaced by digital alternatives. This has led to a democratization of the entire journalistic landscape, where conventional economic entry barriers have been drastically reduced. Inevitably, this has also increased competition in the domain, with independent journalists and large media corporations alike vying for readers’ attention in the digital space. This attention is monetized either via advertisements on news pages or through an online subscription model. The ensuing competition has led media houses to use creative and somewhat devious news headlines to generate the all-important ’click’ from readers, which can be monetized. One such commonly used tactic is ’clickbait’. A clickbait is a news headline that encourages people to click on it to know more, without revealing much information about what the readers will see on the hyperlinked article, for example, ”You won’t believe what Apple showcased yesterday!” Clickbait works by rousing readers’ specific epistemic curiosity. The perception of an ’Information Gap’ is created in the mind of readers, where attention becomes focused on a gap in one’s knowledge based on the partial information conveyed by a clickbait headline. Readers click on such headlines to satiate the created knowledge gap, making clickbait effective in the process. Cognitive research has shown that clickbait is a form of attention distraction that increases stress and lowers productivity. The proliferation of clickbait also impacts readers’ news consumption experience. It has been called a diversion of publisher resources, away from quality value-added journalism towards a rapid-churning factory of digital serfs. Additionally, clickbait may also lead to the propagation of false information when readers rely solely on headlines with misleading or scarce information to form their worldview rather than reading complete articles. For example, a clickbait headline like “This is what X did to a dog” can have a subjective interpretation based on one’s bias towards X. If one has a preference for X, then without reading the article, the information gap will likely be filled, assuming a compassionate action for the dog. While, if one has a negative bias against X, inferences will be skewed in the opposite direction. The use of word-limited media platforms like Twitter would further perpetuate the above perceptions. The democratization of digital news media, while a positive development towards greater freedom of speech and allowing for alternate viewpoints, raises serious issues around the credibility of information. Our first study explored the impact of clickbait headlines on the credibility of news items through a study on 200 participants recruited on Amazon’s Mechanical Turk. We found that clickbait headlines significantly reduce the credibility of a news item when controlled for the article’s content. To explore the demographic segments most likely to indulge clickbait headlines, we also looked at relations between clickbait propensity and factors like readers’ age, curiosity, news interests, news sources, education levels, gender, among others. Our second study was a first-of-its-kind exploration of the proliferation of clickbait in mainstream Hindi news media. The objective here was to bring to light the urgent need for further research in non-English languages. Clickbait detection research in Hindi and other regional languages lags far behind work done for English. 7 independent annotators were recruited to mark an aggregated 100 most retweeted news posts by five mainstream Hindi news sources. Clickbait proliferation in Hindi news media was found to be similar to English news media. Additionally, a positive correlation was found between readers’ interaction and the clickbait score of news headlines. In follow-up experiments, we looked at the consumption of clickbait in Hindi news media and its relation with readers – exploring clickbait propensity of different demographic segments, the role of curiosity, and the impact on credibility. We observed no significant difference in the click-through rate of clickbait and non-clickbait headlines for Hindi news articles. Interestingly, male participants had a significantly higher propensity for clickbait than female participants for Hindi news media. Clickbait had no impact on the credibility of news media for Hindi news articles. In our third study, we focused on the impact of clickbait headlines on readers’ visual attention. Visual attention was measured in a controlled lab experiment with subjects reading patterns observed under an eye-tracker setup as they browsed through news items. Additionally, recall was also measured through a questionnaire

Abstract

We showcase a topological mapping framework for a challenging indoor warehouse setting. At the most abstract level, the warehouse is represented as a Topological Graph where the nodes of the graph represent a particular warehouse topological construct (e.g. rackspace, corridor) and the edges denote the existence of a path between two neighbouring nodes or topologies. At the intermediate level, the map is represented as a Manhattan Graph where the nodes and edges are characterized by Manhattan properties and as a Pose Graph at the lower-most level of detail. The topological constructs are learned via a Deep Convolutional Network while the relational properties between topological instances are learnt via a Siamese-style Neural Network. In the thesis, we show that maintaining abstractions such as Topological Graph and Manhattan Graph help in recovering an accurate Pose Graph starting from a highly erroneous and unoptimized Pose Graph. We show how this is achieved by embedding topological and Manhattan relations as well as Manhattan Graph aided loop closure relations as constraints in the backend Pose Graph optimization framework. The recovery of near ground-truth Pose Graph on realworld indoor warehouse scenes vindicate the efficacy of the proposed framework.

Abstract

Retail stores have become an integral part of our daily lives and play a vital economic role in a society. It has been found that retailers can increase sales through proficient shelf-space management. So, developing approaches for efficient product placement in retail stores is one of the key research issues. Traditionally, approaches have been proposed based on dynamic programming models. These modeling approaches have limitations due to the inherent complexity of handling a large number of variables with approximation. Since 1990, data analysis methods have provided an opportunity to retailers to understand the buying patterns of their customers by analyzing customer purchase data. Moreover, after the emergence of data mining approaches, several research works have been proposed by extending pattern mining techniques for improved product placement in retail. Especially, Frequent Pattern Mining, which is one of the task of data mining, can be used to extract patterns (or itemsets) from a given set of transactions. Furthermore, several kinds of utility mining techniques have been proposed in the literature for extracting the knowledge of high-utility itemsets by incorporating the notion of utility of the item. On the other hand, in the field of pattern mining, approaches have been proposed to extract the knowledge of generalized itemsets from the given transcational dataset and a taxonomy among the items. In this thesis, we propose an improved product placement approach by extending a generalized itemset mining framework to the existing utility mining approach, which has been proposed for product placement. Generalized high-utility itemset mining entails the extraction of high-utility itemsets by exploring the association among categories/generalized items at higher-level concepts in a given product taxonomy. We exploit the fact that the knowledge of generalized high-utility itemsets extracted from a user purchase transactional database in conjunction with a product taxonomy can provide new insights about customer purchase behaviour. Given a user purchase transactions database and a product taxonomy, we propose a utility-based indexing scheme to extract high-utility (revenue) generalized itemsets. For a given level of the taxonomy, we build an index, designated as the Generalized Utility Itemset (GUI) index, to identify and store high-revenue generalized itemsets. Intrinsically, generalized itemsets are virtual in the sense that they cannot be directly placed in the slots of the given retail store. Here, the issue is also to identify the specific actual items pertaining to a given generalized pattern to be placed in the slots of the retail store for improving the revenue of the retailer. The proposed product placement framework exploits the proposed GUI index for placing items in the shelf space of the retail store to maximize retailer revenue. Our performance evaluation on three real datasets, namely the instacart retail dataset (containing 49,688 items and 3,214874 transactions), the classical R ”groceries” dataset (containing 169 items and 9,835 transactions) and the fruithut dataset (containing 1,265 items and 181,979 transactions), demonstrates the effectiveness of the proposed scheme in terms of total revenue and execution time as compared with the three existing schemes.

Abstract

Online learning is a very well worked learning paradigm that has both theoretical as well as practical appeal. Online learning aims to make a sequence of accurate predictions given the correct answer to previous prediction tasks and possibly additional available information. One of the subproblems of great interest in this field of learning is multiclass classification in online settings. Multiclass classification can be understood as predicting the best label, out of a given number of labels, for a particular instance. In this thesis, we address the problem of multiclass classification in an online setting. Notably, we investigate the case of learning in limited feedback (partial and bandit) from the environment in online fashion. We may not be given exact class labels or ground truths for training instances in many real-life classification problems. Instead, we could be given a set of candidate labels containing the true label or binary feedback indicating whether our prediction is correct or not. In both of these scenarios, we are left in uncertainty about the actual class label. This thesis will do a literature survey and a brief study of the current work done. We will then propose the solutions to the problems mentioned above with thorough mathematical analysis, including regret bounds and experimental evidences suggesting the correctness and efficiency of the proposed methods.

Abstract

As we march into the digital information age, data overload is one of the most significant concerns in almost all domains. Massive volumes of data generate and accumulate every day. With the rise in data volumes arise the need for sophisticated computational techniques and tools to support the extraction of useful knowledge from data. This data can only provide value if we can extract hidden patterns and knowledge from it and utilize it to achieve business or operational goals. The field of Knowledge Discovery in Databases (KDD) aims at finding structures and meaningful information from raw unstructured data. KDD is an iterative process consisting of multiple phases and generally requires domain knowledge and data analysis expertise. With the inclusion of information technology in all spheres of life, significant work has been done in the field of KDD to utilize computational techniques. Today we have a plethora of software systems to support KDD. These systems provide the ability for KDD specification and execution with an interactive user interface or API integration for external systems. However, most of these systems support the KDD process in a fixed, predetermined manner. The specification and execution procedures are coded as a fixed set of rules/algorithms, lacking the much-needed dynamism in the so-called fuzzy, complicated knowledge discovery process. We propose a solution that can ease this stringent process by using the concept of meta workflows. We show that the KDD process can be modeled as a workflow, which can then be coupled with Meta Workflows leading to a flexible KDD management system. We allow KDD specification and execution procedures to be dynamically modifiable at runtime by using the concept of meta workflows. In our work, we present a Meta Workflow based solution for KDD specification and execution. This is done using two Meta Workflows – Meta Specification Workflow and Meta Execution Workflow for KDD. A Meta Specification workflow captures the process to specify a KDD process. Similarly, a Meta Execution workflow defines the execution engine of a KDD process. The Meta Execution workflow instances couple itself with KDD workflow instances and executes them. We build a prototype Web user interface based KDD system by utilizing the flexibility provided by Meta Workflow logic combined with the power of existent KDD tools like RapidMiner. We establish adaptable execution logic by maintaining multiple Meta Execution Workflows in our system, which provides flexibility, automation, and exception handling in KDD specification and execution. We use a Task Scheduler, which continuously looks out for any ready tasks and executes them by coupling them with Meta Execution workflow instances. We propose the execution algorithms used in our system to support this model. We also demonstrate the working of our solution with real-life scenarios using KDD and how our approach works in these cases.

Abstract

Traditional air pollution monitoring systems are bulky and expensive resulting in a very sparse deployment. In addition, the data from these monitoring stations may not be easily accessible. With the advent of internet of things (IoT) technology, millions of smart devices will be connected to each other as well as to the internet enabling easier air pollution monitoring. Low-cost portable sensors along with IoT can overcome the above two issues of traditional monitoring systems. This thesis focuses mainly on three aspects. Firstly, research, development and deployment of IoTbased dense air pollution monitoring using network low-cost sensor nodes in an Indian urban setting which is first of kind in India in terms of dense deployment and spatial coverage. Second, it deals with improving the energy consumption of the sensor nodes developed and finally, reducing the redundancy of the nodes. More specifically, a new adaptive sensing algorithm and hierarchical clustering based spatial sampling paradigm have been introduced. The results of the proposed implementations have been evaluated upon real-time deployment of the nodes. In total, ten low-cost IoT nodes monitoring particulate matter (PM), which is one of the most dominant pollutants, are developed and deployed in a small educational campus in Indian city of Hyderabad. New datasets were created in the process which are thoroughly investigated by applying various preprocessing, signal processing and clustering techniques. Different analyses such as correlation and spatial interpolation are done on the data to understand efficacy of dense deployment in better understanding the spatial variability and time-dependent changes to the local pollution indicators. For reducing energy consumption, an adaptive, non-parametric method to change the sensing rate using the maximum frequency estimate based on recent historical data. The proposed algorithm has been tested on the data collected over one year from an IoT network consisting of multiple PM sensor nodes. A performance comparison of the proposed scheme with the existing approach shows the effectiveness and performance improvement in terms of Reduction Factor (RF) and Mean Absolute Error (MAE). For removing the redundant nodes, a framework based on Hierarchical Agglomerative Clustering for deciding an optimal number of nodes and which nodes in an IoT network of sensor nodes has been proposed. The approach proposed is an end to end framework to obtain the required number of nodes and their location based on an error threshold in a deployed IoT network. The framework’s performance has been compared with the brute force approach, which entirely relies on comparing all the possible combinations. Finally the trade-off between the sensor nodes’ spatial density and the error in the spatial reconstruction for an optimal spatial understanding of PM values has been presented.

Abstract

Modern Computers were first conceptualised by Charles Babbage in the 19th century. This first concept envisioned a machine in which a program (set of instructions to be performed by computer) were provided using punched cards. Over the past century, the idea of a programmable computer became a reality. As computers became more sophisticated and powerful, it became hard to program computers using punched cards. To solve this problem, programming languages were conceptualized and implemented. In last 50 years, computer programming has evolved from being a method of instructing computers into a necessary skill. Nowadays, It is even taught in primary schools. Programming Word Problems (PWP) are used to teach Introductory Programming in schools and colleges. A PWP consists of a problem in natural language giving a background story and input/output format. The solver is expected to come up with a computer program which processes the input into expected output. As PWPs are much harder to solve, there has not been much work in automatically solving them. As a preliminary step towards solving these problems, we introduce the problem of Programming Word Problem Classification. The problem is about predicting the algorithm class to which a PWP belongs. We create two datasets of a total of 4000 problems and pose this as a single and multi label classification task. We provide a deep learning based approach which gives an accuracy of 62.7 percent. Along with the task of classifying Programming Word Problems, we introduce the problem of generation of Programming Word Problems. This problem is about automatically generating a Programming Word Problem. We propose a graph based representation for a PWP. Using the graph based representation and template based methods, we propose a method for generating programming word problems. We generate a set of Programming Word Problems and carry out human evaluation to evaluate correctness and relevance of the generated problems. The evaluations show that the generated problems are sufficiently realistic

Abstract

Text summarization is a natural language processing problem which has been investigated by the NLP community for half a century. In the era of information explosion, the community has intensified research for more sophisticated methods for automated text summarization. Attempts were made in the past to frame extractive and abstractive techniques for multidocument summarization. Extractive techniques select a subset of sentences which can approximate the summary of the input corpus of documents, while abstractive summarization techniques construct a semantic representation and are expected to generate the summary in its own learnt writing style. Extractive techniques create an intermediate representation for the target text, capturing the key textual features. Possible approaches for intermediate representation are Topic Signatures, Word frequency count, Latent Space Approaches using Matrix Factorizations, or Bayesian approaches. These intermediate representations are then used to assign scores for individual linguistic units within the text and select a subset of linguistic units which maximizes the total score as the summary of the target text. The mathematical scoring function for the summary is generally composed of components to quantify topical coverage and topical diversity. They report the accuracy in terms of a measure called the ROUGE score. Relatively less work is available on abstractive multi-document summarization in the past. Most of them utilise sub- syntactical structures which are directly extracted from input documents to generate summary sentences. Sub syntactical structures such as phrases are reorganized to create summary sentences using a method which can ensure relevant topical coverage, topical diversity and gramaticality. They also incorporate means to ensure factual accuracy so that sentences generated by the abstract summarization system are factually correct with respect to original corpus. Despite all the attempts to improve summarization in easily quantifiable dimensions such as topical coverage and diversity, a summary needs to be improved in other qualitative dimensions such as comprehensibility and coherence to match with a well-crafted human summary. Coherence represents the presence of inter-sentence structural relationships and topical continuity. Comprehensibility denotes how much a sentence is comprehensible without its context in the source document during an extractive summarization process.