Abstract

Treebanks are major resources for developing various natural language processing applications. Dependency framework has proved to be successful for handling free word ordered languages. Indian languages are mostly morphologically rich and are relatively free-word order (MoR-FWO) languages. There has been a recent surge in addressing parsing for morphologically rich languages. Most of the work in parsing Indian languages has been done at the chunk level. Full sentence dependency parsing is not explored in detail till now. In this work, we start our experiments to improve dependency parsing accuracies for Indian languages (Hindi, Telugu and Bangla) as part of ICON 2010 Tools Contest. We explored MaltParser, a data driven parser, on grounds of large feature pool consisting of morphological and syntactic features. We prepared different parser configurations by considering different parsing strategies, classifiers and feature templates. Additionally for Hindi, we utilized shallow parser output as features and tried to incorporate minimal semantics. We selected the best onfiguration for each set of data and were able to produce the best average accuracy in the ICON 2010 Tools Contest. We achieved Labeled Attachment Scores (LAS) of 88.63, 70.12, 70.55 on the fine grained data of Hindi, Telugu and Bangla respectively. Subsequent to this, we moved to developing a robust rule based intra-chunk dependency annotator which generates full sentence dependency treebank from interchunk dependency treebank by marking dependencies inside the chunk. We developed the detailed intra-chunk dependency guidelines for Hindi. The rule-based annotator uses these guidelines as the basis for framing rules. The rule based annotator was further improved by using the output from MaltParser, a statistical parser. The tool has the state of the art LAS, Unlabeled Attachment Score (UAS) and Labeled Score (LS) accuracies of 98.17, 98.81 and 98.63 respectively. As we prepare a full sentence dependency tree by marking intra-chunk relations on an inter-chunk dependency tree, we call this process as ’Expansion’ of inter-chunk dependency treebank. Dependency treebanks are capable of containing lots of information apart from the syntactic information and therefore make a rich resource for other linguistic annotations on top. These annotations happen layer wise. For example, the present Hindi dependency treebank is enriched with propbanking and minimal semantics information. These layers of annotation happen in parallel on the initial version of dependency treebank. While these layers are being annotated, the base layer (initial version) undergoes further changes in the tree structure either due to change in guidelines or due to correction of annotating errors. Hence it is essential to merge the additional layers of linguistic information onto to the latest version of dependency treebank. We concentrated on building a simple tool which extracts these additional linguistic information and maps on to the newer version of dependency treebank. We call this process ’Merging’ of different versions of same dependency treebank.

Abstract

Today, Infrastructure-as-a-service (IaaS) providers are trying to minimize the cost of data center operations, while maintaining the Service Level Agreements (SLAs). This can be achieved by one of the advanced state-of-the-art services of virtualization - the live migration capability. Live migration is defined as the process of transferring an active virtual machine (VM) from one physical machine to another without any disconnection. This is achieved by transferring all of the encapsulated states of the VM from one host to another. Thus, it has become an essential tool for efficient management of resources in a data center by enabling server consolidation and load balancing among other possible benefits with a minimal effect on client services. There are two classical migration techniques, namely - pre-copy and post-copy, which employ different memory transfer mechanism during the offloading of a VM. In the case of pre-copy, the memory is iteratively transferred from the source to destination until the remaining dirty memory along with the other device states is left to be transferred in a shorter last iteration. While in the case of post-copy, all the device states except memory is immediately transferred to the destination. Source VM’s memory is only transferred if needed by the running VM. However, these existing techniques suffer from high network bandwidth utilization, large network data transfer, large migration time as well as destination’s VM failure during migration. In this thesis, we propose a novel hybrid live migration technique by combining the existing pre-copy and post-copy approaches. Our hybrid technique is a fast, efficient and a reliable migration technique compared to its counterparts. This technique provides a reasonable solution to high efficiency and less disruptive migration scheme by utilizing all the three phase of the process migration. For effective network bandwidth utilization and reducing the total migration time, we introduced a learning phase to estimate the writable working set (WWS) prior to the migration process. Only those pages which are not present in the estimated WWSare transferred to the destination initially. Pages from the estimated WWS are retrieved from the source machine through page faults as the virtual machine resumes execution on the destination. Our learning technique helps us in achieving almost a single time transfer of the pages when compared against the naive hybrid technique. Several other optimizations like compression, block based paging, page pre-fetching and push phase parallel transfer are incorporated in the migration scheme. Similar to the post-copy technique, hybrid live migration results in virtual machine failure if the destination machine fails during the pull phase of migration. We introduced reliability into the pull phase by using a fail-stop model which periodically checkpoints the virtual machine state during the pull phase. If the destination machine fails during the pull phase, the virtual machine can be recovered on the source host from the latest check pointed state on the disk. We implemented the proposed hybrid approach on the top of a KVM hypervisor and conducted experiments on diverse workloads. Our compression based hybrid learning approach decreases the total data transfer by 1:83 - 7:47 times for pre-copy, and 1:16 - 12:21 times for post-copy. And it decreases the total migration time by 1:42 - 9:84 times for pre-copy, and 2:43 - 8:57 times for post-copy.

