Abstract

Monitoring of the Earth System and its various constituents using both satellite and airborne Remote Sensing techniques is becoming quite widespread, but at the same time posing enormous challenges in managing the acquired data and processing it suitably to derive meaningful products and outcomes that can be used by different research disciplines that study the various components of the earth system. Earth Observation Systems (EOS) provide data at multiple resolutions which has been widely used in studies of environmental changes, natural resource management, and ecosystem and landscape analysis in general. With the development of new remote sensing system, very-high spatial resolution images provide a set of continuous samples of the earth surface from local, to regional scales. The spatial resolution of various satellite sensors ranges from 0.5 meters to 25,000 meters now. The development of efficient analysis methods of using these multi-scale datasets to improve land use/cover mapping, classification accuracies at the local class level and linking coarser and finer resolution datasets to get a complete understanding about the spectral unmixing processes has been the main theme of this thesis work. Image Classification is one of the most widely used approaches in deriving relevant information from remote sensing data by categorizing, either manually or automatically, all the image pixels into the appropriate classes or themes. Over the last four decades, a large number of classification techniques have evolved based on the spectral, spatial and temporal information associated with the satellite image data. While the spectral pattern recognition utilizes the pixel-by-pixel spectral/reflectance information, the spatial pattern recognition involves categorization of image pixels on the basis of their relationship with pixels in the neighborhood, and the temporal pattern recognition uses the change in time as an aid in the feature identification. Each of these approaches provide a certain set of information but are still inadequate in understanding the entire gamut of land cover, its changes and the processes that drive these changes. In the studies focusing on the land cover and land usage change analysis, the availability of very high resolution (VHR)/high resolution (HR) imagery for a particular period and interest region is always a challenge due to sensor revisit time and the high cost of acquisition and therefore, this research work was focused on increasing the utility of the cost and computationally advantageous frequently available lower resolution (LR) imagery. The statistical techniques developed during this research exploit the spectral and spatial information associated with the available multi-resolution satellite datasets and mainly focus on the sub-classification of the datasets at a specific resolution (preferably LR), to obtain sub-regions of high importance within the classified regions, which were validated using the datasets available at a different (preferably HR) spatial resolution.The widespread classification techniques provide us a global estimate of the class accuracies, which limits its utility (in a range of applications) and also limits the identification of sub-class regions which may have higher accuracy than the global class accuracies. In this research work, we initially focused on establishing a relationship between the multi-resolution datasets, with the aim of using them later for carrying out the experiments as well as their validation. The literature in the field of remote sensing has concepts related to pure pixel and mixed pixel regions, although for better understanding we also introduced an idea about the impure pixel regions. With regards to the pixel-classification problem in this thesis work, the classified pure pixel regions have similar ground truth class values as the classified outputs, classified mixed pixel regions match one of the ground truth class values in the obtained classified output and the classified impure pixel regions match none of the ground truth classes in the obtained classified output. Further, we establish the meaning of pure, mixed and impure pixel regions with regards to multi-resolution datasets and also introduce concepts like Near Pure Pixels (NPPs) and Near Purity Measure (NPM) for better understanding of the research areas tackled during the thesis work. We also proposed a Spatio-Spectral Unmixing framework, which reduced the number of approximations to the Linear Spectral Mixing model in Remote Sensing and helped in better analysis and visualization of mixed pixel regions, owing to improved classification accuracies. The results for the proposed methodologies have been shown as a proof of concept, and therefore datasets have been classified into fewer but higher importance class regions. The experiments conducted can be carried out on any available multi-resolution datasets, where the

Abstract

