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.

Abstract

Empathy, a complex social skill, allows for the ability to understand the emotional and cognitive states of another. In general, empathy is crucial in the social world and for survival. Several studies have demonstrated that the default mode network (DMN) is involved in the process of internal mental simulations (also known as mind wandering) - an aspect significant for empathetic response. Researchers have found an overlap in brain regions between the social networks and the DMN. Since the DMN is activated during the mind wandering process, most of empathy literature has examined the DMN during resting state. Therefore in this thesis, we investigate the functional connectivity differences in resting state DMN and empathy-task DMN. In this study, we apply a novel time-frequency filter method on the BOLD signal to investigate the FC of the DMN. The aim of this thesis is to demonstrate the role of the DMN in empathetic processes and to further identify the time-frequency characteristics of the DMN activations during free-viewing emotional movie clips. Specifically, we use movie clips because research has shown more intense emotions being evoked in participants during dynamic stimuli vs static stimuli. And since we want to capture the complex psychological process of empathy, we decided to use emotional movie clips to portray the naturalistic complexity of human interactions. It must be noted that the time-frequency technique used in this thesis (the single frequency filter bank) provides a better resolution compared to traditional approaches such as sliding window. Using this novel technique, analysis on two sets of fMRI data were conducted to examine the time-frequency dynamics. To the best of our knowledge, this is the first study to explore the time-frequency characteristics of the DMN in empathy tasks. In the first experiment, fMRI response signals from the three short diverse movie clips (Disney, Green, and Taare) were analyzed. Before the stimuli was presented, resting state data of 3 minutes was also recorded for the 8 participants. Specific scans which consisted of the most emotional scenes were chosen to conduct the comparative analysis. The results from this preliminary investigation demonstrated differences in the activations between empathetic task vs resting state. This preliminary study corroborates findings from previous studies. For example, we found highly skewed power distributions where most power was at the lowest frequencies. This has been shown in previous research as well

Abstract

Machine Translation is a sub-field of Computational Linguistics that deals with systems that automatically translate text or an utterance from one language into another. The field has made huge strides, from rule-based translators to the now state-of-the-art neural machine translators. However, translators in the general domain are far from achieving human parity. At this stage, even for state-of-the-art translators, a human needs to check the output and post-edit it. The aim therefore, is to continuously improve the machine translator so that the post-editing effort reduces. Guided by this aim and a will to make translators more complete, I identify one area where even state-of-the-art machine translators perform poorly – translating idiomatic and non-compositional constructions. I establish that these constructions are infrequent in the data translators are trained and tested on, which could be the primary reason for the inadequacy of their translations. To improve the translation adequacy of non-compositional constructions, I propose a rule-based pre-processor that detects these constructions in the input sentence and simplifies them into more compositional constructions – which are far more likely to translate adequately. I start by compiling a list of constructions, which range from fully lexical and rigid constructions to constructions with slots constrained by parts of speech, all the way to fully syntactic constructions. Using examples of sentences that have these constructions, I evaluate five English–Hindi NMT systems and report that their performance is thoroughly inadequate when translating non-compositional constructions. To understand the capabilities that a pre-processor would need to solve this issue, I conduct an analysis of these constructions, and come up with features that a rule-based pre-processor needs to detect and simplify the constructions. This theoretical analysis of rules is followed by a description of the actual pre-processor I created as part of this project and its rule formalism. The pre-processor is then systematically evaluated for English – Hindi translation. I report a high accuracy of construction detection in English based on manually written rules, as well as a significant improvement in the quality of translation in Hindi after the non-compositional constructions in the English input text are preprocessed into more compositional constructions. I conclude by discussing the results of this evaluation and the errors made by the pre-processor, some limitations of this solution, as well as possible future work to extend this system and improve it. The pre-processor is open-source and its code is available at https://github.com/khannatanmai/rule-based-preprocessing-mt.

Abstract

Gold Nanoparticles (AuNPs) are significantly important in the field of biomedical applications and are being used to diagnose and treat various important diseases such as cancer. The properties of AuNPs strongly depend on the size, structure, and morphology. Experimental conditions or mechanism which lead to specific morphology have not been clearly understood; therefore, it is of utmost importance to understand the influence of experimental parameters, geometrical properties on the growth of AuNPs and mechanism which lead to different morphology of AuNP. Modeling the atomistic behavior of nanoparticles with the timescale that approach actual experiments and represents the true atomistic behavior is a challenging task in the field of computational chemistry. In the literature survey, methods like Molecular Dynamics (MD), phase-field method, level-set method, adaptive mesh techniques, random walks with adaptive step sizes have been used to model the atomistic behavior of nanoparticle. This thesis uses the Kinetic Monte Carlo (KMC) scheme along with greedy nearest neighbor approaches to make the computation less expensive for modeling the true atomistic behavior of AuNP in the solution of gold ions with the timescale that approaches the actual experiments. Three processes namely adsorption, desorption, and surface diffusion have been considered. This model is further used to study the effects of different experimental parameters that influence shape and size and also to find out geometrical trends of different initial seed shape over time. AuNP of different morphology like the truncated octahedron, cuboctahedron, truncated cube, cube, rhombic dodecahedron, and the sphere was synthesized by the model at the certain specific experimental condition. This study will help scientists, nanotechnologists, and experimentalists to understand the mechanism and conditions to synthesize specific morphology

Abstract

Language identification (LID) refers to the task of figuring out the language in a given speech utterance. The task of Language Identification is very important in development of spoken dialogue system especially for multilingual society like India. In this work, an implicit approach has been used for the task of language identification. Combination of MFCC feature vector and RCC feature vector has been explored for Indian Language identification (LID) task. MFCC represents the vocal tract information and RCC represent the excitation source information which are complementary to each other. To combine these two complementary features different fusion based approaches has been used. Decision level fusion based approach and feature level fusion based approach has been explored for this task. Deep neural network (DNN) framework has been used as a classifier. DNN models are very popular for the task of speaker identification and other speech signal processing related task. In decision level fusion different fusion techniques such as Min, Max, Average, and Min-Max has been used. In feature level fusion approach canonical correlation analysis(CCA) has been performed to combine MFCC feature vector and RCC feature vector. In this algorithm only one DNN classifier is trained which has improved computation time and accuracy. Several experiments has been performed on 13 Indian languages data set. This data set consists of 120 hours of training data and 30 hours of testing data. Here, EER is equal error rate which is used as the performance metric. Lower the value of EER, higher the accuracy of LID performance. Results are compared with state of art I-vector based approach. Decision level fusion based approach gives an equal error rate of 9.64% as compared to an equal error rate of 10.18% of I-vector based approach. CCA based feature level fusion gives an equal error rate of 9.19% as compared to average EER of 9.64% of decision level fusion approach. From the results it is proved that Fusion based approaches performed better as compared to the individual feature vector based approaches.