Abstract

The elucidation of order parameter/reaction coordinate for molecular dynamics (MD) without any a priori knowledge is an open and illposed problem. Several methods for extracting the order parameter like Bayesian analysis, genetic neural network etc. require some input information (like reactant and product state) about the system or they involve extracting thermodynamic/statistical quantities (like “free energy”), as a function of a “progression coordinate”, which is typically not known beforehand. We have implemented a recently developed nonlinear dimension reduction and spectral clustering technique “diffusion map” (DM) on equilibrium trajectory of alanine dipetide and non-equilibrium trajectory of β-hairpin. DM is successfully able to extract small number of good order parameters known as “Diffusion Coordinate” (DC), without any a priori knowledge. These extracted DC’s are dynamically meaningful and also show good correlation with physical parameters. We have integrated two features in DM: i) coarse graining of the graph and ii) Nystr¨om extension; these features reduce the computational cost while preserving the essential features of the dataset. Further more, we have also addressed the solutions of sampling problem in MD. We have proposed new methods to enhance the sampling of phase space along the extracted DC. In one method, we have applied a bias force to push the system (particle/biomolecule) out of the free energy minima and this bias force is a function of DC. We have successfully implemented this method on M¨uller-Brown potential. In another method, we enhance the sampling of phase space by aim-less shooting approach (without using any biased force/potential) and successfully tested this method on alanine dipeptide system.

Abstract

Many state-of-art technique in robotics such as mapping of environment, robotic exploration, localisation of robot, SLAM etc. depends a lot on effective segmentation of ground plane. An autonomous robot using camera as primary sensor should contain a processing module that can clearly indicate the sharp boundary between the obstacle and ground plane with high precision. A better understanding of environment plays a vital role in most of the robotics application. To build a map or to explore in an unknown environment or to localise a robot, all of these requires fine metric details which can only be improved if you have a clear knowledge of ground plane. Detection and segmentaion of small obstacle of the order of a few centimeters is very difficult even with sophisticated depth sensors such as laser range finders. This thesis presents an effective approach to segment ground plane and discover small obstacles in an indoor environment by exploring some of the probabilistic graphical model technniques. Probabilistic graphical models such as Bayesian Network and Markov Random Field have been used with a robotic application point of view. The Bayesian Network was used here by fusing appearance and geometric (homography) cues which provides a way for accurate and reliable ground plane segmentation in significantly difficult situations. Herein the appearance and homography based error models are appropriately weighed to come up with the eventual class probability of a feature track. It was observed that bayesian network works effectively in most of the cases but do fail in certain cases as posterior tends to saturate over time and sudden change in environment does not gets reflected quickly. So, to improve further on my problem, I came up with a novel pipeline for segmentation of ground plane that makes use of several state of the art modules culminating in a Markov Random Field (MRF) based graph cut formulation that provides for optimal classification. While sharing similarities to the problem of appearance based image segmentation, obstacle detection when approached as a traditional segmentation problem, suffers from the following pitfalls 1) Obstacles having same appearance characteristics with the navigable ground plane regions tend to be classified as ground plane regions. 2) Ground Plane regions that change their appearance can be classified as non-ground regions. The algorithm that uses MRF avoid both the above pitfalls and shows robust ground plane segmentation, and detection of obstacles, big and small in diverse environments. By using the pipeline discussed in the thesis, it is possible to detect obstacle as short as 2-3cms as far as 7m away from the camera at real time rates. vi

Abstract