Several attempts have been made in the past for the creation of a comprehensive and structured ontology to enable better and efficient semantic analysis for web related common sense reasoning tasks such as Question Answering, Summarization, Word Sense Disambiguation, Analogy making, Classification, and so on. But, these approaches lack in a strong design paradigm for representation of facts about objects in general and artifacts in specific. Also, whereas the human cognition is ‘purpose’-based, none of the KBs (knowledgebases) built so far have taken the ‘purpose’ perspective into account. To address these lacunae in existing KBs, PurposeNet – a comprehensive KB that addresses all possible information requirements about artifacts with ‘purpose’ as the underlying principle for the design has been engineered. Artifacts have been described as being constituted of relationships and features. The features have been further designated as either a set of descriptions of the various morphological and anatomical characteristics of the artifact, or a set of actions that the artifact participates in during the course of its manufacture, use, and final disposal. Each of these actions has been described using a common generic frame, which is the special feature of our KB. The design is compact, with several directly and indirectly recursive relations among its constituents, which is the basis for networking in the ontology. Generality has been preserved in the design by way of class hierarchy implementing inheritance, and the design of an independent set of generic action frames for artifact-dependent as well as artifact-independent query processing. The design has been implemented on the transport domain using Web Ontology Language. A set of 10,00,000 assertions have been created using the ontology. All issues at development and implementation stages have been discussed. The ontology design has been validated, and the implemented ontology has been evaluated. This work also addresses the issue of detection and extraction methodologies for the relations prescribed in the artifact design. One relation of the artifact – namely, its ‘purpose’ has been taken as an example case for which various machine learning and pattern-matching methodologies described have been applied for detection with encouraging results. Relation extraction has also been implemented using two proven methods – typed dependency parse and surface pattern extraction. The comparative performance of these two methods has been evaluated for the extraction of the ‘purpose’ relation. Finally, this work presents some applications that showcase the usage of PurposeNet - i.e., a QA system, an enhanced expert system, an online web help, and the improvement of comprehension of passages by aiding existing Scripts. Each one of these demonstrates the usefulness of the PurposeNet KB.

Abstract

After a stall in improvement of clock speeds, High Performance Computing(HPC) community is looking for general purpose computing on graphics processing units(GPGPU). Due to their low cost, high performance per watt and evolving programming models they are becoming very popular not only among HPC community, but also for getting good performance on commodity devices like laptops and mobile phones. Unlike the traditional graphics rendering cards, now a days manufacturers are providing many other architectural features like cache and shared memory which make them promising for general purpose computing. A wide range of applications in the scientific and financial domains, benefit from the merits of the GPU architecture. GPUs offer an alternative machine architecture in three ways. GPUs provide, firstly, lots of cycles for independent parallelism, secondly, fast memory access under the right circumstances, and finally, fast mathematical computation at relatively low costs. Because of this different architecture there is a need to reinterpret the applications in a highly threaded manner. This architecture is a good fit for applications which have regular memory access patterns like dense matrix multiplication. But for non regular applications like list ranking, graph algorithms, sparse matrix calculations. Exploring such applications and accelerating them using GPUs is the need of the hour. Also most applications accelerated by GPU tends to use only GPU in computation. CPU’s role limits to just passing the code and data to GPU for computations and accumulating the results back. When GPU is busy executing given code, CPU stays idle. Hence CPU resources are not utilized properly. By carefully designing our applications we can get a significant speedup over the GPU-only implementation. To use both CPUs and GPUs in computation, tasks and data has to be divided efficiently. This partitioning of data is mostly dependent on the underlying CPU and GPU platform specifications. This is also referred to as static load balancing. Static load balancing through empirical or analytical methods have many drawbacks. While analytical methods are not available for most of the applications, empirical methods outputs the partition which is specific to the platform and hence making application hard to port efficiently. In this thesis we explore Aggregate risk analysis which is a stochastic simulation technique for portfolio risk analysis and pricing process using multi-core CPUs and many-core GPUs. Firstly, a sequential aggregate risk analysis algorithm is implemented in C on a CPU, followed by parallel implementations using C and OpenMP on multi-core CPU and using C and CUDA on many-core GPU platforms. Aggregate risk analysis is a form of Monte Carlo simulation performed on a portfolio of risks that a re-insurer holds rather than on individual risks. This involves a high number of simulations with lookups from real world database. These lookups are highly irregular and hence slow down the entire computation. Also there are huge data structures which need to be handled very carefully. Storing them in dense format is quite slow, and sparse formats which are easy to lookup take too much space in memory. We design a hybrid implementation which uses both CPU resource and GPU resource in computation and hence more efficient. The implementation is based on work sharing. We validate our results by comparing them to GPU-only implementations on two different CPU-GPU combinations. The work partition is computed empirically and experimentally for getting maximum efficiency. This partition is platform dependent making the application less portable. To address this challenge we propose an alternate automated hybrid solution, which works well for all CPU-GPU combinations and hence platform independent. This solution adds more portability to the application. We analyzed this automated solution and found it very close to the non-portable hybrid implementation.

