Abstract

This thesis is driven by the idea of advancing computing to address critical challenges in the domain of education. In particular, focuses on facilitating the design of educational technologies for scale and variety, where scale is the number of systems to be developed and variety stems from a diversified range of instructional designs [consisting of varied goals, processes, content, teacher styles, learner styles and so on]. More specifically, we address this challenge in the context of adult literacy in India [287 million learners spread across 22 Indian languages and instructional designs developed by 32 state resource centers spread across India]. How to address these challenges and design educational technologies that adhere to instructional design principles, provide flexibility and are less effort intensive? This thesis presents an approach for design of educational technologies for scale and variety in education. The crux of this approach is the application of software engineering ideas like patterns, ontologies and software product lines without losing focus on instructional design. This approach consists of (i) modeling different aspects of instructional design like goals, process and content using patterns and mapping them to commonly accepted approaches like Bloom’s taxonomy and Merrill’s first principles of instruction (ii) representing these patterns using an ontology based framework that systematically captures different aspects of instructional design (iii) based on the modeling of domain through patterns and ontologies, this thesis presents a pattern oriented software product lines approach for modeling a family of instructional designs and for further semi-automatically generating eLearning Systems based on these instructional designs. The core concern of quality of instruction is mitigated by deriving patterns and ontologies from well-established and field tested methodologies and instructional material under the aegis of National Literacy Mission Authority of Government of India. Finally, we demonstrate how software tools built on top of our approach [http://rice.iiit.ac.in] can be used to semi-automatically generate eLearning Systems for flexible instructional designs and multiple Indian languages. We see that the proposed approach for scale and variety based on patterns, ontologies and software product lines could be applicable beyond adult literacy to the broad spectrum of education, and in particular to skill and school education.

Abstract

This thesis is driven by the idea of advancing computing to address critical challenges in the domain of education. In particular, focuses on facilitating the design of educational technologies for scale and variety, where scale is the number of systems to be developed and variety stems from a diversified range of instructional designs consisting of varied goals,processes, content, teacher styles, learner styles and so on]. More specifically, we address this challenge in the context of adult literacy in India [287 million learners spread across 22 Indian languages and instructional designs developed by 32 state resource centers spread across India]. How to address these challenges and design educational technologies that adhere to instructional design principles, provide flexibility and are less effort intensive? This thesis presents an approach for design of educational technologies for scale and variety in education. The crux of this approach is the application of software engineering ideas like patterns , ontologies and software product lines without losing focus on instructional design. This approach consists of (i) modeling different aspects of instructional design like goals, process and content using patterns and mapping them to commonly accepted approaches like Bloom’s taxonomy and Merrill’s first principles of instruction (ii) representing these patterns using an ontology based framework that systematically captures different aspects of instructional design (iii) based on the modeling of domain through patterns and ontologies, this thesis presents a pattern oriented software product lines approach for modeling a family of instructional designs and for further semi-automatically generating eLearning Systems based on these instructional designs. The core concern of quality of instruction is mitigated by deriving patterns and ontologies from well-established and field tested methodologies and instructional material under the aegis of National Literacy Mission Authority of Government of India. Finally, we demonstrate how software tools built on top of our approach[ http://rice.iiit.ac.in] can be used to semi-automatically generate e Learning Systems for flexible instructional designs and multiple Indian languages. We see that the proposed approach for scale and variety based on patterns, ontologies and software product lines could be applicable beyond adult literacy to the broad spectrum of education, and in particular to skill and school education.

Abstract

Today, general-purpose GPUs (GPGPUs) have become very ubiquitous and available in something as simple as a personal laptop. These GPUs can be utilized to a great extent for their huge parallelism such as NVIDIA GT520 having 48 cores and GTX580 having 512 cores that we use for our implementations. On such devices Single Instruction Multiple Data(SIMD) operations can be performed using NVIDIA CUDA programming model. GPUs for general purpose computing has brought forth several success stories with respect to time taken, cost, power, and other metrics. However, accelerator based computing has significantly relegated the role of CPUs in computation. As CPUs evolve and also oer matching computational resources, it is important to also include CPUs in the computation. We call this the hybrid computing model. Indeed, most computer systems of the present age oer a degree of heterogeneity and therefore such a model is quite natural. With such a hybrid model in mind, in this thesis, we try to explore ways to harvest the benefits of hybrid computing. In this thesis we explore two such ways namely Dynamic Load Balancing where we split the work among GPU and CPU dynamically and the other technique is graph pruning to recursively remove 1-degree nodes before applying an algorithm on a much smaller resultant graph and later post-processing the results to the complete graph. The first two chapters propose hybrid solution to two of major application in GPU computing such as Lattice Boltzmann Method(LBM), a class of computational uid dynamic problem and Ray Casting, an image processing primitive.Later we propose a light-weight, low overhead, and completely dynamic framework that addresses the load balancing problem of heterogeneous algorithms.Our framework will be applicable for workloads which have a few simple characteristics such as having a collection of largely independent tasks that are easily describable. To show the efficacy of our framework, we consider two different heterogeneous computing platforms, and two of the above mentioned workloads: LBM and ray casting. For each of these workloads, we demonstrate that using our framework, we can identify the proportion of work to be allotted to each device up to 8% on average with reference to the base hybrid solution. Further, solutions using our framework require no more than 5% additional time on average compared to best possible load assignment obtained via empirical search. In the later part of the thesis we introduce graph pruning as a technique that aims to reduce the size of the graph. Certain elements of the graph can be pruned depending on the nature of the computation. Once a solution is obtained on the pruned graph, the solution is extended to the entire graph. We apply the above technique on a very fundamental graph algorithm: Single Pair Shortest Path that we later generalize to solve All Pairs Shortest Paths (APSP). To validate our technique, we implement our algorithms on a heterogeneous platform consisting of a multicore CPU and a GPU. On this platform, we achieve an average of 35% improvement compared to state-of-the-art solutions. Such an improvement has the potential to speed up other applications reliant on these algorithms.

Abstract

In recent years, the amount of information generated and stored is inconceivable. A plethora repsesentations are available to store such kind of data, with graphs being one of the most efficient ap- proaches, useful for studying and analysing various attributes of data. Considering amount of data to process, parallel computing is the most suitable option but many state of the art algorithms are not ef- ficient enough to take maximum advantage of available architectures. Hence researchers are focusing on development and enhancement of parallel graph algorithms. Parallel graph algorithms continue to attract a lot of attention in research given their applications to several fields of sciences and engineering. However, efficient design and implementations of graph algorithms on modern many-core accelerators has to contend with a host of challenges including not being able to reach full memory system through-put and irregularity. Of late, focusing on real-world graphs, researchers are addressing these challenges by using decomposition and preprocessing techniques guided by the structural properties of such graphs. In this direction, we present a new algorithm for obtaining an ear decomposition of a graph. Our implementation of the proposed algorithm on an NVidia Tesla K40c and Intel Xeon E5-2650 improves the state-of-the-art by a factor of 2.3x and 2.02x on average respectively on a collection of real-world and synthetic graphs. The improved performance of our algorithm is due to our proposed characterization that identifies edges of the graph as redundant for the purposes of an ear decomposition. We then study an application of the ear decomposition of a graph in computing the betweenness-centrality values of nodes in the graph. We use an ear decomposition of the input graph to systematically remove nodes of degree two. The actual computation of betweenness-centrality is done on the remaining nodes and the results are extended to nodes removed in the previous step. We show that this approach improves the state-of-the-art for computing betweenness-centrality on an NVidia K40c GPU by a factor of 1.9x on average over a collection of real-world graphs.

Abstract

Increasing complexity and diminishing size of wireless devices often lead to quick depletion of en- ergy stored in batteries with limited capacity. In certain applications, sensors are often installed at loca- tions that are hazardous or inaccessible, which makes the battery replacement or recharging impossible. This could often lead to interruptions in the operation of the network. In such scenarios, transferring energy to these devices wirelessly plays a significant role in prolonging the life of the sensor networks. Since most of these devices perform wireless communication, it is of practical interest to consider the transfer of energy to the device using the same electromagnetic wave that is used for communication. This technique, termed ‘simultaneous wireless information and energy transmission (SWIET)’, holds great promise in many applications. SWIET enables joint transfer of data and energy to the receiver, which performs both information decoding and energy harvesting simultaneously from the same re- ceived electromagnetic wave. This technique will be central to various emerging technologies and has gathered considerable attention recently. Many current and future technologies like wearable devices, sensors used in hazardous areas, 5G and beyond, etc., are expected to use SWIET technique. In this work, we develop transceiver algorithms for the application of SWIET in two types of com- munication networks. In the first scenario, we consider SWIET in a wireless network employing multi- carrier transmission technique. The transmitter is designed to support both information and energy transfer simultaneously. The network employs orthogonal frequency division multiplexing (OFDM) for signal transmission. Receivers are capable of decoding the information as well as harvesting energy from the same received signal. In this context, we address the problem of the optimal transceiver design for maximizing the weighted sum-rate under a constraint on harvested energy and for maximizing the total harvested energy under constraint on minimum rate. In the second scenario, we consider SWIET in a cooperative network employing amplify-and-forward (AF) relays. The source node, relays, and the destination node, are all capable of handling both data and energy transmission simultaneously. In this context, apart from the optimal transmit and receive processing, we also consider the problem of optimal selection of a relay out of L given relays to maximize the rate and the harvested energy. We investigate the problems for both time switching (TS) and power splitting (PS) schemes. In TS, the receiver harvests all the energy from the received signal for a fraction of the block duration; while for the remaining duration, the received signal is utilized for information decoding. On the other hand, a fraction of the received signal power is used for harvesting energy and the remaining power is used for decoding information simultaneously, in case of PS. We have developed optimal and reduced complexity sub-optimal algorithms to solve the problems described above and have analyzed the performance in various scenarios. It is assumed that the channel state information (CSI) is perfectly known for all the scenarios. The benefits of proposed designs under different operating conditions and parameter values are illustrated via numerical simulations.

Abstract

The thesis is based upon two important concepts of foundation of quantum mechanics, locality and complementarity. Violation of locality and presence of complementarity are key features of “quantumness” of a system distinguishing it from all classical systems that conform to the idea of local realism. The first part of the thesis is devoted to the investigations of issues related to non locality and complementarity of quantum correlations in multipartite scenarios, in particular, the Svetlichny model. Our investigations are based upon device independent approach valid irrespective of any theoretical setting. We show that there exists a complementary relationship in terms of the genuine non-locality as a principle between the system and subsystems. We investigate Svetlichny games in a multiparty binary input and output scenario with a threshold value of the winning probability as a signature of genuine multiparty non locality. We analytically show that in the Svetlichny games setup, there exists complementary relationship between Svetlichny correlations of n party versus Svetlichny correlations of k ≤ n party which arise due to no-signaling principle. In other words, the violation of locality for multiparty systems can not be arbitrary, it comes at the price of non violation of locality in the reduced subsystem. The latter is one of the major findings of the thesis. In addition to Svetlichny games, we consider many non local games like Mermin games, Bancal et. al’s IP, Guess Your Neighbors Input game and present the details of our numerical investigations in case of No-signaling and quantum correlations. We demonstrate that the numerical findings support of our main result obtained analytically. In the second part of the thesis, we have considered hypothetical yet theoretically possible situation, by considering the existing models of closed time like curves. It had been noted in the literature earlier that these models of closed time like curves give enormous power to achieve things which are computationally and physically impossible with the existing structure of quantum mechanics in the causality respecting region. Specifically, we show that it is possible to create an arbitrary superposition of unknown states in case CTCs are invoked in the quantum framework which is otherwise impossible. This is an important finding which should be added to the list of no-go results which become permissible by the allowance of closed time like curves in quantum framework.

Abstract

Reasoning about objects in images and videos using 3D representations is re-emerging as a popular paradigm in computer vision. Specifically, in the context of scene understanding for roads, 3D vehicle detection and tracking from monocular videos still needs a lot of attention to enable practical applications. Current approaches leverage two kinds of information to deal with the vehicle detection and tracking problem: (1) 3D representations (eg. wireframe models or voxel based or CAD models) for diverse vehicle skeletal structures learnt from data, and (2) classifiers trained to detect vehicles or vehicle parts in single images built on top of a basic feature extraction step. In this paper, we propose to extend current approaches in two ways. First, we extend detection to a multiple view setting. We show that leveraging information given by feature or part detectors in multiple images can lead to more accurate detection results than single image detection. Secondly, we show that given multiple images of a vehicle, we can also leverage 3D information from the scene generated using a unique structure from motion algorithm. This helps us localize the vehicle in 3D, and constrain the parameters of optimization for fitting the 3D model to image data. We show results on the KITTI dataset, and demonstrate superior results compared with recent state-of-the-art methods, with upto 14.64 % improvement in localization error.

Abstract

In recent times, there have been an increase in Optical Character Recognition (OCR) solutions for recognizing the text from scanned document images and scene-texts taken with the mobile devices. Many of these solutions works very good for individual script or language. But in multilingual environment such as in India, where a document image or scene-images may contain more than one language, these individual OCRs fail significantly. Hence, in order to recognize texts in the multilingual document image or scene-image, we need to, manually, specify the script or language for each text blocks. Then, the corresponding script/language OCR is applied to recognize the inherent tasks. This is a step which is preventing us to move forward in the direction of fully-automated multi-lingual OCRs. This thesis presents, two effective solutions to identify the scripts and language of document images and scene-texts, automatically. Even though, recognition problems for scene texts has been highly researched, the script identification problem in this area is relatively new. Hence, we present an approach which represents the scene-text images using mid-level strokes based features which are pooled from the densely computed local features. These features are then classified into languages by using an offthe-shelf classifier. This approach is efficient and require very less labeled data for script identification. The approach has been evaluated on recently introduced video script dataset (CVSI). We also introduce and benchmark a more challenging Indian Language Scene Text (ILST) dataset for evaluating the performance of our method. For script and language identification in document we investigate the utility of Recurrent Neural Network (RNN). These problems have been attempted in the past with representations computed from the distribution of connected components or characters (e.g. texture, n-gram) from a larger segment (a paragraph or a page). We argue that, one can predict the script or language with minimal evidence (e.g. given only a word or a line) very accurately with the help of a pre-trained RNN. We propose a simple and generic solution for the task of script and language identification without any special tuning.This approach has been verified on a large corpus of more that 15.03M words across 55K documents comprising 15 scripts and languages. The thesis aims to provide a better recognition solutions in document and scene-texts space by providing two simple, but effective solutions for script and language identification. The proposed algorithms can be used in multilingual settings, where the identification module will first identify the inherent script or language of incoming document or scene-texts before sending them to corresponding script/language recognition module.

Abstract

Understanding human appearance in images and videos is one of the most fundamental and explored area in the field. Describing human appearance can be interpreted as a concoction of smaller and more fundamental related aspects like posture, gesture, outlook etc. By doing so we try to grasp holistic sense from semantically lower level information. The utility behind understanding human appearance and related aspects is the industrial demand for applications that involve analyzing humans and their interaction with surroundings. This thesis work tackles two of such related aspects: i. more fundamental problem, human pose estimation and ii. deeper understanding from cloth parsing based on pose estimation. Determining the human body joint locations and configuration is quizzed as human pose estimation problem. In this work we address the problem of human pose estimation for video sequence data type. We exploit the availability of redundant information from redundant data type. The proposed iteratively functioning methodology has the first iteration involving parsing data from a quintessential generic base model. For the following iterations, we run a 3 step pipeline: grabbing confidently positive detections from previous iteration using our novel selection criteria, fine-tuning external-to-base parameters to local distribution by synthesizing exemplars from picked ones, and enforcing the learned information using an updated amalgamation model. The resulting pipeline propagates correctness in temporal neighborhoods of a video sequence. Previous methods that use the same base models have relied more on tracking strategies. From the unbiased experiments conducted, our approach has proven to be much more robust and overall better performing. In the second half, we indulge in determining a more deeper understanding of human aspects i.e. cloth parsing. This involves predicting the cloth types worn by humans and their segmented regions in images. Our work focuses on incorporating robustness to a previously formulated method. Conceivably, determining hot regions for each cloth type is dependent on the underlying pose skeleton of the human, eg. hat will be worn on the head. Hence, availability of pose information is key to cloth parsing problem, but incorrect body part estimations can also simply lead to false cloth detections and segmentations. The previous method uses pose information from pictorial structure based model, whereas we update the formulation to incorporate information from more robust part detectors. The changed model has shown to be performing better at more wild outdoor settings. However, the performance from available and proposed methods is below par and appears non-viable for application purposes. To answer this, we report a set of experiments in which we take different lookouts and report observations.

Abstract

With the ever-increasing influence of social media in our lives, it is important to automatically make sense out of the enormous amounts of social media data generated each day and leverage it for different applications. A politician trying to gauge her chances of winning the election, the government reaching out to understand the grievances of the citizens regarding various administrative issues, a company attempting to promote its products and perceive its market reach - all of them have one thing in common, their destination, i.e. the social media. Even a few years ago, a restaurant interested in customer feedback would have to run manual surveys, requesting customers to fill out lengthy feedback forms. Not only did this approach have limited reach, it also had the additional problem of customers not being responsive. Now, with the advent of social media, this process had become much less cumbersome, with people reporting their experiences openly and unguardedly, thereby minimizing the cost incurred to the companies many folds. However it is challenging to mine information from the huge amount of user generated unstructured social media data. Understanding this data entails primarily identifying, understanding and analysing the topics discussed in social media along with the opinions expressed towards those topics. In this thesis, we focus on this problem, by first treating the two tasks of topic and sentiment identification independently, before eventually presenting a joint model. Topic identification in social media posts have been widely studied in the recent past. In contrast, we direct our attention towards capturing the topics in the conversations that arise out of interactions between users on social media. Specifically, given a conversation on Twitter, we aim to automatically recommend a relevant tweet, treating the conversation as a tree. Existing solutions to this problem exploit similarity of a candidate tweet to a single tweet, or to past tweets in a user-pair conversation. In this work, we generalize the problem setting to recommend a tweet considering the context from an entire conversation tree which often includes tweets from multiple users. While this setting is more natural, it brings in additional challenges: (1) how to choose an anchor tweet node from the conversation tree for which a new tweet can be recommended as a reply? (2) how to choose the tweet to recommend? We learn regression models with novel features to address both the challenges, and use them to perform extractive response recommendation. The first regression model predicts the time required by a tweet node to get its first child node, while the second predicts the number of retweets received by a tweet, as a measure of its popularity and acceptability, and hence quality. Experiments with millions of tweets show that the proposed recommendation method is more accurate compared to the state-of-the-art approaches,with respect to ground-truth labels. Due to lack of manually annotated data, we have used proxy signals to infer labels and used them as ground truth. Sentiment Analysis is another important task that complements topic identification in order to capture actionable information from social media. While sentiment analysis has been studied widely, it is not a completely solved problem when it comes to the noisy nature of the social media data. In this work, we introduce some novel features and learn supervised models to improve performance in the area of sentiment analysis in Twitter. With careful feature ablation experiments, we show which of the novel features contribute to the performance improvement of our system and to what extent. It is a simple model that performs competitively with respect to state-of-the-art systems and can be quickly and easily prototyped as an end-to-end system from scratch. But, one drawback of this work is that we have not taken the topics into consideration. Given a piece of text, we assign a sentiment label to it, irrespective of the topics being discussed in that text. This is especially problematic, when multiple topics are at play and the sentiment expressed throughout the text is not uniform. In order to alleviate this shortcoming, we further aim to learn topics and sentiment together. However, it is still a pipeline model instead of a joint one. In this model, we want to overcome the drawbacks of topic-agnostic sentiment analysis and tackle the problem which is formally known as Aspect based Sentiment Analysis, in which the goal is to identify the sentiment associated with each of the aspects being discussed in a post. First the aspects or topics being discussed in the text are identified and we treat this sub-task of aspect category detection as a multi-class multi-label classification problem. Instead of assigning a single generic sentiment label to a piece of text, our goal here is to associate a sentiment label to each of the aspects or