Abstract

All visible objects have shape and texture. The main aim of computer graphics is to represent and render real world objects efficiently and realistically. To make the objects look realistic from a geometric point of view, we have to make sure that the shape and texture of the object are accurate. In practice, shape is either hand crafted using 3D modeling tools such as Blender, or is acquired from real world objects using 3D reconstruction techniques. Texture is the second aspect of appearance that must be ensured to make the rendered objects look real. The texture has to be pasted on the surface in such a manner that it perceptual corresponds to the correct part of the mesh. This process of pasting the texture on the surface of a mesh model is called Texture mapping. Texture mapping can be done in two ways. First way is to texture a surface by synthesizing the texture directly on the surface. The second method is to wrap a synthesized texture around the surface and cut and merge the seams so that it fits correctly on the surface. To visualize this problem we can think of texture as a cloth. The first method can be thought of weaving around the body to fit it exactly like a sweater, while the second method is like cutting and stitching an already woven cloth according to the shape of the mesh model. In this thesis we propose a new method that follows the second approach. The primary goal of our method is to map a texture on to large mesh model at interactive rates, while maintaining the perceived quality. The primary technique for mapping a flat texture (image) onto an arbitrary shaped mesh model is to parameterize the shape, which defines a mapping from points on the mesh surface onto a 2D plane. When parameterizing these mesh models, we try to maintain the geometric correspondence between the mesh vertices intact to reduce the distortion of the texture. Typically, parameterizing a mesh model involves solving a set of linear equations representing the geometric correspondence of the triangles. The approach involves defining an energy function for the mapping and searching for a global optimum which minimizes the distortions during the mapping. Such methods are capable to achieving texture mappings that has high perceptual quality. However, typical energy minimization procedures are computationally expensive and cannot be applied for real time applications or with large mesh models. As the size of mesh models increase, global optimization techniques employed by the parameterization methods tend to become computational bottlenecks. To make parameterization a real time procedure for large meshes, we propose a greedy approach that operates on local optimization function rather than the traditional global optimization function. We express the surface in terms of local curvature and store these values in a priority queue, which is used to determine the portion of the mesh that is to be textured next. Our algorithm is simple to implement and can texture at approximately one million polygons per second on current day desktops. We show that our algorithm is robust to dynamically changing meshes and produces the same texture even when a part of the mesh is removed and brought back. This is an important feature because in case of optimized rendering of large objects, we cull out large parts of the model from rendering based on visibility, and render them again when these objects fall back into the view frustum. In such situations, re-texturing of previously seen parts should not change its appearance. The proposed algorithm is also not affected by a sudden change in the density of points on a noisy mesh surfaces. That is, the algorithm’s runtime complexity does not depend upon the complexity of the surface unlike most traditional parameterization algorithms. The time complexity is linearly related to the model size and it is not affected by the size of the texture. To complement the proposed texture mapping algorithm, we introduce a method to make a texture self tileable. This allows us to store only the texel structure, if the required texture is repetitive. We present qualitative and quantitative results in comparison with several other texture mapping algorithms. The proposed algorithm is robust in terms of the output quality and can find applications in different scenarios such as rapid prototyping, where you require interactive texture mapping rates and the ability to deal with dynamic mesh topology. It can also be used for applications such as large monument visualizations, where we need to deal with large and noisy mesh models that are generated using techniques such as multi-view stereo.

Abstract

