Abstract

Indian languages are morphologically rich and free word order languages. There are many other distinguished characteristics possessed by them. Keeping these in mind Computational Paninian Grammar formalism was chosen to represent the syntacto-semantic relations between different words in a sentence and establish their relationship with the verb, for these languages. The syntactico-semantic dependency relations and their labels defined in the CPG formalism are very fine grained to account for the rich grammatical functions. The number of distinct dependency labels are 82 as per the scheme (both interchunk and intrachunk). It has been observed that the more semantically oriented annotation schemes make labeled parsing more difficult than the schemes based on more surface-oriented grammatical functions. These relations can be organised in the form of a hierarchical structure with each level representing a degree of granularity which can be underspecified. We aim to explore whether reducing granularity of these labels can help bridge the gap between between Labeled Score and Unlabeled Attachment Score. Universal Dependencies (UD) on the other hand have a coarser scheme of grammatical representation. We extend UD to Indian languages through conversion of Paninian Dependencies to UD for the Hindi Dependency Treebank (HDTB) and observe the effects of a relatively sparse taxonomy. We discuss the differences in annotation in both the schemes, present parsing experiments for both the formalisms and empirically evaluate their weaknesses and strengths for Hindi. We produce an automatically converted Hindi Treebank conforming to the international standard UD scheme, making it useful as a resource for multilingual language technology. Indian language treebanking was undertaken to create resources for facilitating data driven syntactic analysis. The annotations in Indian Languages’ treebanks are generally multi-layered and furnish information on part of speech category of word forms, their morphological features, related word groups and the syntactic relations. Rich syntactic features are very important for building state-of-the-art syntactic analysers but they require lot of feature engineering expertise. These indicative features pose the problem of data sparsity, incompleteness and expensive extraction. Building expensive tools to automatically generate these features is an expensive task. Keeping this in mind our work proposes to apply non linear neural network for parsing five resource poor Indian Languages belonging to two major language families – Indo-Aryan and Dravidian. Bengali and Marathi are Indo-Aryan languages whereas Kannada, Telugu andMalayalam belong to the Dravidian family. The non linear architecture elegantly addresses all the problems mentioned above. While little work has been done previously on Bengali and Telugu linear transition-based parsing, we present one of the first parsers for Marathi, Kannada and Malayalam. All the Indian languages are free word order and range from being moderate to very rich in morphology. Therefore in this work we propose the usage of linguistically motivated morphological features ( suffix and postposition ) in the non linear framework, to capture the intricacies of both the language families. We also capture chunk and gender, number, person information elegantly in this model. We put forward ways to represent these features cost effectively using monolingual distributed embeddings. Instead of relying on expensive morphological analyzers to extract the information, these embeddings are used effectively to increase parsing accuracies for resource poor languages. Our experiments provide a comparison between the two language families on the importance of varying morphological features. Part of speech taggers and chunkers for all languages are also built in the process.

Abstract

In this thesis, we extensively study the problem of broadcasting of entanglement. We first introduce the elements of quantum information theory and then define various kinds of quantum and classical correlations. We also talk about various measures to quantify correlations, which are important in the context of broadcasting correlations. Next, we re-conceptualize the idea of state dependent quantum cloning machine, and in that process, we introduce different types of state dependent cloners like static and dynamic state dependent cloners. We derive the conditions under which we can make these cloners independent of the input state. Our main motivation for defining various types of cloning machines is that if we have partial information about the state to be cloned beforehand, we can choose the best performing cloner. In the broadcasting part, as our resource initial state, we start with general two qubit state and consider specific examples like, non maximally entangled state (NME), Werner like state (WLS), and Bell diagonal state (BDS). We apply both state dependent and state independent cloners, both locally and non-locally, in each of these cases. Incidentally, we find several instances where state dependent cloners outperform state independent cloners in broadcasting. This work gives us a holistic view on the broadcasting of entanglement in various two qubit states, when we have an almost exhaustive set of cloning machines in our arsenal.

Abstract

