Abstract

The field of pattern mining has emerged to discover potentially useful hidden knowledge (information or patterns) from the voluminous data. The rapid development of data acquisition technologies like sensors contributes to the generation of massive spatial trajectory data from the users using a global positioning system in their mobile phones, cars, watches, and others. The trajectory of the user is defined as the sequence of locations of the user during the transit. Mining patterns from the user trajectory data is an active research area. Research efforts are being made to propose approaches to process user trajectory data and propose approaches for better travel path identification, transportation management, user-activity recognition. The Google Maps system is one of the useful application that exploits user trajectory data. In this thesis, we proposed a pattern mining based framework for computing the popular paths by analyzing the user trajectory data. Furthermore, we proposed a pattern mining framework to allocate the advertisements in billboards with the goal of improving the revenue of the billboard operator. First, we investigated the problem of finding the paths based on user preferences, which we designate as popular paths. Such user preferences may include roads with relatively high thoroughfare (i.e., better for safety), smoother roads with better infrastructure (e.g., fewer potholes), roads with more facilities or points of interest nearby, lighted roads as opposed to dark and unsafe streets, roads with relatively lower crime rates, roads with better scenic beauty and so on. In practice, given that users naturally follow some of these paths significantly more as compared to other paths, the popularity of a given path often reflects such user preferences. Moreover, users typically prefer diverse paths over similar paths for gaining flexibility in path selection. Given a set of user traversals in a road network and a set of paths between a given source and destination pair, we address the problem of performing top-k ranking of the paths based on both path popularity and path diversity. We proposed a model to compute the popularity score of the given path. Given a road network, a set of user traversals, and the source and destination pair, we have proposed an efficient framework by extending the transactional framework and frequent pattern mining technique for computing the popularity score of the given path between the source and destination pair. We conducted an extensive performance evaluation with two real datasets to demonstrate the effectiveness of the proposed approach. Second, we have proposed an efficient framework to improve the billboard operator’s revenue in the billboard advertisement scenario based on the user traversal data. A billboard operator manages the ad slots of a set of billboards. Normally, a user traversal is exposed to multiple billboards. It is possible to improve the billboard operator’s revenue by meeting the advertising demands of an increased number of clients if the user encounters different ads on the billboards during the traversal. We introduce the problem of billboard advertisement allocation to clients for improving the billboard operator revenue. We have proposed an improved billboard ad allocation scheme by extending the transactional framework and coverage pattern mining approach. We conducted a performance evaluation with a real dataset to demonstrate the effectiveness of the proposed scheme. Overall, we have proposed improved approaches to have better travel experience and improve the revenue of the billboard operator. We have demonstrated the effectiveness of the proposed schemes by conducting experiments on real datasets.

Abstract

Religious sites are ubiquitous places with high cultural and social significance where people gather to perform various religious activities. The research in evolutionary archeology shows evidence for the existence of religious practices in human societies from the Middle Paleolithic era. From that time to today, religion plays a prominent role in people’s social, economic, and religious lives in many indigenous communities. A study of the religious sites in those spaces focusing on the spatial components of information has the potential to reveal possible relations with other physical factors and socio-economic processes. Due to technological advancements, many new ways are emerging for mapping, analyzing, understanding, and conserving the religious sites but rarely explored. In this thesis, we describe and demonstrate a novel approach for the in-depth exploration of 282 religious sites of Spiti Valley in Himachal Pradesh. This study is a confluence of ethnographic fieldwork methods and GIS-based computational tools to understand the religious geography by mapping the religious sites identified from 25 selected villages of Spiti Valley. Spiti Valley is a very sparsely populated Buddhist cold desert located in the northeast part of the Himachal Pradesh in Western Himalayas at the tip of the Tibetan Plateau. According to the 2011 census, Lahaul and Spiti district stands second, next to Dibang Valley of Arunachal Pradesh in India’s least densely populated districts with a population density of around two people per sq km. Spiti Valley has a share of 12, 457 people inhabited in 7, 101 square km out of the total 31, 564 people in an area of 13, 835 square km in the Lahaul and Spiti district. Despite the cold weather and most challenging living conditions, the people of Spiti somehow managed to keep the strong connection with their culture and traditions, including pre-Buddhist religious practices like worshiping mountain deities and the elements of nature from ancient times intact. The people of Spiti Valley follow Vajrayana Buddhism, similar to that of the Tibetan region. In this little part of the world up until the present day, religion has a precise role to play in the day-to-day activities of each and every individual resisting the changes across time and preserving the unique bond with nature passed down from their ancestors. This study started from an exploratory field visit to Spiti in October 2018 by 12 researchers working on the ICSSR sponsored project titled, ’Change and Continuity in a Trans-Himalayan Buddhist Community: A study of monasteries of Spiti, Himachal Pradesh.’ After that, we visited Spiti two more times to conduct fieldwork in July and September of 2019 for data collection. During the data collection, we conducted semi-structured interviews guided by the questionnaires with the help of field investigators to identify the religious sites in 25 selected villages. Then we visited each of them to collect the precise location and take photos and videos. We have combined all the information from our field visits, interviews, census reports, historical gazetteers, traveler tales, and others to create a spatial dataset of religious sites that is much more than the sum of its parts. Building on the dataset of religious sites created from the fieldwork, we have presented an eightfold model for categorizing the religious sites based on the similarities and dissimilarities in the structure, architecture, features, functions, and purpose. Among the eight classes, we have conducted a detailed analysis of Monasteries and Chorten (mChod-rTen). While looking at monasteries, we gave a brief introduction to Spiti’s five big monasteries, i.e., Tabo, Dhankhar, Kungri, Tangyud, and Kee Monastery. Then we created maps to trace the role of monasteries in the administrative divisions and traditional fiscal system given in the 19th-century works by some of the pioneering scholars who worked on Spiti. While looking at Chorten, we start with a historical background; then, we will classify 132 chorten based on the architectural style to understand the symbolism behind different types located at different places in Spiti. Lastly, we will discuss the correlations in the distribution of Chorten and land usage patterns. We have built a couple of Web GIS Applications to take users on a virtual tour to the religious sites along with images and other descriptive information. We are also building a mobile application to empower the people of Spiti and others as well for conserving the traditional knowledge in the form of geotagged images and short text descriptions.