The current state-of-the-art text-to-speech systems use either statistical parametric synthesis or hybrid systems (a combination of statistical parametric synthesis and unit selection synthesis). In statistical based techniques, phones (along with their context) are used as basic units. A major issue is to model the trajectories and reduce the over smoothing effect. Longer units such as syllables are not straight-forward to model when compared to phones. In this thesis, we show how syllable HMMs are effective in generating a HMM based TTS system HTS). We will explore the issues in modeling these sub-word units, clustering them with different categories of features including contextual information of the phone, position and manner of articulation, linguistic and syntactic features. We will also present the advantage of using syllable based models in explicitly capturing the prosodic based characteristics. Later, we will propose an approach using longer size units such as syllable, and build a statistical template for each syllable using dynamic programming to inherently capture the trajectories. Two types of statistical templates are being used for synthesis: average and median. The technique can also avoid source modeling, as one could use median templates as exemplars to build concatenative speech synthesis system. Also, the effects of using local constraints in DTW has been explained with respect to average template based speech synthesis system. Experiments are conducted on Telugu, Kannada, Hindi and English speech databases. The subjective evaluations show that the statistical template based approach performs reasonably good. Finally, different prosody modification approaches such as time-domain and frequency-domain with their limitations are described. Mainly, prosody modification using instants of significant excitation and Mel-cepstral vocoder are explained in detail and a comparison of both the techniques over non-linear modification is discussed for integrating into TTS systems.

Abstract

In this thesis we present a mathematical model for applications in the area of energy. The mathematical model is based on Kalman Filter prediction and correction technique. Kalman Filter has been applied to predict the maximum power point of a solar photovoltaic array and also to forecast the load and schedule the load for smart grid. Maximum Power Point Tracking has been the key area for solar photovoltaic array. A lot of research has been going on in this area so that efficient solar inverters can be built for power transmission with minimum loss. MPP tracking requires a prediction and correction model when done in real time; hence we opted for Kalman Filter algorithm. Two types of Kalman Filter algorithms have been used for MPPT. The one is considering the whole system to be linearly varying i.e. considering somewhat ideal behavior of the panels hence we have used Discrete Kalman Filter approach for this purpose. However, in the real situation the behavior varies with irradiance and temperature hence ideally the system shows a non linear behavior. Hence, for that purpose we have used Unscented Kalman Filter approach. Using either of these approach the maximum power point tracking (MPPT) becomes much faster than using the conventional Perturb &Observe approach specifically in case of sudden weather changes. In this thesis comparative analysis of both the algorithms being implemented on FPGA is presented. Simulations have been performed under optimal conditions as well as under cloudy conditions i.e. falling irradiance levels. Using the linear Kalman filter the maximum power point of a solar PV array has been tracked with an efficiency of 97.11% while using the Unscented Kalman filter technique the maximum power point of the same solar PV array is tracked with higher efficiency of 98.3%. However, the maximum power point has been tracked at a much faster rate i.e. 4.5 ms using the linear Kalman filter approach as compared to the unscented Kalman filter approach which tracks maximum power point at 11 ms which is in turn faster than existing generic Perturb and Observe approach which takes 15ms to track the maximum power point . The system has been implemented on Altera EP2C20F484C7 FPGA board to check the number of resources being used. The FPGA based Kalman Filter has been used for load forecasting and that to focusing on short term load forecasting which leads to load scheduling for smart grid. With smart grids the forecasting becomes much easier as we would be receiving load consumption data at the household level. The information of load consumption can be obtained from smart meters already installed in smart grid. This problem also requires a good prediction and correction model so we again took Kalman Filter algorithm in consideration. For this case we have used only Discrete Kalman Filter algorithm based upon the parameters we have considered for load forecasting approach. The algorithm proposed in this paper uses load consumption and temperature of previous few days as parameters for estimation and this forecasted data is used for scheduling purpose. Estimation is done separately for Weekdays & Weekends/Public Holidays. Using the proposed algorithm the load has been estimated with absolute mean percentage error around 1.5% and the algorithm for load scheduling has been successfully implemented on the logic of FPGA.

Abstract