Natural language parsers lie at the core of various natural language processing (NLP) systems such as machine translation (MT), question answering (QA), information extraction/retrieval (IE/IR), etc. Building accurate, wide-coverage parsers has been one of the main goals in NLP research for the last two decades. As a result, there exist today highly accurate parsers based on a variety of approaches not only for English but also for a few other languages. Statistical parsers have proven to be most effective both in terms of coverage and precision. However, statistical parsers whether constituency-based or dependency-based make certain independence assumptions about sentence structure. Simply put, statistical parsers of all hues assume that sentence structure can be factored into smaller sub-structures which can be predicted independently varying only in the type of factorization. Although such assumptions are necessary in order to ensure tractability of parsing algorithms, they are not linguistically tenable since we know that there is a significant amount of interaction among the factored sub-structures. There are a number of linguistic phenomena such as subject-verb agreement, verb argument structure and coreference of noun phrases where information about the linguistic relationship is spread over more than one sub-structure. In other words, in all these cases, the cues for parsing one sub-structure correctly can come from another sub-structure. Most state-of-art statistical parsing models which make independence assumptions about sentence structure fail to capture such non-local phenomena. In this thesis, I study two approaches to overcome this limitation and make use of non-local features that encode greater contextual information during parsing. The first approach is based on the technique of discriminative reranking which consists of two steps: increasing the width of the search beam to allow more candidate parses and then employing a classifier that can use non-local features to rank the candidate parses and pick the best among them. The second approach is based on the technique of ensemble parsing whereby parsing models with complementary strengths/weaknesses can be combined to obtain best possible parsing performance. In particular, I study the stacking approach to combining parsers at learning time. The explored experimental setup allows for non-local features defined over the output of one (or more) parser(s) to be used while training a graph-based parser. In my experiments on discriminative reranking and ensemble parsing, I build several highly accurate parsers for English which can be directly used in in-house large-scale English-to-Indian language machine translation systems. I combine freely available parsers using the ensemble technique of re-parsing to build the best performing model for dependency parsing of English. This high accuracy dependency parser for English is available under GPL and can be deployed in a wide array of NLP systems. In my experiments on stacking dependency parsers, I build stacked parsing models with different combinations of non-local features for three Indian languages– Hindi, Telugu and Bangla –to study the influence of each feature in improving parsing performance. The accuracies of the best performing of these models are the state-of-art accuracies for parsing these Indian languages. Although I do not come up with a entirely new way of overcoming the limitation of feature locality in statistical parsing frameworks, the insights gained from the studies presented in this thesis can inform efforts aimed at development of contextually rich models of syntactic parsing.

Abstract

Information about blood flow in the brain is of interest to detect the presence of blockages and ruptures in the vessel network. A standard way of gathering this information is to inject a bolus of contrast agent into the blood stream and imaging over a period of time. The imaging is generally done over an extended period of time (tens of minutes) during which a patient can move which in turn results in corruption of the acquired time series of volumes. This problem is often observed in dynamic magnetic resonance (MR) imaging. Correction for motion after scanning is a highly time-intensive process since it involves registering each volume to a reference volume. Moreover, the injected contrast alters the signal intensity as a function of time and often confounds traditional motion correction algorithms. In this thesis, we present a fast and efficient solution for motion correction in 3D dynamic susceptibility contrast (DSC) MR images. We present a robust, multi-stage system based on a divide and conquer strategy consisting of the following steps: i) subdivision of the time series data into bolus and non-bolus phases depending on the status of bolus in the brain, ii) 2D block-wise phase correlation for detecting motion between adjacent volumes and categorizing the corruption into four categories: none, minimal, mild and severe depending on the degree of motion and iii) a 2-pass, 3D registration consisting of intra-set and inter-set registrations to align the motion corrupted volumes. The subdivision of time-series into distinct sets is achieved using Gamma variate function (GVF) fitting. The dynamic non-uniform variation in signal intensity due to the injected bolus is handled by employing a clustering-based identification of bolus-affected pixels followed by correction of their intensity using the above GVF fitting. The proposed system was evaluated on a real DSC MR sequence by introducing motion of varying degrees. The experimental results show that the entropy of the derived motion fields is a good metric for detecting and categorizing the motion. The evaluation of motion correction using the dice coefficient measure shows that the system is able to remove motion accurately and efficiently. The efficiency is contributed to by the proposed detection as well as the correction strategy. Including the detection prior to existing correction methods achieved a savings of 37% in computation time. Whereas, when the detection is combined with the proposed correction stage, the savings increase to 63%. Notably, the above performance was found to be had with no trade-off between accuracy and computation cost.