Abstract

Measuring inter-document similarity is one of the most essential steps in text document clustering. Most of the document clustering methods rely on the Bag-of-Words (BOW) model for representing the text documents. The BOW model assumes that the terms of a text document are independent of each other. We attempt to explain and address two of the major drawbacks of such single term analysis of the text. First, it completely ignores the underlying (semantic) structure of a document. In the literature, sufficient efforts have been made to enrich BOW representation using phrases and n-grams like bigrams and tri-grams. These approaches take into account dependencies between adjacent terms or a continuous sequence of terms only. However, while some of the dependencies exist between adjacent words, others are more distant. We make an effort to enrich traditional document vector by adding the notion of term-pair features. A Term-Pair feature is a pair of two terms of the same document such that they may be adjacent to each other or distant. We investigate the process of term-pair selection and propose a methodology to select potential term-pairs from the given document. Utilizing term proximity between distant terms also allows some flexibility for two documents to be similar if they are about similar topics but with varied writing styles. Second major drawback of single term analysis of text is that it treats whole document as a single semantic unit and thus, ignores other semantic units like sentences, passages etc. A document is inherently an organized structure consisting of various text segments or passages. We attempt to take advantage of this underlying subtopic structure of text documents and investigate whether clustering of text documents can be improved if text segments of two documents are utilized while calculating similarity between them. We concentrate on examining effects of combining suggested inter-document similarities (based on inter-passage similarities) with traditional inter-document similarities following a simple approach for the same. Experimental results on standard data sets suggest improvement in clustering of text documents for both of the above mentioned approaches.

Abstract

Topic detection in a text corpus is the detection of semantic units from the underlying texts that can function as building blocks of knowledge discovery. Topic detection provides a powerful tool for text summarization and information navigation across a corpus of documents. Topic detection from text documents using statistical models and natural language processing techniques has been extensively studied by the researchers. In the recent years, it has drawn considerable research interest in the field of data mining too. The problem is also interesting and challenging in the domain of academia, considering the ever growing size of academic literature and the fast changing fields of research, which requires the algorithms to be fast and highly scalable in order to efficiently mine research topics and their features over the time-line. In this thesis, we model the topic detection problem through the paradigm of data mining by proposing a closed frequent keyword-set based approach to form topics from a large corpus of research papers. The topics as detected by our algorithm preserves the semantics present in the documents and we experimentally show that our algorithm is fast and effective than the state of art frequent item-set mining algorithms. Our approach also studies the closely linked problem of document clustering by providing a topic-based clustering technique for the research papers by using the detected topics as similarity measure to form hierarchical, overlapping clusters. Our next contribution is to develop an approach to rank the topics on the basis of their importance. The current set of algorithms mostly focus on the detection of topics, and not much effort has been put to order the topics based on their importance in the research community. For a researcher, it becomes a very cumbersome task to go through the entire list of topics and decide upon which topics are the prominent ones. The bibliographic datasets belong to the hyperlinked set of documents, which are connected to each other through citation links. The citation links contain important information in the form of peer votes in the research community, which interestingly has not been utilized by existing models for topic ranking. The current approaches primarily model the popularity index of the topics by considering the frequency of the documents belonging to the topic for ranking them, rather than their importance factor which is better modeled by the peer votes in the community. In this thesis, we propose a time independent modified PageRank algorithm that assigns an authoritative score to each topic by considering the citation links of the sub-graph of the topics, producing a ranked list of topics. We also address the problem of time bias in the hyperlinked environments incurred in calculating the authoritative scores of the topics. It is observed that the newer papers do not get sufficient time to be cited compared to the older papers and thus fall behind in the ranking even if they are important. The use of citation network and the introduction of time invariance in our topic ranking algorithm reveal interesting patterns.

