Abstract

Indian languages are MoR-FWO and hence differ from English in structure and morphology. There are many distinguished characteristics possessed by Indian languages. While working with these languages we have to keep in mind, these characteristics and plan strategies accord- ingly. We worked on improving Dependency Parsing for Indian Languages, more specifically for Hindi, an Indo-Aryan Language. In the conventional Dependency Parsing methods, the focus has been on developing robust data driven dependency parsing techniques. This initiated efforts in creating hand annotated large treebanks, consisting of hand annotated features. These treebanks serve as input for the training of data-driven parsers. The annotations in Indian Languages’ treebanks are generally multi-layered and furnish information on part of speech category of word forms, their morpho- logical features, related word groups and the syntactic relations. For improvements, richer and richer features are being added. This process of manual annotation is expensive, as it requires a lot of human efforts. It is a tedious task to create treebanks for all the languages. Even if we make the treebanks available, in the real time scenario we require many tools to extract features automatically. Building such tools is also a complex task. We are in an era with almost unlimited access to raw data. Nevertheless, we often struggle to make sense of most of it. Much of this data is unlabeled and thus useless in many of the traditional supervised ma- chine learning scenarios, that require explicit labeled/hand-annotated examples. In this work, we present our efforts towards exploring cost effective approaches for building and improving parsers for resource-poor languages. For this purpose we try to use unsupervised techniques to extract features from the largely available mono-lingual raw corpus. Using cross-lingual treebank transfer, we exploit the available treebanks for other languages and using some techniques like MT and try to generate a treebank for the target language. We can use this treebank for training of parser. We first try this approach for Hindi. An important constraint for using this approach is that the annotation of treebank needs to be similar cross linguistically. For this, we use UD framework. Universal Dependencies is an initiative to create cross-linguistically consistent treebank annotation for many languages, with the goal of vii facilitating multilingual parser development, cross-lingual learning, and parsing research from a language typology perspective. In the previous studies, we have seen that CPG framework is better suited for Indian Languages. So we try to compare other techniques with the cross-lingual parsing in UD framework. In the concluding work, we try to make use of Vector Space Modeling on a large monolingual raw data, a recent technique being used widely across different tasks. Use of large monolingual corpus helps reducing the problem of data sparsity. We try to explore this technique to achieve three goals. Using word-embeddings extracted from vector space modeling as features, we first try to improve the state-of-the art accuracy for Hindi. Here we use word-embeddings as additional features other than the conventional features. The second goal is to help building parsers for less resourced languages. This is done by replacing the costly linguistic features with word-embeddings. This requires minimal human annotation. The third goal we achieve, is improving parser’s performance in general domain data. We show results where parser is trained on News domain and input sentences are from four different domains Box-Office, Cricket, Gadget and Recipe.

Abstract

Imitating the behaviour and characteristics of fluids with the help of a computer is called fluid simulation. Real world fluids are fickle. They are subtle and gentle at times; at times they are ravenous and tumultuous. Needless to say, complex equations are behind even the tiniest of ripple, so much so that often fluid mechanics has been described as ”the physicists nightmare”. The development of fluid simulations has traditionally been in two concurrent streams, viz., Eulerian and Lagrangian Simulations. Lattice Boltzmann Method developed around the same time but unlike the conventional methods, it is a statistical method based on Kinetic Theory. In this work, we combine physical models of non-Newtonian fluids with Lattice Boltzmann Method. We give the CPU implementation, showing how easy it is to understand and code. We show how the method, in spite of its ease of implementation, doesn’t compromise on physical realism or accuracy. We also give a model for GPU implementation for increased efficiency and interactive frame rates.

Abstract