Abstract

An autonomous personal assistive robot should be able to interact with humans and objects at high level, by understanding the semantic constructs in the environment. Robot should be able to fetch, place, move objects in the environment. This involves detection, recognition and manipulation of the object across the semantic construct. These semantic constructs can be defined on wide range of categories, from building, room, furniture to object level. This semantic understanding can be acheived by perceiving the environment with lot of details and then represent it in the form of a map. Obstacle location details should be available to the metric level for robust navigation of the robot. There are many mapping paradigms in literature and semantic mapping is recently focused for this purpose. Assuming that robot is able to perceive the environment in terms of semantic constructs like lab, room, table and chairs, the performance of recognition of any object is entailed to the position or the view of the robot’s camera which is under motion. Object search also depends on the efficiency and robustness of the recognition algorithms for a moving camera sensor. This thesis explores two problems: 1) How to place/move the robot in a indoor environment in order to efficiently search for an object? 2) How to use visual saliency models for practical indoor settings? Assuming that the map of the environment with semantic constructs is available to the robot, an exploration strategy has been formulated to search for an object in optimal way. Having done this for an ideal setting, visual attention models have been analysed for the practical indoor settings. In the first part, manual way of extraction of the semantic constructs using Kinect sensor in the form of 3D map is explained. Since these semantic constructs reduce the search space for the robot from the entire map to certain locations, they are defined as ”potential locations” for the search. This information is used to explore for the object in the environment. Viewpoint of the Kinect sensor is used as the primary ingredient in this formulation, so as to place the robot to view potential locations as highly as possible. At every instant a next best viewpoint is calculated based on the explored and un-explored semantic contructs in the map. Exploration is continued till the object is found or till all semantic constructs are explored. Comparisons of this exploration is shown with two other methods and their timings have been captured to substantiate our claim. Secondly, visual attention models have been explored to provide cognitive advantage to solve the above problem for a practical setting. Existing visual saliency models that mimic the attention regions, have been used to localize the single/less clutter regions in the scene and cannot be directly used to indoor settings. Influence of depth in the salient region detections have been experiments and cases have been derived. A new saliency model called 3D saliency has been proposed in this work and fused with the existing saliency models to derive RGBD-saliency. This improves the performance for indoor settings with an average improvement of 9% across all the methods. Fusion process uses SVM learning. It is explored on how this saliency can help in object search formulated earlier and pave ways of improvements in the future work.

Abstract

No Results Found

Abstract

The interplay of three biomolecules, DNA, RNA and proteins provide complexity and richness to the biological world. Proteins have long been the primary research focus among various groups across the world. The nature of their internal dynamics, apart from the biochemical and functional aspects, has attracted enormous attention. Investigation of the factors governing the dynamics can give valuable insights into protein activity or functions. Advanced theoretical and experimental techniques contribute to the better understanding of protein structures, stabilities and internal dynamics. Computer simulations provide with an excellent alternative to interpret and complement the experimental investigations and provide a molecular level insight into protein structure, dynamics and functions. This atomistic-level information obtained from biomolecular simulations can be used to derive various experimentally measurable macroscopic observables, including heat capacity, free energy, by using statistical mechanics. Like harmonic solids, the protein atoms execute harmonic vibrations around their equilibrium positions, at low temperatures. Upon heating, the amplitude of these harmonic motions increases linearly with the increase in temperature up to a critical temperature (Tg) beyond which a transition from the glass-like phase to liquid-like phase is observed. Atomistic MD simulations calculate dynamical properties relevant to harmonic-to-anharmonic transition which are attributed to flexibility in proteins and onset of biological activity. The glass transitions have been reported in proteins, DNA and RNA by various experimental and simulation studies. The glass-transition temperature (Tg) is observed at about 220 K. Recently, a low-temperature anharmonic transition has been observed in many proteins at around 150 K, that is much below the Tg. Reasons for the same have not clearly been stated. This work is an attempt to understand the underlying factors which contribute significantly to this behavior. The present work emphasizes on the role of MD simulations to understand the factors that contribute to the anharmonic transitions of proteins. Four homomeric polypeptides, polyglycine, polyalanine, polyisoleucine and polyphenylalanine have been analyzed for the dynamical behavior of each kind of side-chains to the anharmonic transitions over a range of temperatures (between 10K and 300K in steps of 10K). The dynamical properties of proteins are largely attributed to the amino acid side-chain groups as is exemplified by the system under consideration. Polyglycine, representing backbone-only polypeptide shows only solvent-dependent dynamical transition, while as polyalanine, polyisoleucine and polyphenylalanine shows a low-temperature onset of anharmonicity along with the dynamical transition at the critical temperature (Tg). The results obtained from our simulation studies correspond exactly with the experimental data from elastic incoherent neutron scattering (EINS) studies.

