Abstract

Previous works have used word alignments in parallel corpora to transfer information like POS tags, syntactic trees, named entities and word senses from source to target sentences. In this thesis, we worked on the problem of transferring syntactic relations from English to morphologically rich Hindi parallel text. Since the size of the parallel corpus is small and considering the presence of inflectional variations in Hindi pose data sparseness problem. We reduce these complexities to some extent using Local Word Groups (LWGs) and show their effectiveness in simplifying alignments as well as in transferring syntactic dependencies by building an alignment model with LWGs as base units and training a dependency parser on the relations projected using these LWGs. The LWG alignment model using GIZA++ scores decreases the Alignment Error Rate (AER) by 1.16 points when compared to the best GIZA++ model trained on lemmas. We also show that a dependency parser trained on the syntactic relations projected using LWGs obtained statistcal significant improvements over the relations projected using lemmas by a margin of 3.49% in terms of Unlabeled Attachment Score (UAS).

Abstract

The world of academia is growing at a tremendous rate with thousands of research papers being published every year. For a researcher looking for new dimensions of research, it is becoming an increasingly difficult task to identify the relevant yet novel domains of research from amongst the host of varied domains. There is a definite need of a system that could help the researchers in their decision making by interacting with large academic information space. Recommender systems are aimed at performing this very task. They help the researchers to overcome the information overload problem by exposing them to the most interesting results and by offering novelty, surprise and relevance. The ever-changing research fields and the increasing complexity in the relationships within the academia have therefore made such a system an essential tool in a researcher’s quest for expanding his research base. In this thesis, we propose a novel and efficient approach for author and topic recommendation to an author in a bibliographic dataset that exploits the hidden relationships in such datasets as well as addresses the issues of scalability and sparsity. Existing recommender systems largely work by creating a neighborhood of similar users and use their preferences to generate recommendations for the active user. In this thesis, we also rank the items to determine their importance in the dataset and use the ranks of the items of interest for the active user in the recommendation process. Our topic-based author recommendation algorithm aims at suggesting latent yet relevant authors to a researcher based on his research topics. For a pair of authors, their shared research interests as well as the relative diversity between their research interests forms the basis of the similarity measure in our algorithm. The objective of our topic recommendation algorithm is to suggest a set of relevant topics to a researcher based on the research interests of similar authors. The recommendation algorithm considers the importance of a topic as well as the importance of the suggesting authors to assign authoritative scores to the recommended topics. We also exploit the hierarchy of topics and their temporal property to prune the irrelevant topics for the task of recommendation. We test our algorithms on the DBLP dataset. Our experiments produced a ranked set of recommended authors and topics that on examination by field experts and based on our study were found to be relevant and fairly accurate. We study our algorithms on various parameters and validate our experiments by dividing the dataset into training and test portions. We also do a comparative study of our author and topic recommendation algorithms with popular recommendation techniques. We also discuss the system called Research Patterns built to facilitate the accessibility and visualization of the results produced by our algorithms and the possibility of extending our algorithms to other domains. Our algorithms have a host of applications like author and topic recommendation, retrieval of authors for a given topic query and vice-versa, building communities of similar authors, research paper recommendation, etc.

Abstract

The automation of activities in all areas, including business, engineering, science, and government, produces an ever-increasing stream of data. Especially, the amount of multimedia content produced and made available on the Internet, both in professional and personal collections is growing rapidly. Equally increasing are the needs in terms of efficient and effective ways to manage it. And why is that so? Because, people believe that data collected contains valuable information. But, extracting any such information/patterns is however an extremely difficult task. This has led to a great amount of research into content based retrieval and visual recognition. The most recent retrieval systems available extract low-level image features and conceptualize them into clusters. A conventional sequential scan on those image features would approximately take about a few hours to search in a set of hundreds of images. Hence, clustering and indexing forms the very crux of the solution. The state of the art uses the 128-dimensional SIFT as low level descriptors. Indexing even a moderate collection involves several millions of such vectors. The search performance depends on the quality of indexing and there is often a need to interactively tune the process for better accuracy. In this thesis, we propose a visualization-based framework and a tool which adheres to the it to tune the indexing process for images and videos. We use a feature selection approach to improve the clustering of SIFT vectors. Users can visualize the quality of clusters and interactively control the importance of individual or groups of feature dimensions easily. The results of the process can be visualized quickly and the process can be repeated. The user can use a filter or a wrapper model in our tool. We use input sampling, GPU-based processing, and visual tools to analyze correlations to provide interactivity. We present results of tuning the indexing for a few standard datasets. A few tuning iterations resulted in an improvement of over 5% in the final classification performance, which is significant. vi