Abstract

To perform any task, humans often rely on certain amount of broad background knowledge obtained from sources outside the context of the task. Similarly, machine learning models can also leverage external knowledge to perform well on a task. External knowledge sources can induce knowledge from across the web. Hand-crafted features are used to solve a wide range of natural language processing (NLP) tasks ranging from part-of-speech tagging to machine translation and sentence simplification. Hand-crafted features generated from external knowledge sources induce broad knowledge from across the web. Using hand-crafted features computed from external knowledge sources in addition to the features computed from the data alone improves the performance of an approach significantly due to the external knowledge induced. Recently, deep learning methods have shown impressive gains on many NLP tasks by using neural networks based on dense vector representations. The deep learning approaches try to automatically identify and learn useful features to better represent the data and solve a problem. They can represent huge amounts of data and draw complex decision boundaries using large neural networks. Deep learning algorithms seek to exploit the unknown structure in the input distribution to discover good representations, often at multiple levels, with higher-level learned features defined in terms of lower-level features. Most of the works either use shallow models (with hand-crafted features) or deep learning methods to solve NLP tasks. As deep learning approaches are giving superior performances over methods employing only hand-crafted features, they are being worked upon the most these days. Even though, the deep learning based approaches can automatically find patterns for a task and underlying distribution of data, the hand-crafted features are subjective. Deep learning based models cannot find some patterns which are easily captured by hand-crafted features generated from data and external knowledge bases. Thus, hand-crafted features for a given problem are still important. They enhance the performance of deep learning based algorithms. In most of the NLP tasks, the hand-crafted features are mainly being used in shallow models like SVM, logistic regression, etc. but not in deep learning models and thus missing out the patterns which can be easily captured by hand-crafted features. In this thesis, we propose novel approaches to Predict Answer Quality in Community Question Answering Forums and to Detect Sub-Topics in a tweet. We use external knowledge sources to generate more hand-crafted features in addition to the ones generated from the data alone to generate better representation of the data. Due to these knowledge sources, a lot of information from the web was induced resulting in enhanced performance for both the tasks. We use the hand-crafted features generated from both the data and external knowledge sources in our novel approach to detect sub-topics in tweets. Further, we compute handcrafted features from both the data and external knowledge sources and feed these hand-crafted features as inputs to a deep learning model in our novel approach, “Deep Feature Fusion Network (DFFN)”, to predict answer quality in community question answering forums. In addition to the hand-crafted features, the question and answer representations are given as inputs to the deep learning model. DFFN combines the hand-crafted features in the deep learning model with the processed output of the question and answer representations to predict the quality of an answer. This fusion allowed us to leverage the advantages of both hand-crafted features and deep learning based models and achieve significant improvement. We outperform the all baseline and state-of-the-art approaches for both the tasks discussed in this thesis

Abstract