Processing a sentence for any practical application requires complete understanding of the syntactic and semantic structure of the sentence. Natural language parsers, are used to perform formal analysis of a sentence into its constituents(words or phrases), resulting in a parse tree showing their syntactic relation to each other. For example, which groups of words in a sentence go together as phrases and which words are the subject or object of a verb. Natural language parsers are generally two types, Rule based parsers- often constructs a parser given a grammar and data-driven parsers - construct a parser given a treebank (sentences with the whole syntactic information annotated in them in the form of tags and dependent relations). The accuracy of these parsers, both rule based and data driven often depends on the complexity of the sentence they are parsing. The complexity varies from the ambiguous structures/words, out of vocabulary words, loosely annotated syntactic information of a sentence like Parts-of-speech tags, syntactic relation between phrases or words etc. In case of data-driven parsers, they use knowledge of language processes from the sentences they learn on to produce the most likely analysis of new sentences, hence it is very important for the parsers to extract enough and proper information from the sentence before it parse. Consider an example like below where all the syntactic information like subject, object, verb etc is present in the sentence and it is easy for any application to extract complete information. Jon and Mary went to hospital Now, consider the following example ‘John can sing a song, and Mary can too’ Sentences like these are very common to appear in the treebanks, as the treebanks are created from a wide range of sources like articles, books, discourses. As mentioned earlier, to accurately predict the syntactic structure of these sentences, it needs the syntactic information annotated in them. Now, if we look at the example above, the complete syntactic information expected from the parsers are ‘John can sing a song, and Mary can (sing) too’ In the first example, ‘John can sing a song, and Mary can too’ Whether or not the verb ‘sing’ is included in this sentence is up to the speaker and to communicative aspects of the situational context in which the sentence is uttered. But, for the parser, the verb ‘sing’ along with its information like POS tag and its relation with other elements in the sentence, very important to be part of the sentence to parse it properly. The missing elements not only create a problem for parsing the sentence, but for any application that requires sentence syntactic understanding, for instance, information extraction, question-answering, and related semantic tasks, machine translation, parts-of-speech tagging, morphology etc. The more precise and detailed our predicate argument structures are (including empty categories), the more complete our event descriptions will be, and therefore the more effective our semantic processing techniques will be. We call these missing words/phrases as ‘Empty Categories’ or ‘Null Elements’. In this work, empty categories are retrieved in two ways: 1. Retrieve empty categories in sentence itself 2. Retrieve empty categories in parse trees while parsing Inserting in the sentence is handled statistically with the help of machine learning algorithms and by leveraging this method as a postprocessing step, i.e empty categories are inserted on the parser output. Then we will see how to detect and retrieve empty categories in a data-driven parser itself. We will then move to handle empty categories in Hindi dependency treebank by analysing and classifying the empty categories and then identify various discovery procedures to automatically detect the existence of these categories in a sentence. For this we make use of lexical knowledge along with the parsed output from a constraint based parser. Through this work we show that it is possible to successfully discover certain types of empty categories while some other types are more difficult to identify. This work leads to the state-of-the-art system for automatic insertion of empty categories in the Hindi input sentence and a generic approach to handle empty categories in any language dependency treebanks.

Abstract