Natural Language Processing (NLP) is a challenging field in the area of artificial intelligence and computational linguistics. In simplistic terms, it can be defined as processing a natural language in any form either speech or written text. Though extensive research has been done for many of the languages in the world, Indian languages are still lagging behind in the race. Processing of any natural language requires analysis to be done at multiple levels like word-level, phrase-level, sentence-level, semantic-level and higher levels of pragmatic and discourse. In this work we are presenting our efforts of making new advancements at the sentence level, which in linguistics terms, is regarded as Syntactic Parsing. Syntactic parsing involves establishing relations between different words of a sentence to convey the possible meaning. Indian languages are morphologically rich and exhibit free-word order (MoR-FWO). Dependency Parsing, a type of syntactic parsing is better suited to such languages. Our efforts start from delivering a state-of-the-art Hindi Dependency Parsing system through the platform provided in the form of a shared task (Sharma et al., 2012). We employed a data-driven transition-based statistical system (Malt Parser), trained on Hindi Dependency Treebank (Bhatt et al., 2009; Palmer et al., 2009). Error-analysis performed in the task, helped us to target the problems in a more specific manner. In the next phase, to target some of the problems like case ambiguity, data sparsity, lack of case marker, etc., we aided the process of dependency parsing by enriching the training model with semantic information. The information is extracted automatically from a rich lexical resource, Hindi Word- Net (Narayan et al., 2002). Learning from the insights obtained in this advancement process, we moved to another well-established approach, Ensembling. Ensembling works on the principle of exploiting diversity of multiple parsing systems and combining their strengths to improve the parsing performance. We explored two ensembling approaches namely, re-parsing algorithms and word-by-word voting, using six different weighting strategies to combine six algorithmic variants of Malt parser. Improvements had been observed in the second approach. After establishing a systematic comparison between both the techniques of ensembling, we obtained the lead to search for better weighting strategy to improve ensembling. The search ended with Parse Quality Estimation (PQE) score. Adapting the work done in the past, we extended this functionality for our purpose of performing ensembling. The approach, which has failed earlier, has now shown improvements. Further, we also expanded the scope of PQE score for dependency arcs (attachment) to capture confusion made by the oracle in the parsing system. The functionality had also been extended for Joint prediction of both arcs and labels simultaneously. To prove the efficacy of the approach, we implemented several real-world applications of PQE score. Finally, we proposed a robust evaluation framework in terms of Domain Adaptability (DA) and Inter-Language Portability (ILP), to better judge the effectiveness of Hindi Dependency Parser. During this evaluation process, using the property of portability, we also built dependency parsers for two of the Dravidian languages: Tamil and Telugu, which can be integrated easily in real world NLP systems like Machine Translation.

Abstract

The World Wide Web has evolved from a set of simple static pages connected by hyper links to a complex platform, to meet the demands of users and businesses. The modern web is characterised by complex operations such as online social networking, content sharing, electronic payments, single sign-on etc. The evolution of web APIs (Application Programming Interfaces) and open data initiatives encouraged developers to build Mashups, web applications that integrate data from multiple servers. Data has become the currency on the web, due to which the web has turned into a lucrative target for attackers a.k.a cyber criminals. Newer web standards such as HTML5 are evolving and newer versions of browsers are emerging to meet the needs of the modern web. However, the security policies governing the web have not evolved at the same pace. Due to this, the number of vulnerabilities and newer web based attacks are increasing rapidly. Browsers, being the entry points to the web, are heavily targeted by attackers. One good reason is that the time and effort required to compromise a website due to a vulnerability in the application layer is much lesser compared to that of other layers. E.g., to steal certain sensitive data from a web server, it is much easier to inject a small snippet of JavaScript into a vulnerable web page loaded in a browser and exfiltrate the data, than to intercept a connection and break a fairly strong crypto system, or to bypass firewalls and break into the network. This work attempts to understand the core security policies of web browsers that govern the security and privacy of web interactions. It closely examines a series of client side web attacks, their existing defenses and deficiencies. It observes the need for novel application-level security frameworks as well as browser security policies in mitigating them. The outcome of the work is two fold: Firstly, it presents a security abstraction layer (as an API library) called “SafeMash”, which helps developers build safe mashups over the current low-level security APIs in HTML5. Secondly and more importantly, it proposes a novel declarative browser security policy called CORP (Cross Origin Request Policy) to mitigate a set of attacks which we refer to as “Web Infiltration attacks”. CORP enables a server to control which site can access which resource on a cross-origin server, and through which browser event. To evaluate the effectiveness of SafeMash and CORP, several experiments were conducted. The usage of SafeMash was empirically demonstrated by first building an interactive mashup using open APIs from ProgrammableWeb (without using state-of-the-art security echanisms) and then rebuilding it using SafeMash without losing functionality. To clearly understand the security model of web browsers and its limitations, a corpus of web attacks was developed. The formulation, effectiveness and ease of deployment of CORP was demonstrated based on the insights derived from examining the corpus of web attacks. The design of CORP was formally verified by building a light weight model in the Alloy model finder. An implementation of CORP was provided as a browser extension for Chrome and it is evaluated against real-world cross origin attacks on open source web applications. Our initial investigation revealed that most of the popular websites already segregate their resources in a way which makes deployment of CORP easier.