Abstract

Computer aided diagnosis (CAD) using medical images is a vital outcome of application of computers in medicine. Over the years, several methods of CAD have been proposed and implemented for various pathologies and imaging modalities. In theory, CAD systems should achieve complete automation in detecting and diagnosing diseases, whereas in practice these systems aim at assisting the medical expert, for example a Radiologist, to perform effective diagnosis. CAD can also play a significant role in assisting the medical experts in public health enterprises like disease screening. Disease screening is performed by medical experts at specific community healthcare centers to detect diseases early in order to reduce the ensuing mortality and suffering. The two most prevalent applications of disease screening have been detecting retinopathy (retinal diseases) from color fundus images and breast cancer from digital mammograms. Application of CAD in such disease screening initiatives is known to produce high throughput in terms of reduction in effort, time spent and mistakes committed by the medical experts. Since screening is intended for prevention and early detection of diseases, a large number of patients arriving at the point of care turn out to be normal (no disease symptom). This poses a significant challenge for the medical expert using CAD as a large number of false alarms are detected due to the high sensitivity of disease detection in CAD systems. Therefore a significant time of the expert is spent on rejecting the false alarms during diagnosis. The large number of false alarms occurs essentially due to the difficulty in modeling various disease symptoms and normal background across images of normal and abnormal patients. This problem is further compounded due the disease centric approach of CAD where various manifestation of a disease is detected separately from the images resulting in accumulation of false alarms from each detection method. In order to address the challenges of existing CAD systems in disease screening, we propose to perform automated diagnosis in disease screening problems using a two-stage hierarchical approach. In the first stage, presence or absence of a disease is ascertained in the given image. We will refer to this stage as abnormality detection. Once the abnormality of an image is ascertained, further analysis of the disease symptom is performed for assessment of its severity, in the second stage. The abnormality detection task is treated as a normal learning problem, where only a single class corresponding to characteristics of normal medical cases are learnt. A medical case, not conforming to this normal behavior is termed as abnormal. The normal class is learnt using the global characteristics of normal medical images. The proposed approach is showcased on two disease screening problems, detection/assessment of lesions in color fundus images and classification of mammographic lesion as benign or malignant. Evaluation of our method for detection of lesions from color fundus images is performed on four publicly available image datasets. The detection performance has a sensitivity of 100 percent with specificity between 74 percent and 90 percent. Cases needing immediate referral are detected with a sensitivity of 100 percent and specificity of 97 percent. A 10-fold cross validation for lesion detection was also performed to evaluate the average detection performance. The Area Under the receiver operating characteristic Curve (AUC) ranges from 0.89 to 0.99 for various datasets. Assessment of retinal diseases into moderate and severe cases of retinopathy resulted in accuracy of 81 percent for the moderate case and 100 percent for severe cases. Lesion classification in mammograms was performed by treating benign lesions as belonging to the normal class while separating the malignant lesions by identifying them as abnormal. The sensitivity of detecting malignant lesions at 100 percent was achieved with a specificity of 97 percent. The best AUC for the lesion classification task was recorded as 0.98. The success in automated disease detection from color fundus images and mammograms establish the effectiveness of the proposed methodology.

Abstract