Abstract

Identifying subjective text and extracting opinion information about different entities from News, Blogs and other forms of user generated content like social media has a lot of applications. We wish to address this challenging task of mining opinions about different entities like organizations, people and places from different languages. But, it is known that resources and tools for mining opinions are scarce in many languages. In our research, we try to address resource scarcity problem by designing approaches which leverages resources from rich resource language like English for opinion mining. Named Entities, adjectives and verbs treated as possible opinion words are extracted from English in a comparable corpora. Possible opinions on targets (mainly people) represented by adjectives, verbs are translated and transliterated to resource-scarce languages. Initially, these transformed words are used to identify subjective sentences in resource-scarce languages. Though this approach is unsupervised, subjective and objective text classification at sentence-level can be improved using a supervised method. Accuracy of sentence-level subjectivity detection is further improved using language independent feature weighting and selection methods which are consistent across different languages. Once the subjective sentences are identified, they are used to create a subjective language model (SLM). While transliterated and translated words are used to form structured opinion queries (OQs) using inference network (IN) for retrieval to confirm the opinions about opinion targets in the documents. Experiments are performed at sentence-level and fine-grain level using Hindi comparable corpora to evaluate the effectiveness of approaches in finding opinions. Even though experiments are performed on Hindi, approach can be easily extended to other resource-scarce languages. Results have shown that for fine-grained opinion mining, OQs and SLM with IN framework are effective for opinion mining tasks in minimal resource languages when compared to other retrieval approaches. While Entropy based category coverage difference criterion (ECCD) feature selection method with our proposed feature weighting methods along with Naive Bayes Multinomial classifer is consistent for sentence-level subjective classification in Hindi, Telugu and other languages including English and European languages.

Abstract

Understanding the process of protein folding/unfolding has been a challenge for more than 50 years. Atomic level understanding requires huge computational power to gain insights in the process of unfolding. The emergence of single-molecule force measurement experiments has facilitated a better understanding of protein folding pathways and the thermodynamics involved. Experimentally, techniques like atomic force microscopy and optical tweezers are used to study the mechanical properties of single molecule. A computational method that closely mimics these experiments is steered molecular dynamics (SMD) simulations, which can provide atomistic level insight into the unfolding pathways. Recent experimental studies have shown that combinations of single-molecule experiments with traditional methods such as chemical and/or thermal denaturation yield additional insights into the folding phenomenon. In this study, results from extensive computations (a total of about 60 SMD simulations with a total length of about 0.4 μs) that address the effect of thermal perturbation on the mechanical stability of the I27 domain of the protein titin are reported. A wide range of temperatures (280 – 340 K) were considered for the pulling, which was done at both constant velocity and constant force using SMD simulations. The distance between the N- and C- terminal Cα atom was considered as the reaction coordinate for the present study. For I27 domain, maximum force of unfolding decreases with respect to increase in temperature, but the extension corresponding to this force remains similar, indicating the validity of end-to-end distance as reaction coordinate. Similar trends were observed for the most probable unfolding force and are in good agreement with the available experimental data. It is observed that the rate of unfolding increases with an increase in temperature after the initial barrier is crossed in the constant force simulations. This study identifies two competing pathways for the mechanical unfolding of I27 both at constant velocity and constant force SMD simulations, and illustrates the significance of combining various techniques to examine protein folding.