Abstract

The field of quantum information and computing has gained a lot of attention in the past couple of decades. It is an inter-disciplinary field comprising of mathematics, physics and computer science. Researchers have been able to exploit the quantum properties like superposition and entanglement to improve the efficiency of classical algorithms and communication and cryptographic protocols. In this thesis, we address a few problems in quantum cryptography and communications. We introduce the basic mathematical structures and postulates of quantum theory in the first chapter. We also describe the basic quantum information tools which are essential of this thesis. The field of quantum cryptography is introduced here as well.In the second chapter, we address a problem in quantum secret sharing schemes. We give a protocol for sequential quantum secret sharing where the dealer does not have access to all the secrets at the beginning of the protocol. We also show that the resource requirement for our protocol is optimal. We analyze our protocol in case of a noisy quantum channel. We use weak measurements to demonstrate that the efficiency of the protocol in such noisy environments can be enhanced. In the third chapter. we address a problem in a new emerging sub field of quantum cryptography, namely, device independent cryptography. We discuss the issues of the usual quantum cryptographic schemes and show how device independent cryptography addresses some of those issues. In particular, we deal with the case when Alice and Bob has been provided with untrusted devices and Eve can control Bob’s detectors using tailored bright pulses. We analyze the security of such attacks in a semi-device independent scenario and give the sufficient conditions for unconditional security. In the final chapter, we introduce an useful information processing task, namely broadcasting of correlations. It essentially deals with the procedures of creating a larger number of less correlated systems from a highly correlated system. Then we move on to broadcasting of general correlations (possibly even stronger than quantum correlations). We introduce the the mathematical framework and define linear transformation rules. We study the correlation properties of the resulting resources in terms of the initial correlations and transformation parameter.

Abstract

This thesis describes a system for EnergyPlus speedup that splits a single annual EnergyPlus simulation into 12 simulations, runs them in parallel over a cluster of 12 computers, collates the results once the simulations are finished, and does a quality analysis (of the parallelization) on the results. This thesis is based on the earlier studies done on the methodology for speeding EnergyPlus simulation by splitting an annual EnergyPlus simulation into multiple smaller simulations. The EPparallel tool, developed as a part of this thesis, uses Message Passing Interface API and runs on Linux. The thesis describes the methodology to prepare the input file for multiple runs, how the computers are connected to form the cluster, how message passing & file sharing is done between the nodes, and how the results generated by multiple instances of EnergyPlus are collated. Further, a quality check method has been developed which gives indication on the level of accuracy the parallel runs have achieved as compared to the results that would have been obtained by a single annual run. Also, an enhancement has been made on shadow synchronization technique proposed in the earlier studies. The tool has been tested on 16 different commercial reference buildings over 16 US weather files (total 256 combinations). The results of these 256 runs, showing the runtimes, overheads, speed gains, and accuracy of results are presented in this thesis. The speed gain ranged from 2.9x to 7.8x and accuracy (percentage of output values obtained in parallel simulation which were off by more than 1% as compared to output values obtained in annual simulation) ranged from 0% to 3.7%.

Abstract