Recent technological advancements have led to the proliferation of uncertain data. Uncertainty is inherently present in many real world domains like images. Such databases are more complex because of the additional challenges of representing the probabilistic information. While analyzing such data, it should be handled cautiously. Traditional data-oriented techniques for analyses on uncertain data do not achieve best possible accuracy. There is a growing demand to develop efficient novel methods to handle such kind of data. Existing works on uncertain data mining are largely theoretical, where application areas are suggested but not experimented and are hypothetical. Whereas in this thesis, we present techniques and apply them in a full-fledged real-world application namely image classification and clustering. We utilize the concept of representing images in the form of a normalized model using interest points in images. This model is an uncertain-data-based adaptation of Bag of words (BoW), with each image not only represented by the visual words that it contains, but are also associated with a respective probability of occurrence in the clustered features of the image. We propose two novel algorithms for classification and clustering images which utilizes the normalized bag of words model for image representation. The uncertain associative classifier for object class identification in images (UACI) uses an Associative Classification approach to leverage latent frequent patterns in images for the identification of object classes. Unlike most image classifiers, which rely on positive and negative class sets (generally very vague) for training, UACI uses only positive class images for training. Negative class set is the set of all positive as well as negative class set. So, it is very vague and the choice of negative class set would affect the classifier. We empirically compare UACI with three other image classifiers. In our experimental evaluation, associative classification doesn’t compare well with more recent SVM based techniques like SVM-BoW-Baseline for uncertain image dataset but performed better than the BoW. Also, we propose a clustering algorithm to meaningfully group images into different categories. It uses an uncertain frequent itemset mining approach to extract the latent patterns in the form of frequent itemsets. These patterns eliminate much of the noise and represent the dominant trends which lead to a high degree of accuracy. To analyze the efficiency of this approach, we ran a set of experiments on two different datasets. This algorithm has good efficiency in generating quality clusters.

Abstract

With the daily expansion of computer network and internet applications, the risk of network related crimes are also increasing [1]. Most of the present day intrusion protection systems, security applications and antivirus software aim at detecting, and a few preventing, the damage done to end systems, at the premises where they are installed. In today’s world of rapidly paced networks, we need efficient techniques to identify the source of attacks so as to completely eliminate the malicious systems and the attacks caused by them which can benefit the entire network. Network Forensics includes the field of study which deals with techniques that aims at identifying the source of the attack. The most important part in the field of cybercrime investigation is the need to capture and store data for determining potential legal evidence and at the same time safeguard the privacy of the data plying through the network. Packet attribution systems have been used to perform trace back of the packet in the internet to its source. At the packet header level, determining the source machine from the source IP address is not an effective solution, as IP address can be altered. In order to perform trace back based on packet payload, payload attribution has to be performed at every network device through which packet traverses. This concept of payload attribution was introduced by Shan- mugasundaram et al. [2, 3]. From now throughout the remaining paper let us refer the content of packets to be queried for trace back as “excerpt”. During trace back, the excerpt has to be matched with the stored packet payload at every network device and determine the path taken by the packets. But storing the entire payload at every network device is not a practical solution due to storage and privacy concerns. Various efficient techniques based on bloom filter and its variations have been proposed until now [4]. Source Path Isolation Engine (SPIE) [5] is a payload attribution system which uses space efficient bloom filters for hashing and storing packet payload. SPIE performs repeated hashing of packets, including the invariant portion of the packet header and a part of packet payload and inserts them in Bloom Filters. These compact filters are then stored at the routers. When all routers implement SPIE, it is possible to trace back the packet to the source. The problem with SPIE is to store the packet with its non-mutable headers and a part of the payload and reconstruct the packets during trace back querying [2]. This issue is overcome by the concept of Block Bloom Filters (BBF), where the packet payload is split into blocks of certain size and hashes performed on these blocks are stored in the bloom filters. This technique has to consider all possible offset values and hence the false positive probability (FPP) increases [2]. The value of FPP can be reduced by performing attribution of hierarchies of blocks, a concept named as Hierarchical Bloom Filters (HBF) [2]. But the practical implementation of these concepts on all the routers installed in different networks and network levels increases burden on these routers in terms of processing and storage size. In this thesis, we propose a flexible environment for the implementation of these concepts and increase its practicality in the present day network devices. We put forward our analysis on certain parameters over which system administrators can analyze and take final decision on implementing these techniques on the network devices. To trace back the packet from the destination to the source, all routers in the path of the network have to implement these payload attribution mechanisms. Imposing the same implementation rules and constraints on all these routers is not practical owing to their difference in their capacity of processing and storage capabilities. Depending on the capabilities of the network device, parameters like block size, false positive probability can be adjusted to suite the situation. We have prototyped these con- cepts as software and provided experimental results for processing and storage requirements, by varying these parameters. In the later section of the thesis, we have proposed the use of attribution techniques with only the control packets that ply on the network. This information can be used to trace back vital network control information among routers like network access, session control, trafficking, etc. Our experimental results show that this approach is extremely efficient in terms of storage size and processing speeds. We then discuss our analysis on possible heterogeneous approaches which combine the idea of attributing control packets and data packets individually at every router with variable parameters to configure the bloom filter used for forensic analysis.

Abstract