The development of ultra-low power LSIs is a promising area of research in microelectronics. Such LSIs would be suitable for use in power-aware LSI applications such as portable mobile devices, implantable medical devices, and smart sensor networks. From compact sensors to advanced multi-core smartphones, various IoT devices hold precision and power efficiency as critical factors. Efficient management of switch on-off time acts as a key to minimize the power consumption. Therefore, maintaining accurate time is crucial for such type of devices. This is embraced by an on-chip RTC to retain reliable information of event occurrences. In addition, RTC’s interrupt management to alert the micro-controller host evaluates the robustness of the device. An RTC maintains a precise track of time by counting the oscillator cycles. Ultimately, the oscillation frequency (32.768KHz) is bounded by a speculation of time resolution and low power. Although the stable and precise nature of crystal oscillators (XOs) serve the purpose, they have few downsides. For being bulky, expensive and having high power consumption, the replacement of XOs is highly recommended. Focused research has been carried out for years on CMOS based oscillator architectures with sophisticated compensation techniques for reducing PVT variations. However, boosting the stability at low frequencies with low complexity, area and power have been a major challenge for next-generation IoT applications. This work presents a novel PVT-invariant CMOS relaxation oscillator for Real-Time Clock (RTC) applications. The proposed design works in a core voltage domain of SoC. The introduced self-adaptive compensation loop dynamically modifies the time constant of the oscillator core on sensing the process variation. Moreover, the design is accompanied by a digital calibration unit for further process compensation. The replacement of the resistor with a voltage-biased MOSFET has greatly enhanced the area efficiency. The required voltage and current bias in the circuit are generated through a novel current mixing technique which plays a crucial role in enhancing the performance of the system. Besides, the introduced supply independent bias circuit has greatly improved the supply regulation of the oscillator frequency

Abstract

In the last few decades, we can see our day-to-day life being dependent on software programs. The digital revolution in the software industry has been progressing at a staggering rate. Thousands of software applications like web browsers, search engines, simulators (aviation), etc. are being developed by the different enterprises in various domains that are changing every facet of our lives. Most of these software programs are written in fast, low-level and memory-unsafe languages like C/C++. These memory unsafe languages rely on the programmer’s expertise for memory management of objects created during runtime and hence, leads to some memory-corruption bugs like buffer-overflow [1], dangling pointers [2], etc. Later, these bugs have the potential to be exploited by some malicious users compromising the software security. These bugs can cause serious security problems, such as confidential information leakage, system crashes, user permission changes, etc. These bugs (when exploited) have an adverse effect on both consumers and enterprises in terms of money, time and even human lives. In such a scenario, it becomes extremely important to catch these bugs apriori and mitigate before any exploitation. This thesis helps in identifying and reporting a class of these bugs, which could breach some confidential information out of the software (aka information leaks).Fuzzing is arguably the most effective security testing technique to find memory-corruption bugs in applications. However, fuzzing is effective in finding specific bugs that result in some observable effects, like crash. Consequently, information leak bugs often remain undetected by fuzzing, in spite of their serious effect on the security of the application. In order to help fuzzing detect such bugs, address sanitiser (LLVM/GCC Asan option) based approaches are employed. However, such an option is available only when we have the source code of the application available. Other binary-only solutions, like Valgrind, have limited ability to detect information leaks (e.g., stack variables are not covered). In this thesis, we investigate the application of dynamic taint flow analysis(DTA) to detect information leak in binary executables. In this approach, we leverage DTA to track data and pointer taintedness and device a set of rules to infer when there could be a possible information leak. Our method is suitable for typical desktop applications (for example, image and document viewers) that parse and display the information contained in the provided input. In order to show the effectiveness of the proposed technique, we build a dynamic binary analysis (DBA) tool - TailFinder (Taint Assisted Info Leak Finder) in C++ using PIN dynamic binary instrumentation framework and evaluate it on real-world applications. On such applications, we find information leaks that have known CVEs1 , thereby showing the applicability of the proposed technique. We also present, how we can integrate these tools with fuzzing to find possible information leaks apriori.

Abstract

Graph centralities play a crucial role in graph/network analytics to help us determine the importance of nodes in real-world graphs. Betweenness centrality is one such metric and is indeed the most popularly used centrality measure. Algorithms to calculate Betweenness centrality have been studied in the literature for a long time, the latest and most profound one being the Brandes Algorithm. Although many optimizations of the Brandes algorithm exist, very few of them address the problem of finding centrality in a continually evolving graph i.e, graphs that change due to the addition/deletion of nodes/edges. The majority of the graphs where these metrics are required are dynamic graphs. In such scenarios, having techniques to update centrality quickly and efficiently becomes paramount. There have been works on updating centrality on the addition/deletion of a single node/edge. However, the techniques become computationally expensive when updates happen in bulk. We build upon the work done on single edge betweenness centrality update and present a novel parallel algorithm to process a batch of edges at once. We also introduce some new optimization techniques along the way that exploits specific structural properties of graphs. We implement our algorithm on both multi-threaded CPUs and GPU and provide detailed analysis of our algorithm across CPU, GPU for varied batch edge updates on a variety of graph datasets spanning major application areas.