Sparse matrix computations such as multiplying a sparse matrix with a sparse matrix, denoted spmm, and multiplying a sparse matrix with a dense matrix, denoted csrmm, are fundamental operations in linear algebra that have several applications. Hence, efficient and scalable implementations of spmm and csrmm have been a topic of immense research. Efforts are aimed at implementations on FPGAs, multi-core architectures, GPUs and such emerging computational platforms. The architectural trend towards heterogeneity has pushed heterogeneous computing to the fore of parallel computing research. Owing to the highly irregular nature of spmm and csrmm it is observed that CPUs and GPUs can offer comparable performance (Lee et al. [26]) and hence implementations on CPU+GPU systems are widely researched. In this thesis, we propose Sorted-Workqueue, a CPU+GPU heterogeneous algorithm for spmm and csrmm based upon Workqueue framework proposed by Kothapalli et al. [25]. We perform experiments on general sparse matrices from standard datasets and study the performance of spmm and csrmm. Another trend towards customizing algorithms according to characteristics of the input are gaining research interest in recent times. In this thesis, we consider real-world sparse matrices that exhibit scale-free nature and exploit their characteristics to propose better algorithms for spmm and csrmm. Focusing on such matrices, we propose novel algorithms HH-CPU for spmm and HD-CPU for csrmm on a CPU+GPU heterogeneous platform. We perform experiments on a wide variety of real-world scale-free matrices from standard datasets and show performance improvement over the state-of-art algorithms on CPU+GPU heterogeneous platform. A majority of the heterogeneous algorithms follow a work partitioning approach where the input is divided into appropriate sized pieces so that individual computing units can process the “right” pieces of the input. Such a division is done by means of some parameters, usually thresholds which vary for each input instance. However, identifying the right value of the threshold is usually non-trivial and may require an extensive empirical search. Such an extensive empirical search may potentially offset any gains accrued out of heterogeneous algorithms. We also show that one of our proposed method, HH-CPU, requires some thresholds to be computed in order to identify the right work that can be assigned to the right processor. For this, we propose a simple, yet effective technique based on sampling which can adapt to the algorithm used, the input instance and the heterogeneous computing units in the platform. Our technique is generic in its applicability as we will demonstrate in this thesis. We validate our technique on HH-CPU and show that we can find the required threshold ± 7.5% away from the best possible threshold.

Abstract

This thesis proposes the development of an FPGA prototype to estimate the direction of arrival for adaptive array antenna based on matrix pencil technique.With the passage of time, there is need for more data rates however due to the limitation of natural frequency we have to look for other alternatives. Therefore, people have started other ways to increase the frequency like angle, code, geographical space, etc. In this thesis, we will be concentrating on angle dimension. In estimating Direction of Arrival (DOA), the most important step is to calculate the eigenvalues of matrix. Literature survey reveals that limited work has been carried out to compute the eigenvalues of an asymmetric matrix from implementation perspective. Therefore a new approach to calculate the eigenvalues of matrix has been described. In this work we present a method to estimate the DOA, known as Matrix Pencil which is a key technique to estimate the DOA for adaptive array antenna for cellular wireless base stations. This thesis describes the hardware implementation of Matrix Pencil on FPGA. Matrix Pencil uses QR algorithm for the calculation of eigenvalues which is the most critical part of the system. In order to accelerate and increase the efficiency of the system it utilises Triangular Systolic Array (TSA) architecture to compute the eigenvalues of the system. Matrix Pencil is found to yield better results than its peer algorithms like MUSIC, ESPIRIT. When processing have to be performed in coherent environment and when there is small number of snapshots available. The power consumed by the design is 0.65W. Maximum frequency which can be achieved by the system is 900MHz. Latency of our design is 2.7 mS which is approximately 28 times faster than general purpose computer based solution.

Abstract

Code-switching is a phenomenon of mixing grammatical structures of two or more languages under varied social constraints. The code-switching data differ so radically from the benchmark corpora used in NLP community that the application of standard technologies to these data degrades their performance sharply. Unlike standard corpora, these data often need to go through additional processes such as language identification, normalization and/or back-transliteration for their efficient processing. In this thesis, we investigate these indispensable processes and other problems associated with syntactic parsing of code-switching data and propose methods to mitigate their effects. In particular, we study dependency parsing of code-switching data of Hindi and English multilingual speakers from Twitter. We present a treebank of Hindi-English code-switching tweets under Universal Dependencies scheme and propose domain adaptation techniques to efficiently leverage monolingual syntactic annotations and the annotations from the Hindi-English code-switching treebank. Firstly, we propose modifications to the parsing models which are trained only on the Hindi and English monolingual treebanks. We have shown that code-switching texts can be efficiently parsed by the monolingual parsing models if they are intelligently manipulated. Against an informed monolingual baseline, our parsing strategies are at-least 10 LAS points better. Secondly, we propose a neural stacking model for parsing that efficiently leverages part-of-speech tag and syntactic tree annotations in the code-switching treebank and the monolingual Hindi and English treebanks. We also present normalization and back-transliteration models with a decoding process tailored for code-switching data. Our neural stacking models achieve an accuracy of 90.53% for POS tagging and 80.23% UAS and 71.03% LAS for dependency parsing. Results show that our neural stacking parser is 1.5% LAS points better than the augmented parsing model and our decoding process improves results by 3.8% LAS points over the first-best normalization and/or back-transliteration.