Abstract

We propose a supervised learning technique for associative regression. Assuming frequent patterns quantify correlations in dataset, we constrain the Iterative Scaling (IS) convergence algorithm for Max- imum Entropy (ME) models. We also assume prior probabilities on the ME model as a control on the step size in convergence iteration. We have used the combinations of ME parameters and IS probabilities as discriminative weights to frequent patterns. The weighted frequent patterns then predict the associative regression rules. To find the regression error of our proposal, experiments are conducted on sparse numeric datasets. Our technique is comparable to the standard regression algorithms. We demonstrate the feature extraction and convergence criterion in experiments. Results suggest that con- densed representations of frequent patterns allow parametric models suitable for class association rule mining. Intutively, our idea of information is derived from an objective function expressing number of bits needed to represent data by frequent patterns. Conceptually, our model represents information regarding functional dependencies in a database as weights derived from a binary/fuzzy relation. The elements of the binary/fuzzy relation are indicator functions of an incidence matrix about conditional /joint probability distributions where dataset is taken to be a inmemory contingency table. Our technique has application in incremental semisupervised learning algorithms requiring discriminatory information from clustering, classification and association rule mining.

Abstract

Focused crawling has wide number of applications in the area of Information Retrieval. It is a crucial part in building genre specific search engines, personalized search tools and extending digital libraries. Be it Google Scholar to search for scholarly articles or Google news to search for news articles, genre specific search is the most widely acclaimed application of focused crawling. Unfortunately, there are very few genre specific search engines available for Indian languages. Sandhan is one such project which offers search in tourism and health genres across 10 major Indian languages. The amount of Indian language content on web is less compared to other languages. When we restrict the search space to a specific genre (say tourism) the probability of finding relevant pages reduces further. Hence crawl coverage plays a major role in such a scenario. Also, due to the tendency of Indian language web pages linking to other language pages (usually English), traditional crawling methods end up crawling a lot of unnecessary content. This means that we need to spend most of our resources in crawling something that is not useful for us! In the first part of this thesis we try to explore ways of gathering Indian language tourism and health pages from the web for Sandhan using a language and genre specific focused crawler. We crawl the web extensively for Indian language tourism and health pages. We use different evaluation metrics to evaluate the quality of our crawl - precision, recall and harvest ratio. Using the focused crawling approach we save 63.57% resources (disk space, bandwidth, processing time) while maintaining a coverage of about 74% and 58% for tourism and health genres respectively. In the second part of this thesis we try to solve the problem of seed selection for genre specific search engines. Diversity of crawl is one of the pivotal aspects of a genre specific search engine. To a large extent, it is governed by the initial set of seed URLs. To ensure a diverse crawl there must be diversity within the seed URLs. For selecting seed URLs, most of the existing approaches rely on manual effort. In this work, we automate this process by “selectively picking” URLs posted on Twitter and using them as seed URLs. We propose a graph based algorithm to get a set of diverse seed URLs from Twitter. Each vertex in the graph is a URL coming from Twitter. Two vertices are connected if there is some similarity between them, which is measured using the information in the corresponding tweets: tweet content, URL N-Grams and retweet. Our algorithm then picks the URLs from the graph in such a way that the resulting set consists of diverse seed URLs. We experiment with the tourism genre and find that our approach is indeed able to capture diversity within our seed set. We also propose several metrics for evaluating the diversity of a web crawl which can be used to compare seed sets and focused crawlers w.r.t diversity.

Abstract