The past decade has witnessed the emergence of participatory Web and social media, bringing together people in many creative ways. Millions of users are playing, tagging, working, and socializing online, demonstrating new forms of collaboration, communication, and intelligence that were hardly imaginable just a short time ago. Social Media refers to interaction among people in which they create, share and exchange information and ideas in virtual communities and networks. Social Media also helps reshape business models, sway opinions and emotions, and opens up numerous possibilities to study human interaction and collective behavior in an unparalled scale. In the study of complex networks, a network is said to have community structure if the nodes can be easily grouped into sets of nodes (even overlapping) such that each set of nodes is densely connected internally. Community structure are quite common in real networks. Social Networks often include community groups based on common location, interests, occupation etc. Metabolic Networks have communities based on functional groupings. Citation Networks form communities by research topic. Being able to identify these sub-structures within a network can provide insight into how network function and topology affect each other. In this thesis, we design an end-to-end framework for identifying communities from raw, noisy social media data. The framework is composed of two important phases. First, we introduce a new method of converting the raw, noisy social media data into a weighted entity-entity co-occurrence based consistency network. This includes a simple iterative noise removal procedure for cleaning the entity consistency network by removing noisy entity pairs. Secondly, we propose an approach for identifying coherent communities from the weighted entity network, by introducing novel notions of community-ness and community, based on eigenvector centrality. We use this framework to solve three different problems from two distinct domains. The first problem involves detecting communities from raw social media data and showing the application of the communities discovered in a recommendation engine setting. We use the framework for converting the raw data into a clean network and propose a highly parallelizable seed based greedy algorithm to detect as many communities as possible from the weighted entity consistency network. Our framework for community detection is unsupervised, domain agnostic, noise robust, computationally efficient and can be used in different Web Mining applications like Recommendation Systems, Topic Detection, User Profiling etc. We also design an recommendation system to evaluate our framework with existing state-of-art frameworks~cite{LDA,Farkas,bigclam} on a variety of large real-world social media data - Flickr, IMDB, Wikipedia, Bibsonomy, Medline. Our results outperform other frameworks by a huge margin. The second problem is, given a set of communities of discovered by traditional community detection methods~cite{Palla,Lancichinetti09}, we need to identify loose communities among them and partition them into compact ones. Here, we use the second phase of our framework to identify such loose communities using our notion of community-ness and propose an algorithm for partitioning such loose communities into compact ones. We illustrate the results of our algorithm over Amazon Product and Flickr Tag data and compare its superiority over the traditional community detection methods in a recommendation engine setting. The third problem is about showing the application of such framework in an Image Annotation scenario in presence of noisy labels. The problem of image annotation is defined to be, given an unknown image, we need to predict labels which best describes the semantics of the image. This problem is best solved in a supervised nearest neighbor setting, and we show how our framework can be used to address this problem, when the labels associated with training images can be noisy and redundant.

Abstract

Image matching is a well studied problem in the computer vision community. Starting from template matching techniques, the methods have evolved to achieve robust scale, rotation and translation invariant matching between two similar images. To this end, people have chosen to represent images in the form of a set of descriptors extracted at salient local regions that are detected in a robust, invariant and repeatable manner. For efficient matching, a global descriptor for the image is computed either by quantizing the feature space of local descriptors or using separate techniques to extract global image features. With this, effective indexing mechanisms are employed to perform efficient retrieval on large image databases. Successful systems have been put in place in desktop and cloud environments to enable image search and retrieval. The retrieval takes fraction of a second on a powerful desktop or a server. However, such techniques are typically not well suited for less powerful computing devices such as mobile phones or tablets. These devices have small storage capacity and the memory usage is also limited. Computer vision algorithms run slower, even when optimized for the architecture of mobile processors. These handheld devices, or so-called smart devices are increasingly used for simple tasks that seem too trivial for a desktop or a laptop and can be easily accessed on a smaller display. Further, they are more popularly used for taking pictures (gradually replacing the space of digital cameras) owing to the improved embedded camera sensors. Hence, a user is more likely to use a query image from the mobile phone, rather than from the desktop. This increases the scope of applications that demand real-time search and retrieval result delivered on a mobile phone. Many applications (or apps) on mobile smart phones communicate with the cloud to perform tasks that are infeasible on the device. People have attempted to retrieve images in this cloud-based model by either sending the image or its features to the server and receiving back relevant information. We are interested to solve this problem on the device itself with all the necessary computations happening on the mobile processor. It allows a user to not bother for a consistent network connection and the communication overheads associated with the search process. We address the range of applications that need simple text annotations to describe the image queried on the mobile. An interesting use case is a tourist/student/historian visiting a heritage site and can get all information about the monuments and structures on his mobile phone. Once the app is initialized on the device, the camera is opened and just pointing the camera or with a single click all the useful info about the monument is displayed on the screen instantly. The app doesn’t use the internet for communicating with any server and should do all computations on the mobile phone itself. Our methods optimize the process of instance retrieval to enable quick and light-weight processing on a mobile phone or a tablet. Firstly, we obtain a dataset of images relevant to the application’s scope, which is then curated and annotated for the task. This may seem a trivial task, but involves a great deal of manual labour when dealing with datasets of thousands of images. We efficiently address this with a batch annotation approach that results in detailed and part-wise image annotations. Then, we look into the primary problem of performing image retrieval on a mobile phone and propose variants of the Bag-of-words approach. A new indexing mechanism helps us to reduce the memory footprint by a large extent. It also reduces the computational requirements. Finally, we develop the mobile app using existing computer vision libraries for smart phones, keeping in mind a simple and user-friendly design for seamless use by a wide range of users. We validate our approach by using the standard benchmark datasets of Oxford-5K for our experimental purposes and also show results on Paris-5K and UKBench datasets. We demonstrate a working mobile app designed for a heritage site that successfully retrieves relevant information about a monument captured by the mobile phone.