Abstract

We demonstrate the effectiveness of an end-to-end trainable hybrid CNN - RNN architecture in recog- nizing Urdu text from printed documents, typically known as Urdu OCR , and from Arabic text embedded in videos and natural scenes. When dealing with low-resource languages like Arabic and Urdu, a major adversary in developing a robust recognizer is the lack of large quantity of annotated data. We overcome this problem by synthesizing millions of images from a large vocabulary of words and phrases scraped from Wikipedia’s Arabic and Urdu versions, using a wide variety of fonts downloaded from various online resources. Building robust recognizers for Arabic and Urdu text has always been a challenging task. Though a lot of research has been done in the field of text recognition, the focus of the vision community has been primarily on English. While, Arabic script has started to receive some spotlight as far as text recognition is concerned, works on other languages which use the Nabatean family of scripts, like Urdu and Persian, are very limited. Moreover, the quality of the works presented in this field generally lack a standardized structure making it hard to reproduce and verify the claims or results. This is quite surprising considering the fact that Arabic is the fifth most spoken language in the world after Chinese, English, Spanish and Hindi catering to 4.7% of the world’s population, while Urdu has over a 100 million speakers and is spoken widely in Pakistan, where it is the national language, and India where it is recognized as one of the 22 official languages. In this thesis, we introduce the problems related with text recognition of low-resource languages, namely Arabic and Urdu, in various scenarios. We propose a language independent Hybrid CNN - RNN architecture which can be trained in an end-to-end fashion and prove it’s dominance over simple RNN based methods. Moreover, we dive deeper into the working of its convolutional layers and verify the robustness of convolutional-features through layer visualizations. We also propose a method to synthe- size artificial text images to do away with the need of annotating large amounts of training data. We outperform previous state-of-the-art methods on existing benchmarks by quite some margin and release two new benchmark datasets for Arabic Scene Text and Urdu Printed Text Recognition to instill interest among fellow researchers of the field.

Abstract

Large scale emergencies are part of life that can require mass evacuations. Planning for such emergencies is an important component of traffic management to minimize any losses arising due to them. As human cognitive behaviour plays an important role during response to emergencies, understanding such cognitive behavior will help us plan better. The cognitive behavior of each individual driver agent may include greed (hurry), mob mentality and other unexpected biases which may slowdown the clearing up of traffic. To provide an efficient solution to this problem, we study the effect of human cognitive behaviors on traffic patterns during an emergency situation. We make the assumption that during the emergency, there are traffic police or other personnel trying to guide the vehicles so that the traffic clearance is sped up (to minimize the human or property losses), as they have a global view of the emergency and have accurate real-time updates. Another assumption is that the traffic police use the Ford-Fulkerson Algorithm, which is a standard algorithm to perform an efficient evacuation using flow model, to maximize the flow in the (traffic) network and then perform an extensive agent based analysis to study the traffic patterns that arise due to a variety of human factors and biases. While human biases can cause disruption to plans generated by the Ford Fulkerson algorithm, there are situations where we may want encourage behaviors such as greed. For example, we may want an ambulance to reach its destination at the earliest possible time hence would like it to display a greedy behavior. This implies that different vehicles may need to have different priorities. Current evacuation models, including Ford-Fulkerson and other known algorithms, overlook such a scenario, and treat all the vehicles as same. To overcome this drawback, we also focus on the problem of prioritized routing of vehicles without affecting the overall evacuation time. Prioritized routing may happen even during normal times, but it becomes even more important during emergencies, as emergency vehicles, police vehicles and large vehicles (such as buses) that carry a lot of people need to have a higher priority in terms of evacuation. To summarize, we study the following two problems in this thesis: (a) How human biases effect plans made for emergency evacuation (b) Incorporate priority of vehicles when generating plan for evacuation. Through a series of experiments performed using the well-known traffic simulator SUMO, we make the following contributions: (a) We validate that Ford-Fulkerson Algorithm is indeed efficient for clearance of vehicles in case of non-prioritized evacuation (b) Driver agents that do not follow the specified directions due to their preferences and biases lose out on an average (c) In line with our expectations, we find that having a prior knowledge and/or real-time updates about the environment can indeed offset the effect of human biases to a good extent. (d) We map the prioritized routing problem to the minimum-cost maximum-flow problem, a standard problem formulation in network flow theory. (e) We then develop the Prioritized Routing Assistant for Flow of Traffic (PRAFT) that casts the prioritized routing problem which includes a notion of priority of vehicles and priority of routes into the minimum cost maximum flow problem. (f) Through a series of experiments performed using the well-known traffic simulator SUMO, we could establish that PRAFT indeed maps higher priority vehicles to better quality routes and is monotonic in the sense that decreasing priority order of vehicles maps to a decreasing route quality.