The word Spoong has been defined differently by different people but the one that is used in this context is as follows: “Spoofing is a scenario in which a person or a program successfully impersonates another identity by falsifying the data and thereby gaining illegitimate advantage.” As the definition goes, spoofing is generally used by the malicious users to trick the victims into making inappropriate actions. These actions may or may not be profitable for the attackers but will surely affect the victims. The spoofing attacks are possible when the attackers are able to exploit the trust relationship between the entities. Hence, spoofing attacks are easy to implement in the scenarios where the authentication procedure between the communicating entities is weak. Though spoofing is not an attack by itself, it is an important step in many of the other dangerous attacks. Due to its effectiveness and ease of implementation, the usage of spoofing has been increasing. In the context of online world, many forms of spoofing have been observed. For an effective utilization of the available resources and in a secure fashion, the spoofing attacks need to be checked in the network. The present day Internet can be viewed as a huge network in which the users request services from the servers and servers provide them. Hence, the users and the servers are considered as the important actors of the Internet. Studies show that both these actors are susceptible to spoofing attacks. So, in this thesis we aim to focus on the following two most important spoofing techniques which are affecting these actors of the Internet: • IP Spoofing, which plays a major role in Denial of Service (DoS) attacks to bring down the servers and • Profile Spoofing in social networks, which enables privacy evasion of the social networking users. In order to mitigate IP spoofing attacks on the server, we have proposed a Hop-Count (HC) based Defensive Mechanism against IP Spoofing (DMIPS) scheme which can filter the spoofed packets effectively and also improves the overall network performance. The Quality of Service (QoS) also has been improved by reducing the number of false positives. At the user side, we focus on the online social networks where numerous attempts are being made by various people to extract private information from the users. This is done by deceiving the users by profile spoofing and then getting more information than they are allowed to get. To mitigate this attack, we have designed a challenge-response based scheme which assists the users in identifying their friends and differentiating them correctly which enables easy and efficient privacy management.

Abstract

Recent studies in classification have proposed ways of exploiting the association rule mining paradigm. These studies have performed extensive experiments to show their techniques to be both efficient and accurate. In this thesis, we propose Perturbed Frequent Itemset based Classification Techniques (PERFICT), a novel associative classification approach based on perturbed frequent itemsets. Most of the existing associative classifiers work well on transactional data where each record contains a set of boolean items. They are not very effective in general for relational data that typically contains real valued attributes. In PERFICT, we handle real valued attributes by treating items as (attribute,value) pairs, where the value is not the original one, but is perturbed by a small amount and is a range based value. We propose a pre-processing step based on perturbation as an alternative to the standard discretization step to convert real valued attributes into ranges. The PERFICT approaches are built on the Apriori frame-work for frequent itemsets generation. We also propose our own similarity measure which captures the nature of real valued attributes and provide effective weights to the frequent itemsets. This MJ similarity measure inherently prunes away the unnecessary frequent itemsets. The probabilistic contributions of different frequent itemsets is taken into considerations during classification. Some of the applications where such a technique is useful are in signal classification, medical diagnosis and handwriting recognition. Experiments conducted on the UCI Repository datasets show that variants of PERFICT are highly competitive in terms of accuracy in comparison with popular associative classification methods, decision trees and rule based classifiers. We developed PERICASA, PERturbed frequent Itemset based classification for Computational Auditory Scene Analysis(CASA), as an application to HistSimilar PERFICT. It provides a novel architecture for perception of sound waveforms. The purpose of this model is to develop a classifier which can correctly identify audio waveforms from noisy sound mixtures i.e. to solve the classical ‘Cocktail Party Problem’. The architecture is based on Gestalt principles of grouping like Pragnanz, Proximity, Common Fate and Similarity. The primary idea is that more the ease with which we can identify different associated feature values, easier it is to identify the sound waveform.

Abstract