Abstract

Due to the digital and information revolution we are witnessing presently, there are a huge and continously increasing number of images present on the Internet. For example, a query for ``Eiffel Tower" on Google Images returns more than two million images. The easy accessiblity of this data provides us with unique opportunities to mine the contents of these images not only to do automatic organization, but also for providing interactive interfaces to browse, explore and query. This task is challenging given the massive size and the continuous growth of the collection. To add to this, these collections are taken in varying imaging conditions, with different cameras, at different resolutions, from different perspectives and have different degrees of occlusions present in them. Hence, for image collections even the simplest of tasks such as finding matching images turn out to be hard. The Computer Vision community has been actively designing and redesigning algorithms to overcome these challenges. One of the most widespread and noticable idea employed is that of extracting robust, invariant and repeatable local features in the images, followed by the subsequent quantization of the feature space as visual words. The similarity of images is gauged by the correspondence and similarity of thier local features. Verifications of the matchings is done to eliminate spurious matches. Building a data structure such as an inverted index over these visual words can catalyse the process of discovery of matching features. This mining of similar images by matching features, forms the basis of all high level algorithms such as clustering, skeletonization, summarization etc. which help in the organization, exploration and querying of these image collections. This thesis presents two novel algorithms which help in achieving this goal. First, we introduce a novel indexing scheme that makes it possible to do exhaustive pairwise matching in large image collections. The quantization of image features and thier indexing provide on a limited amount of leverage for speeding up the image matching process which depends upon the sparsity the posting lists. This sparsity is controlled by the number of visual words used which after a point cannot be increased arbitrarily without affecting recall. Our scheme, generates higher order features by pairing up nearby features and encoding their affine geometry. This provides a much larger feature space to index which can be subsequently reprojected to any desired size by defining appropriate hash functions. We implement our indexing scheme by providing an analogy with Bloom filters. The higher order features extracted in the images are inserted into their respective equally sized Bloom filters using a single hash function. This unformity in Bloom filters allows for only a single inverted index to be able to index the hash buckets of all the Bloom filters, and thus providing a simplified interface to implicity query all the Bloom filters. We choose the size of these Bloom filters to be in proportion to the size of the database. This enables us to do querying in constant time, since the average size of the posting lists becomes constant. Also, the use of such large implicit Bloom filters is able to sufficiently mitigate the negative effects of using a single hash functions. As a result, we are able to do exhaustive pairwise matching over large databases of upto 100K images in linear time complexity. Second, we present a fast and easy to implement framework for browsing large image collections of landmarks and monumental sites. The existing framework ``Phototourism" would require doing a reconstruction of the whole scene by employing Structure from Motion package called Bundler. This requires pairwise matching required to generate tracks of matching features across images. Next an incremental approach is applied, starting with a seed reconstruction and adding more matching images into the reconstruction. This, however, requires continous refinement of the whole reconstruction using a computationally expensive procedure called bundle adjustment. The pairwise matching and bundle adjustment become the limiting factors in scaling this technique to large image collections. To overcome the issues faced with ``Phototourism", our framework employs independent partial reconstructions of the scene. We use standard Bag of words model and indexing techniques to determine closest neighbours of each image in the collection, and do a local reconstruction corresponding to each image using only the neighbouring images. This requires us to only solve multiple simple reconstructions problems instead of one large reconstruction problem, making it computationally more tractable. Our browsing interface hops from one reconstruction to another to give the user an illusion of browsing a global reconstruction. Our approach also makes it easy to adapt to growing image collections, as adding an image only incurs a