Abstract

Consequent to the discovery of their catalytic and regulatory functions, RNA has been found to be associated with numerous biological processes including regulation of gene expression and protein synthesis. To participate in these cellular processes, RNA molecules are required to be folded into functionally competent structures. Unlike double stranded DNA, the single stranded RNA folds onto itself and thereby displays a diverse repertoire of noncanonical base pairs. Unique geometry, stability and physicochemical properties of these base pairs define the structural landscape of RNA molecules. In this regard, modification of nucleobases constitute an important feature. On one hand, they in- crease the diversity in RNA’s structural alphabets and, on the other, the subsequent changes in their respective electronic properties give rise to a new class of noncanonical base pairs. Interestingly, some nucleobase modifications remain ‘invisible’ even in the high resolution X-ray crystal structures (e.g., protonations, tautomerization, etc.), and can only be inferred through circumstantial evidences. In this thesis quantum mechanics (QM) based methods in conjunction with structural bioinformatics tech- niques have been implemented to study the putative roles of four different nucleobase modifications (e.g. metal ion binding, protonation, tautomerization and synthetic modification) in determining the geometry, stability and function of different noncanonical base pairs observed in functional RNAs. It has been illustrated here that Mg2+ binding not only can stabilize the intrinsically unstable ge- ometry of numerous important RNA base pairs, but also may fine tune their geometries and interaction energies. Among these base pairs, some are also stabilized by Class II nucleobase protonation (i.e., when the loaded proton is not sequestered between two bases). By evaluating the optimized geometries and interaction energies of such base pairs, in the presence and absence of protonation, a proof of con- cept has been established for a strategy to detect hitherto undetected occurrence of N7 and N3 proto- nated guanine base pairs. This also opens up the possibility of the discovery of undetected protonation in other base pairing systems. Consequences of nucleobase protonation has also been studied for base triples, which reveal that nucleobase protonation often leads to cooperative binding of three distantly placed nucleotides. In the context of protein synthesis, it is known that selection of wrong aminoacyl tRNA due to mismatch primarily at the first two positions of the codon-anticodon (C-AC) helix leads to missense errors. Recent crystal structures of complete 70S ribosome revealed that GU mismatches may occur at the first position of C-AC helix, where they mimic the GC like canonical geometry. It has been argued here that nucleobase tautomerization (enolic forms of uracil/guanine) is necessary for such spatial mimicry and is sufficient to maintain the overall interaction of the first C-AC pair with the monitoring residue (A1493) of 16S rRNA. In addition to the aforementioned findings, modified nu- cleobases have been studied, in the light of their important application in biomimetics and RNA based nanotechnology. In this work it has been evaluated why substitution of thymine by 6-Ethynylpyridone (a synthetic thymine analogue) increases the thermostability of double helical stretches. Overall, this thesis highlights that geometry and stability of RNA base pairs are sensitive towards different types of nucleobase modifications. Characterization of such sensitivity enriches the understanding about the sequence-structure-function relationship in RNA.

Abstract