Abstract

With the growing use of computer vision tools in wide-ranging applications, it becomes imperative to understand and resolve issues in computer vision models when they are used in production settings for various applications. In particular, it is essential to understand that the model can be wrong quite frequently during deployment. Developing a better understanding of the mistakes made by a model can help mitigate and handle them without catastrophic consequences. To investigate the severity of mistakes, we first explore this in a simple classification setting. Even in this setting, understanding the severity of mistakes of difficult to quantify, especially since manually defining pairwise costs does not scale well for large-scale classification datasets. Therefore most works have used class taxonomies/hierarchies, which allow pairwise costs to be defined using graph distances. There has been increasing interest in building deep hierarchy-aware classifiers, aiming to quantify and reduce the severity of mistakes and not just count the number of errors. However, most of these works require the hierarchy to be available during training and cannot adapt to new hierarchies or even small modifications to the existing hierarchy without having to re-train the model. We explore a different direction for hierarchy-aware classification – amending mistakes by making post-hoc corrections by resorting to the classical Conditional Risk Minimization(CRM). Surprisingly, we find that this method is a far more suitable alternative than the works on deep hierarchy-aware classification; CRM preserves the base model’s top-1 accuracy and brings the most likely predictions of the model closer to the ground truth and is able to provide reliable probability estimates, unlike hierarchy-aware classifiers. We firmly believe that this serves as a very strong and useful baseline for future exploration in this direction. We turn our attention to a crucial problem in many video processing pipelines: visual(single) object tracking. In particular, we explore the long-term tracking scenario where given a target in the first frame of the video; the goal is to track the object throughout a (long) video during which the object may undergo occlusion, vary in appearance, or go out-of-view. The temporal aspect of videos also makes it an ideal scenario to understand the accumulation of errors that would not be otherwise seen if every image is independent. We hypothesize that there are three crucial abilities that a tracker must possess to be effective in the long-term tracking scenario, namely Re-Detection, Recovery and, Reliability. The tracker must be able to re-detect the target when the target goes out of the scene, and returns must recover from failure and track an object contiguously to be of practical utility. We propose a set of novel and comprehensive experiments to understand each of these aspects which give a thorough understanding of the strengths and limitations of various state-of-the-art tracking algorithms. We finally visit the problem of multi-object tracking. Unlike the problem of single-object tracking where the target is initialized in the first frame, the goal here is to track all objects of a particular category(such as pedestrians, vehicles, animals etc.). Since this problem does not require user-initialization, it has found use in wide-ranging real-time applications such as autonomous driving. The typical multiobject tracking pipeline follows the tracking-by-detection paradigm, i.e. an object detector is first used to detect all the objects in the scene. These detections are linked together to form the final trajectories using a combination of Spatio-temporal features and appearance/Re-Identification(ReID) features. The appearance features are extracted using a Convolutional Neural Network(CNN) trained on a corpus of labelled videos. Our central insight is that only the appearance model requires labelled videos in the entire pipeline, while the rest of the pipeline can be trained with just image-level supervision. Inspired by the recent successes in unsupervised contrastive learning which enforces the similarity in feature space between an image and its augmented version, we resort to a simple method that leverages the spatio-temporal consistency in videos to generate “natural” augmentations which are then used as pseudo-labels to train the appearance model. When integrated into the overall tracking pipeline, we find that this unsupervised appearance model can match the performance of its supervised counterparts in reducing the identity switches present in the trajectories, thereby saving costly video annotations that are impractical to scale up without sacrificing performance.

Abstract