Library science is the predecessor of the present information retrieval (IR) technology. Since decades, libraries were the source of information and knowledge to one and all. A library meant a mammoth structure, home to thousands of books and journals. People from far away lands came to great libraries where they used to learn and later contributed. These people then became the source of information to other people. In present society, we will find a shift in paradigm. Today, thousands of books can be stored on a hand held device or a personal computer like our own personal library. Furthermore, Internet has given the capability of easy accessible knowledge to every person. With age internet services have matured and people are more comfortable to share and contribute content via this medium. This resulted in multiple sources of information pertaining to any single topic. There is no bound on the language of each of these sources. So, now we have many sources in multiple languages. This has led to a whole new set of problems that are needed to be solved by the IR community. The main focus of these problems is management of huge information. They need to figure out what different methods can be used to understand and impart structure to the information. Furthermore, individual needs play an important role to decide the information managing strategies. So, the focus has shifted from getting the information to getting the right information. This work is a step in that direction. We address the problem of Text Summarization and its multilingual solution. Although text summarization is a relatively older problem, the internet age has given a new direction and importance to it. Therefore, the summarization methods are needed to be improvised and novel solutions are needed. In our methodology, we initially focus on changing the heuristic based representation of text to meaningful representation of the text. We have used Hyperspace Analogue to Language (HAL) to represent the text, it is a computational model based upon a cognitive model called Conceptual Spaces. The properties of conceptual spaces allow us to represent words and sentences in the same space, called HAL space. Then, we modeled the problem of summarization as selecting those set of sentences which can represent the source text in the most meaningful manner. To handle the redundancy in summaries we propose a novel mechanism which is effective in the HAL space. Our method is language independent making it scalable over different languages. We provide useful insights into formation of conceptual space using textual examples and behavior of metrics using intrinsic experiments. Intrinsic experiments and extrinsic evaluation were conducted on DUC 2001 and DUC 2002 datasets. The results of extrinsic evaluation show that quality of summaries is preserved over summary size and the system outperforms, previous state-of-the-art systems for longer summaries while being comparable for shorter summaries. Multilingual summarization is a relatively new field in text summarization. We focused on studying two aspects of multilingual summarization first, “Added noisy information” (related to number of languages of the source documents) and second, suitability of monolingual summarizers in a multilingual domain. For our work, we use automatic translation systems along with four generic summarizer systems (including CMDS). These summarizers are used to form monolingual summaries (separately) in different languages. Quality of a summary (for each language) is obtained by the Jensen-Shannon divergence measure between the summary distribution and input distribution. To form multilingual summary, weights proportional to the quality are used to combine the monolingual summaries. This work is done in three languages, namely English, Hindi and Telugu. The experimental results are encouraging and show that as the number of interacting language increase quality of multilingual summaries improve. We also find that compared to structural methods, contextual methods are more suitable for the task of multilingual summarization. Finally, to show that HAL features are effective for different summarization tasks other than generic summarizers, we use them as one of the key features to form summaries of on-line conversation in the domain of debates. The experimental results (ROUGE scores) show that our summaries are better compared to previous state-of-the-art system. One major difference between our approach and previous approach was the use of HAL features to create summaries. This shows that addition of HAL features to sentiment related features is helpful to summarize sentiment rich text. To conclude, we explain the need of meaningful representation of text to improve summary quality. Our work establishes HAL as a quality representation of text and useful for the task of summarization. We also give a summary formation conjecture and t

Abstract