The non invasive measurement of chromophores in blood is in great need for diagnosis of major health hazards. Frequent monitoring of blood glucose levels, along with blood urea will allow early detection of diabetes, liver dysfunction and renal diseases. The non invasive instrument used for accomplishing these tasks must meet several criteria like, accuracy and precision of the measurement. Many efforts have been made by many research groups all over the world in making the procedure as much less invasive as possible by trying to reduce the blood drawn for test to micro liters or by reducing the cross sectional area of the suction needle. The device should be portable, low-cost and reliable overtime. There are many modes of diagnosis that satisfy these criteria but most of them are still in a developmental stage. Although many methods have been proposed and are available in literature, near infrared (NIR) spectroscopy has the advantage of meeting these rigorous demands.Initially, based on the intrinsic property of the analyte molecule, the NIR spectroscopy has been carried out and the wavelength of peak absorption has been identified. Using the identified wavelength a finger clip comprising of sensor and detector has been developed for collecting the in vivo PPG (photoplethsymograph) signals. These non invasive signals are used for estimating the concentration of specific blood analyte. Various statistical techniques have been used for carrying out the calibration of the in vivo signals obtained from the photoplethsymograph based sensing circuit. Secondly, these signals are calibrated using artificial neural networks to predict the analyte concentration. As typical blood analytes, blood glucose and urea are used to establish the proposed methodology to noninvasively estimate the blood parameters. Altogether 282 patients were available for measurement of glucose out of which for 100 samples the reference values are measured using Accucheck glucometer and for remaining 182 samples the reference values are measured using traditional lab based method. For the first 100 samples the testing has been carried out after taking informed consent from patients out of which 50 patient data have been used for training the neural networks and testing has been carried out on remaining 50 patients. The training of neural networks has been done offline using MATLAB and then implemented on FPGA to minimize the design circuitry. For estimating the concentration of urea in blood, samples are collected from total of 70 patients. For this invasive urea measurement is carried out using lab based method. For estimating the blood glucose concentration, the data has been calibrated using two types of neural network architectures conventional neuron model and the inverse delayed (ID) neuron model and the results are compared. It is found that the mean square error in estimating the glucose concentration was found to be 1.89mg/dL using ID function model of neuron as against 5.48mg/dL using conventional neuron model with 10 neurons in hidden layer for each model. In a similar way the blood urea concentration has been estimated and the mean square error is found to be 2.23mg/dL. For measuring the blood urea concentration, the artificial neural network based regression analysis has been carried out. However, different components in blood, although having different absorption spectrum, there is some overlap between absorption spectra of different components. Hence the photoplethsymography output is subjected to different statistical techniques like artificial neural networks(ANN), principal component analysis(PCA). Finally, an attempt has been made to identify the optimal orientation of optode pair with respect to the skin surface using Rayleigh Rice Vector Pertubation Surface Scattering theory, surface roughness models for skin surface roughness have been created and optimal orientation of the optode pair with the skin surface has been theoritically estimated. The results of the theoritical estimation has also been suitably verified with the help of experiments both in the case of reflective and transmissive photoplethsymography.

Abstract

Advertisements (ads) are often filled with strong affective content covering a gamut of emotions intended to capture viewer attention and attempt to convey an effective message. However, most approaches to computationally analyze the emotion present in ads are based on the text modality and only a limited amount of work has been done on affective understanding of advertisements videos from the content and user-centric perspectives. This work attempts to bring together recent advances in deep learning (especially in the domain of visual recognition) and affective computing, and use them to perform affect estimation of advertisements. We first create a dataset of 100 ads which are annotated by 5 experts and are evenly distributed over the valence-arousal plane. We then perform content-based affect recognition via a transfer learning based approach to estimate the affective content in this dataset using prior affective knowledge gained from a large annotated movie dataset. We employ both visual features from video frames and audio features from spectrograms to train our deep neural networks. This approach vastly outperforms the existing benchmark. It is also very interesting to see how human physiological signals, such as that captured by Electroencephalography (EEG) data are able to provide useful affective insights into the content from a user-centric perspective. Using this time series data of the electrical activity of the brain, we train models which are able to classify the emotional dimensions of this data. This also enables us to benchmark this user-centric performance and compare it to the content-centric deep learning based models, and we find that the user-centric models outperform the content-centric models, and set the state-of-the-art in ad affect recognition. We also combine the two kinds of modalities (audiovisual and EEG) using decision fusion and find that the fusion performance is greater than either single modality, which shows that human physiological signals and the audiovisual content contain complementary affective information. We also use multi task learning (MTL) on top of the features of each kind to exploit the intrinsic relatedness of the data and boost the performance. Lastly, we validate the hypothesis of better affect estimation being able to enhance a real world application by supplying the affective values computed by our methods to a computational advertising framework to get a video program sequence with ads inserted at emotionally relevant points, determined to be appropriate based on the affective relevance between the the program content and the ads. Multiple user studies find that our methods significantly outperform the existing algorithms and are very close (and sometimes better than) human level performance. We are able to achieve much more emotionally relevant and non disruptive advertisement insertion into a program video stream. In summary, this work (1) compiles an affective ad dataset capable of evoking coherent emotions across users; (2) explores the efficacy of content-centric convolutional neural network (CNN) features for affect recognition (AR), and find that CNN features outperform low level audio-visual descriptors; (3) study user-centric ad affect recognition from Electroencephalogram (EEG) responses (with conventional classifiers as well as a novel CNN architecture for EEG) acquired while viewing the content that outperform content descriptors; (4) Examine a multi-task learning framework based on CNN and EEG features which provides state of the art AR from ads; (5) Demonstrates how better affect predictions facilitates more effective computational advertising in a real world application.