Scene analysis has been a topic of great interest in computer vision. Humans are the most important and most complex subject involved in scene analysis. Humans exhibit different forms of expressions and behaviour with its environment. These interactions with its environment have been in study for a long time and to interpret these interactions various challenges and tasks have been identified. We focus on two tasks in particular: Head Pose estimation and Emotion recognition. Head poses are an important mean of non-verbal human communication and thus a crucial element in understanding human interaction with its environment. Head pose estimation allows a robot to estimate the region of focus of attention for an individual. Head pose estimation requires learning a model that computes the intrinsic Euler angles for pose (yaw, pitch, roll) from an input image of the human face. Annotating ground truth head pose angles for images in the wild is difficult and requires ad-hoc fitting procedures (which provides only coarse and approximate annotations). This highlights the need for approaches which can train on data captured in a controlled environment and generalize on the images in the wild (with varying appearance and illumination of the face). Most present day deep learning approaches which learn a regression function directly on the input images fail to do so. To this end, we propose to use a higher level representation to regress the head pose while using deep learning architectures. More specifically, we use the uncertainty maps in the form of 2D soft localization heatmap images over five facial keypoints, namely left ear, right ear, left eye, right eye and nose, and pass them through a convolutional neural network to regress the head-pose. We show head pose estimation results on two challenging benchmarks BIWI and AFLW and our approach surpasses the state of the art on both the datasets. We also propose a synthetically generated dataset for head pose estimation. Emotions are fundamental to human lives and decision-making. Human emotion detection can be helpful in understanding human mood, intent or choice of action. Recognizing emotions from images or video accurately is not easy for humans themselves and for machines it is even more challenging as humans express their emotions in different forms and there is a lack of temporal boundaries among emotions. Facial Expression Recognition has remained a challenging and interesting problem in computer vision. Despite efforts made in developing various methods for facial expression recognition, existing approaches lack generalizability when applied to unseen images or those that are captured in wild setting (i.e. the results are not significant). We propose use of facial action unit’s soft localization heatmap images for facial expression recognition. To account for lack of large well labelled dataset we propose a method for automated spectrogram annotation where we use two modalities(visual and textual) used in expression of emotion by humans to label one other modality(speech) for emotion recognition.

Abstract

The advent of modern machine learning and deep learning methods have revolutionized various fields such as computer vision, natural language processing, speech recognition, etc. In the the past decade these methods have made a profound impact in the field of natural science. Particularly, the computations involved in the field of molecular science have been greatly transformed with the advent of machine learning. These changes have resulted in tremendous reduction of time and cost involved in tasks such as molecular generation and property prediction, which are two crucial steps involved in the process of molecular design. In this thesis, two studies on in each of these is reported. First part of the thesis presents a deep learning based inorganic material generator (DING) framework consisting of a generator module and a predictor module. The generator module is developed based upon conditional variational autoencoders (CVAE) and the predictor module consists of three deep neural networks trained for predicting enthalpy of formation, volume per atom and energy per atom chosen to demonstrate the proposed method. The predictor and generator modules have been developed using a one-hot key representation of the material composition. A series of tests were done to examine the robustness of the predictor models, to demonstrate the continuity of the latent material space, and its ability to generate materials exhibiting target property values. The DING architecture proposed in this paper can be extended to other properties based on which the chemical space can be efficiently explored for interesting materials/molecules. Second part of the thesis presents an interpretable deep learning method based on graph networks that accurately predict solvation free energies of small organic molecules. The proposed model CIGIN, comprising of three phases, namely message passing, interaction and prediction is able to predict solvation free energies in any generic organic solvent with a mean absolute error of 0.16 kcal/mol. In terms of the accuracy, the CIGIN model outperforms all the proposed machine learning based models so far. The atomic interactions predicted in an unsupervised manner is able to explain the trends of free energies consistent with chemical wisdom. Further, the robustness of the machine learning based model has been tested thoroughly and its capability to interpret the predictions has been verified with several examples.

Abstract

Centrality plays an essential role in identifying the essential nodes in social networks. This thesis proposes a new flavor of centrality, where we focus on farness and closeness centrality, which identify closer nodes in a network.Since closeness-centrality is a fundamental problem in graph theory, several algorithms exist for this problem for both static and dynamic environments. Recent algorithms for computing centrality have relied heavily on breadth-first search (BFS) traversals of the input graph. Usually, a significant portionof the algorithm’s overall run-time is spent on BFS operations. We have developed a framework (called BRICS) based on the graph’s structural properties, which reduces the time taken for a single BFS traver-sal and reduces the overall number of traversals. Since finding the exact values of centrality requiresconsiderable computational time, we have devised an estimation algorithm with a reasonable trade-offbetween accuracy and speedup.Additionally, we have created a GPU algorithm to update closeness-centrality in a dynamic settingwhen a batch of edges is added or deleted by extending Sarıy ̈uce et al. (CLUSTER 2013), an incremen-tal algorithm (single edge update) to the batch update.We have implemented our algorithm in Nvidia Tesla V100 GPU parallel architecture with 80 SMXs.We experimented on five different types of real-world graphs and varying the optimization techniques to achieve the max speed up. Our experimental results show that we were able to achieve a maximumof 12.54x speedup on computing fairness centrality and 53x on updating closeness-centrality in the dynamic setting.