Telugu is a morphologically rich, free word order language(MoR-FWO). Parsing morphologically rich, free word order languages is a challenging task mainly because the syntactic cues necessary to identify various relations are complex and distributed. In this work, we take up the problem of parsing Telugu and try to propose different approaches. The first approach explored was to implement constraint based hybrid parsing technique for Telugu. This was inspired from Constraintbased hybrid parser(CBHP) built for Hindi. Telugu shares some properties like flexible word order, rich morphology etc with other Indian languages(eg Hindi).Since constraint-based hybrid parsing approach have been known to handle such linguistic patterns with ease, using such an approach to parse Telugu seems like an appropriate choice . For the constraint-based hybrid parsing experiments, Telugu data set released for ICON Tools Contest 2010 is used. It is divided into training, development and test data sets. A knowledge base and the treebank training data is used to develop constraints for parser. CBHP for Telugu is applied for development and test data sets. Parser accuracy obtained for development data was 68.06% Labeled Attachment Score (LAS), 84.41% Unlabeled Attachment Score (UAS), 70.34% Labeled Score(LS) and parser accuracy for test data was, 65.33% LAS, 84.14% UAS, 66.60% LS. Detailed analysis is done to check deficit in LAS. CBHP approach used for Telugu has parsing and ranking as two separate phases. An integrated system is more systematic from an architectural point of view. Hence we tried to merge parsing and ranking phases to build an Integrated Constraint based hybrid parser for Telugu. Experiments were done on same datasets as mentioned above. Integrated parser accuracy was 66.20% (LAS), 85.38% (UAS) and 69.36% (LS) for development data and 64.22% (LAS), 84.05% (UAS) and 65.90% (LS) for testing data. We compared our systems with statistical parsing approach. We have done a series of experiments using a transition based data driven parser(Malt parser). We used the same training data as mentioned above to train the parser. We have prepared best settings by running the parser on several configurations with different combinations of algorithms, classifier and features in feature template. We used a simple forward selection algorithm to pick the best feature template. We are able to achieve 70.12% LAS, 91.82% UAS and 71.95% LS on the fine grained ICON tools contest test data.

Abstract

Relief carving is very popular sculpting technique that is being used for decoration and depicting stories and scenes from ancient times till today. With time, many of the ancient cultural heritage artifacts are getting damaged and one of the important methods that aids preservation and study is to capture them digitally. Reliefs carvings have certain specific attributes that makes them different from regular sculptures, which can be exploited in different computer vision tasks. Repetitive patterns are one such frequently occurring phenomenon in reliefs. Algorithms for detection of repeating patterns in images often assume that the repetition is regular and highly similar across the instances. Approximate repetitions are also of interest in many domains such as hand carved sculptures, wall decorations, groups of natural objects, etc. Detection of such repetitive structures can help in applications such as image retrieval, image inpainting and 3D reconstruction. In this work, we look at a specific class of approximate repetitions: those in images of hand carved relief structures. We present a robust hierarchical method for detecting such repetitions. Given a single relief panel image, our algorithm finds dense matches of local features across the image at various scales. The matching features are then grouped based on their geometric configuration to find repeating elements. We also propose a method to group the repeating elements to segment the repetitive patterns in an image. In relief images, foreground and background have nearly the same texture, and matching of a single feature would not provide reliable evidence of repetition. Our grouping algorithm integrates evidences of repetition to reliably find repeating patterns. Input image is processed on a multi-resolution pyramid to effectively detect all possible repetitions at different scales. Our method has been tested on images with large varieties of complex repetitive patterns and the qualitative results show the robustness of our approach. Reconstructing geometric models of relief carvings are also of great importance in preserving heritage artifacts, digitally. In case of reliefs, using laser scanners and structured lighting techniques is not always feasible or are very expensive given the uncontrolled environment. Single image shape from shading is an under-constrained problem that tries to solve for the surface normals given the intensity image. Various constraints are used to make the problem tractable. To avoid the uncontrolled lighting, we use a pair of images with and without the flash and compute an image under a known illumination. This image is used as an input to the shape reconstruction algorithms. We present techniques that try to reconstruct the shape from relief images using the prior information learned from examples. We learn the variations in geometric shape corresponding to image appearances under different lighting conditions using sparse representations. Given a new image, we estimate the most appropriate shape that will result in the given appearance under the specified lighting conditions. We integrate the prior with the normals computed from reflectance equation in a MAP framework. We test our approach on relief images and compare them with the state-of-the-art shape from shading algorithms.