Abstract

In Natural Language, Anaphora is an expression which refers to another expression in its context. This referred expression, called the antecedent provides the information for interpretation of the anaphora. In Natural Language Processing (NLP), Anaphora Resolution is the task of identifying the referent of the anaphora. Anaphora resolution is required in various NLP applications such as information extraction, summarization and Machine translation. While the task of anaphora resolution for English has been studied to a sufficiently great extent and various techniques have been proposed for it, the research for Anaphora resolution for Indian Languages has been very limited. Hence, in this thesis, we aim to develop resources and explore features and techniques for Anaphora Resolution in Hindi. There are three important contributions of this thesis. First, we developed an anaphora annotated corpus which is required for experiments in Anaphora resolution. Towards the development of this corpus, we proposed a scheme or framework for anaphora annotation. Our goal, with this scheme, is to identify and resolve various consistency issues associated with previous schemes or framework which are used for anaphora and co-reference annotation in English and other languages. Using the proposed scheme, we annotated anaphora references over Hindi Dependency Treebank. Second, we present a hybrid approach to resolve Entity-pronoun references in Hindi. Most of the existing approaches, syntactic as well as data-driven, use phrase-structure syntax for anaphora resolution, we instead, explore the utility of dependency structures as a source of syntactic information. In our approach, dependency structures are used by a rule-based module to resolve simple anaphoric references, while supervised learning algorithms are used to resolve more ambiguous instances using grammatical and semantic features. Our results show that, use of dependency structures provides syntactic knowledge which helps to resolve some specific types of references. Semantic information such as animacy and Named Entity categories further help to improve the resolution accuracy. Finally, we also conduct some preliminary experiments in Event anaphora and co-reference resolution. Similar to Entity anaphora resolution, for event and co-reference resolution too, we explore use of dependency structures in a rule based settings. Our experiments show that even with limited data and using simple syntactic and semantic constraints, reasonable resolution accuracy can be achieved for Event anaphora and co-reference resolution.

Abstract

This thesis was based on the idea of developing assistive systems for search and rescue and rehabilitation. Imagine a search and rescue scenario. Say there is an earthquake or a tsunami and there is lot of debris with people stuck under the debris. If we can improve the process of search then the rescue would come even faster and more lives would be saved. One part of the disaster management is to provide people affected with the disaster assistive systems to improve the quality of life. With this intention several robots and assistive systems are presented in this thesis.Real biological snakes have the ability to traverse several kinds of terrain. They can swim in water, climb trees, go over desert sand and go over step like terrain. So if me model robots with the snake structure in design then we can overcome challenging terrain which is typical to a rescue scenario. With that in mind we designed 5 different kinds of modular units of snake robot. We also were able to make the snake transition gaits autonomously from one part of the terrain to another. To over come slope like obstacles we designed a 6 legged robot that has a robotic spine. By controlling the amount of current in the robotic spine, we controlled its effective torque and were able to show compliance to slope while climbing up and climbing down. We also designed a universal simulator and controller plugin to reduce the fabrication time and simulate virtual models very close to its real counterpart robotic prototypes. Working on the modular design of the snake robot we engineered a new modular for modular snake like arms which was later extended to robotic hand. The robotic hand uses modular joints where each joint is composed of a pair of rolling magnetic spheres. In this attempt we ended up designing a robotic hand with the highest degree of freedom in the world. We have been working on assistive systems like camera mouse which allows a physically challenged person to use a computer. This research in HCI lead to controlling a snake robot with natural and intuitive gestures. We also designed a quake and crash alert system. We designed an intelligent flash light which can be used by a rescue worker to move in unknown places. The torch light uses a GPS,a laser projected micro projector and guides a person from a source to a destination. The work done here uses a combination of inputs from HCI and robotic system building to make search and rescue better. It also reduces the time for the human in loop during rescue