General purpose computing on graphics processor units (GPGPU) has attained widespread acceptance in the high-performance computing community. This has largely been at- tributed to the rise of programming models and large peak performance to cost ratio of the GPU. The peak throughput of modern GPUs are typically 5 TFLOPS at a cost of 600 US $. These upper limits are found only for applications that have a regular and low frequency memory access. Many algorithms which have a computational model orthogo- nal to the GPU model, especially in the domain of graph theory, have been traditionally not known to be well suited for the GPU model. Graph theoretical algorithms are considered as one of the fundamental building blocks for Computer Science in general. They are considered impractical on many of the current high performance platforms because of the large dependence on irregular data movement, which in the GPU context is a major performance bottleneck. In this context, we focus on fundamental primitives with applications for graph theory, with a large number of immediate applications Typical primitives related to graph theory, can be divided into  Graph primitives: Graph primitives include traversal, connectivity algorithms, path based algorithms etc.. In this thesis, we have dealt with connectivity algorithms such as connected components, spanning tree and spanning forest.  Generic Primitives: Graph theory applications rely not just on domain specic primitives, but primitives from other domains play a signicant role especially in large graph operations on parallel machines. One such primitive is the Range Query Primitive (esp Minima and Maxima). We present a GPU specic implementation of range queries and use it to answer queries such as LCA, minimum/maximum element in a subtree etc.. All the primitives rely on an array based representation, and focus on reducing the dependence on the hierarchical structure of the graph. Problems such as minimum key in a subtree are converted into equivalent problems (Range Query) that have a solution more suited to the GPU model. Also, solutions presented here try to reduce data movement by exploiting data level as well as functional data movement redundancies. Thus the focus is on handling data movement judiciously. We show that the results we have obtained on data sizes tting the GPU are faster than results on any hardware currently present in literature.

Abstract

The exponential growth of the World-Wide Web has transformed it into an ecology of knowledge in which highly diverse information is linked in an extremely complex and arbitrary manner. At the same time, huge multilingual content is being added to it through various sources like blogs, news articles and several other forms. To facilitate the access of this enormous multilingual content, Cross Lingual Information Access systems (CLIA) are vital. CLIA systems take users’ information need and returns the required information to them. The information can be obtained from various sources and different languages, reducing the effort of user to search in different information sources. Query translation is the most important task in building an effective CLIA system as the accuracy of the results are dependent on the accuracy of the query translation. The user input, usually few words, is considered as the query. Given the differences in vocabulary across the languages, we have to capture the context of the query to increase the efficiency of the query translation. Query translation forms the vital component of any CLIA system as it captures the users need and translating queries effectively is required. We devised a language independent approach that captures the users intent from his query by mapping query words to Wikipedia topics. Wikipedia, the free on-line encyclopedia, is a hypertext document collection with a rich link structure. Unlike ordinary encyclopedias,Wikipedia is based on the wiki concept, which enables community to create or improve articles. Wikipedia articles cover many domain-specific and general topics, making it a rich knowledge resource. Due to its unique concept, Wikipedia is populated with articles in around 240 languages, making it a rich multi-lingual resource. We intend to leverage this multi lingual knowledge base as a resource to aid multi lingual query translation. In this work, we propose a query translation method that uses the rich link structure across the languages present in Wikipedia. The query translation approach we have adopted is language independent and focuses on minimizing the use of language specific resources, making our approach scalable. This approach is specifically useful for under-resourced languages (Indian, African etc) as these languages do not have sufficient resources and tools with good accuracies. For these under-resourced languages, a query translation approach is proposed using the resources mined from Wikipedia substituting the language-specific resources for query translation. Using the cross lingual links and the articles that are connected with these links, we build dictionaries that forms the resource for query translation. A language independent approach to identify parallel text is also proposed. A parallel text is a text placed alongside its translation or translations. Parallel text forms the major resource for many areas of linguistic research and their availability helps to identify many retrieval problems between the pair of languages. The query translation approach we have adopted takes the context of the query into consideration to perform the translation. We use Wikipedia concepts to mine the context of the user query and use them to form the translation. An evaluation method to evaluate query translation is also proposed using Wikipedia, by mining statistics from the articles and the cross lingual links. A separate evaluation method is required in-line with our intent to develop the system without using any language resources due to their non-availability. The coverage of the dictionaries is 78.1% while the accuracy of the query translation is 69.75%. In this work, we develop a language-independent approach to query translation that also considers the context of the query. Since no language resources were used, our approach is scalable and can be applied to any pair of languages present in Wikipedia. The performance of the system is encouraging and condone our intention of substituting Wikipedia for language resources. Further the resources mined and approaches proposed can be leveraged in various areas of linguistic research. Parallel sentence extraction approach can be used to solve the problem of cross lingual plagiarism detection. Extraction of context from a sentence can be extended to support Update Summarization task. Thus, in this work, we suggest a language independent query translation approach which can be a right direction towards building a CLIA system for less resourced languages.