E-contracts are textual documents describing various contractual assignments/tasksand dependencies among contractual elements such as parties, activities, clauses, exceptions and payments. The dependencies and constraints in e-contract can be differently stated in different parts of large documents. Inconsistencies in the e-contract document, particularly the contract activities and clauses specification, may lead to failures during contract enactment. The thesis work focuses on (i) ensuring consistency at specification level, (ii) failure detection through consistency checking and their handling at execution levelduring e-contract enactmentand(iii) failure preventionby assessing the possible failuresthat may arise due to inconsistent task specifications (leads to violation of constraints during execution) and thereby avoid from abnormal termination of workflow execution.To determine the consistency of an e-contract document, we construct two graphs namelySentence Dependency Graphand Contract Element Dependency Graphfrom dependencies existing in the contract document. We also develop a methodology usingthese two graphs for consistency detection in an e-contract. We also present an evaluation of our approach on a sample contract document and come up with visualization for showing dependencies of contract elements which are present in the document contract. Since contracts may evolve over a period of time, an e-contract enactment system should adapt to changing requirements. For this purpose, we use the concept of Meta Execution Workflowsfor e-contract enactment. Meta execution workflows allow modification of the workflow execution engine process to support design and run time changes. In this thesis, we present a framework to execute workflows in a seamless manner by handling exceptions and failures, and thereby ensuring consistency during e-contract execution. Our framework, using meta execution engine, representsthe workflow execution engine and other components of WFMSin terms of workflows. Our system allows specification, instantiation, modification and execution of workflows on-the-fly with less human intervention even when failures occur.We also provide design and implementation aspects of Failure Resilient Workflow System (FRWS)and demonstrate its applicability for different failure scenarios of anexample e-contract.Though the proposed solution is specific to e-contract enactment, it can be made generic and applied to other domains where the business processes are modeled using workflows.

Abstract

Humans perceive speech as made up of sequence of discrete sounds. However to represent speech as a sequence of phones with well defined, non-overlapping intervals is a challenging problem. This is because of the continuously varying vocal tract system (i.e., vocal tract configuration and vocal fold vibration) leading to the co-articulation effect, where the current phone is considerably influenced by its adjacent phones. Despite this co-articulation effect, there exists events called landmarks, occurring due to abrupt variations in the vocal tract system. Detection of these landmarks can be used to represent speech as a sequence of phones which may help in building systems that process speech similar to that of humans. Landmarks are the time instants in the acoustic signal that are consistently correlated to major artic- ulatory movements such as transition of the vocal tract from a more open to a more closed configuration and vice-versa (i.e., change in manner of articulation), and transition from a free vibration to complete cessation of vocal fold vibration and vice-versa. These landmarks are foci and hence processing of speech can be done only around landmarks instead of considering the entire speech signal, thus reduc- ing the amount of processing required. Also, the analysis around different landmarks can be done with different resolutions. Landmark detection is hierarchical and hence more than one evidence can be ob- tained for making decisions. In this thesis, the hierarchy that exists among landmarks is exploited for vowel landmark detection (VLD). Sonorant segmentation is performed first, and then vowel landmarks are detected in the sonorant regions. Sonorant refers to the sound that is produced with no sufficiently strong constriction so as to produce turbulent noise or stoppage of airflow. The broad manner classes like vowels, nasals and approxi- mants are categorized under sonorants, whereas fricatives, stops and non-speech regions are considered as non-sonorants. Sonorant segmentation of speech signals is critical in developing automatic speech recognition (ASR) systems, audio search systems and for automatic segmentation of speech corpora. In this work, acoustic features based on excitation source and vocal tract system characteristics of sono- rant sounds are proposed for segmentation of sonorant regions in continuous speech. The features are based on energy of zero frequency resonator signal, strength of excitation and dominant resonance fre- quency around epochs. An algorithm is developed to relate these features in a hierarchical manner using knowledge-based approach. Performance of the proposed algorithm is studied on three different datasets, for varying levels of degradation. Vowels being a subclass of sonorant sounds, they exhibit characteristics similar to sonorants. So the features used for sonorant segmentation of speech are also considered for detection of vowel landmarks. Apart from these, features which capture characteristics specific to vowels are also considered for the task of vowel landmark detection (VLD). Using these features, a rule-based algorithm is developed for VLD. Performance of the proposed VLD algorithm is studied on three different databases namely, TIMIT (read), NTIMIT (channel degraded) and Switchboard corpus (conversational speech). The pro- posed algorithm is also tested on TIMIT and NTIMIT datasets for different levels of noise degradations. Speech-laugh is a speech-synchronous form of laughter that often occurs in natural conversation. Speech-laugh not only signifies the emotional state of a speaker, but also carry the linguistic informa- tion. Traditional automatic speech recognition (ASR) systems consider both laughter and speech-laugh as paralinguistic elements. This resulted in loss of information. Discriminating speech-laughs from laughter improves the accuracy of ASR systems. It also helps to know the emotion expressed by laughter i.e., happy, sarcasm etc. In this work, as an application of VLD, excitation source features extracted only in the vowel regions are analyzed for discriminating speech-laugh from laughter and neutral speech

Abstract

Computing a maximal independent set (MIS) is a fundamental problem in distributed computing for its ability to nicely capture the essential challenge of symmetry breaking and also for its myriad applications to other problems. A relaxed version of computing an MIS is the problem of computing a t-ruling set. A t-ruling set for an integer t ≥ 1 in a graph G is an independent subset S ⊆ V such that every nodes v ∈ V is either in S or has a neighbor w ∈ S at a distance at most t from v. Computing a t-ruling set also involves symmetry breaking. All the algorithms we present in this thesis are randomized and synhronous in nature. First, we √ log ∆ O( log log n) rounds with + e present an algorithm which computes a 2-ruling set in any graph in log log n high probability, where n denotes the number of vertices in the graph and ∆ denotes the maximum log ∆ 1/2+ degree of any vertex in the graph. This result is an improvement over the O (log n) + (log n) √ round algorithm from [6] whenever ∆ ∈ O(2 log n ). We then use it to present another algorithm which √ can compute a 2-ruling set for graphs of arboricity a = 2 O( log n) in O( (log n/ log log n) rounds with high probability. We then extend the ideas from the above algorithm and show that a (t + 1)-ruling set for any t ≥ 1 in graphs with arboricity a = O(log log n) can be computed in O(t log 1/t ∆ + t 2 (log log n) 1/t + (log log n) 2 ) rounds. Therefore, a log log ∆-ruling set for bounded arboricity graphs can be computed in O((log log n) 2 ) rounds. Our results therefore indicate that while computing an MIS in graphs of √ bounded arboricity in O( log n) rounds is still an open problem, ruling sets for small values of t can be found in much fewer rounds. Similarly, a (t + 1)-ruling set for a general graph can be computed in √ O(t log 1/t ∆ + t 2 (log log n) 1/t + e O( log log n) ) rounds. Also, a t-ruling set for graphs of girth > 6 can √ be computed in O(t log 1/t ∆ + t 2 (log log n) 1/t + e O( log log n) ) rounds. In a later section, we compare the run time of Luby’s [13] and M ́etivier’s [14] MIS algorithms, two fundamental algorithms for computing an MIS in general graphs. Also, we try to understand the effect of probability of a node getting selected by Luby’s algorithm on the number of rounds required by algorithm to finish. We run these algorithms on different types of graphs, namely Random, Regular and Bipartite Graphs.

Abstract

Today, large amount of audio data is available on the web in the form of audiobooks, podcasts, video lectures, video blogs, news bulletins. In addition, we can effortlessly record and store audio data such as read/lecture/impromptu speech on hand-held devices. These data are rich in prosody, provide a plethora of voices to choose from, and their availability can significantly reduce the overhead of data preparation involved in building general purpose synthesizers, thus helping to rapidly building synthetic voices. But, a few problems such as the following are associated with readily using this data for speech synthesis (1) these audio files are generally long and audio-transcriptions alignment is memory intensive (2) available corresponding transcriptions are approximate, (3) many times no transcriptions are available at all, (4) the audio may contain disfluencies and non-speech noises, since the audio is not specifically recorded for building synthetic voices, and (5) if we obtain automatic transcripts, they are not error free. Earlier works on long audio alignment which addressed the first and second issue generally preferred reasonable transcripts, and mainly focused on (1) less manual intervention, (2) mispronunciation detection and (3) segmentation error recovery. In this thesis, we used a public domain large vocabulary automatic speech recognition (ASR) system to obtain transcripts, followed by confidence measure based data pruning which together address the five issues with the found data, and also ensure the above three points. For proof of concept, we built voices in English language using audiobook (read speech) in female voice downloaded from Librivox and lecture (spontaneous speech) in male voice downloaded from Coursera using both reference and hypotheses transcriptions, and evaluated them in terms of intelligibility and naturalness with the help of perceptual listening test on Blizzard 2013 corpus. The results of subjective intelligibility and naturalness test show that we can build voices of quality comparable to those built using reference transcriptions with the use of automatic transcripts and confidence measure based data pruning.