Abstract

In the recent past, the Web has not only become the predominant source of information, but also a crucial player in the evolution of events. People reporting information about real time events has made it a significant indicator to detect and estimate the pulse of various communities. Currently the most amount of real-time information about events is generated by social networks like Blogs, Twitter and Facebook. In view of this, it is very important to have a system that can condense the data and can extract meaningful information without human intervention. A new area of research in information retrieval (IR) has developed over the past few years called Topic Detection and Tracking (TDT). Topic detection involves detecting the occurrence of a new event such as earthquake, election results, a new movie released, or a political scam in a stream of news stories from multiple sources. Topic tracking is the process of monitoring a stream of news stories to find those that report or discuss the same event as one specified by a user. Previous approaches for Topic detection mainly focused on sources like news streams, web pages, documents, reviews and other structured and semi-structured information sources. In this thesis, we focus on detecting the underlying semantic aspects (Sub-topics) of an event and extract structured information from the sub-topics found. Topics or events on Twitter relate to major events in the real world; sub-topics on the other hand are fine-grained aspects of such events. The velocity, volume and variety with which Twitter generates text is increasing exponentially. Mining sub-topics from entities helps in trend analysis, social monitoring, topic tracking and reputation mining. In the recent past, Twitter has been widely used for spreading the social pulse about real world entities. Fresh latent sub-topics identified from Twitter feeds at any given point of time could be extremely useful in providing better topic-wise search results relevant to users’ informational needs. Also, extraction of Structured information from tweets related to a sub-topic could provide a nice summary for the subtopic. The two main challenges in mining sub-topics from tweets in real-time are (1) understanding the semantic and the conceptual representation of the tweets, and (2) the ability to determine when a new sub-topic (or cluster) appears in the tweet stream. We address these challenges by proposing two unsupervised clustering approaches. In the first approach (SSR), for each tweet, we generate a semantic space representation by keyword expansion and keyphrase identication. In the second approach (CSR), we transform each tweet into a conceptual space that represents the latent concepts of the tweet. For our evaluation, we use RepLab (CLEF) 2013 dataset. The dataset contains tweets for 61 entities. Each entity has about 700 tweets for training and 1500 tweets for testing. The SSR approach gave an F1 measure of 0.259 and CSR an F1 measure of 0.339. We show a significant increase in the F1 measure value by 16.9% as compared to the Baseline and 1% as compared to the best system in RepLab 2013, which indicates that the proposed CSR approach performs better than the state-of-the-art methods. In extension to the previous approaches, we propose a more sophisticated approach which also considers semantic similarity between concepts and a statistical way to determine a threshold for creating a new sub-topic. We initially try to detect Sub-topics from targetted entities and later try to extract structured information from them. We generate a rich semantic representation of tweets using external knowledge bases, and combine it with relevant similarity metrics to train a sub-topic detection classifier. Further, we train a Conditional Random Field (CRF) model to identify subject-predicate-object fact triplets from tweets. Comparisons with various state-of-the-art mechanisms for sub-topic detection on a dataset of 134K tweets show that the proposed approach outperforms others by a significant margin providing a best F1 score of 0.417. The proposed CRF-based fact triplets extraction approach also beats the baselines significantly providing an overall F1 of 0.43. We also try to map the extracted information to manually generated event schemas. For this task we specifically focus on the natural disaster events on twitter. As soon as natural disaster events happen, users are eager to know more about them. However, search engines currently provide a ten blue links interface for queries related to such events. Relevance of results for such queries can be significantly improved if users are shown a structured summary of the fresh events related to such queries. This would not just reduce the number of user clicks to get the relevant information but would also help users get updated with more fine grained attribute-level information. Twitter is a great source that can be exploited for obtaining su

Abstract

The huge growth in digital libraries, WWW (world wide web) and other text resources has created the demand of techniques which can work intelligently on limited linguistic resources and fulfills the growing demand of text analysis, pattern discovery and information management related operations. The graph based automated text analysis and text mining methods have received a great deal of attention in solving these issues. Actually, an important aspect of graph-based method is that it does not require deep linguistic knowledge, nor domain or language specific annotated corpora, which makes it highly portable to other domains, genres, or languages. The development of advanced graph theoretical techniques for social media mining has also enriched this area. However, the development of effective core techniques to mine the information, from text document(s) by using limited linguistic resources is a challenging task of significant interest. Still The huge growth in digital libraries, WWW (world wide web) and other text resources has created the demand of techniques which can work intelligently on limited linguistic resources and fulfills the growing demand of text analysis, pattern discovery and information management related operations. The graph based automated text analysis and text mining methods have received a great deal of attention in solving these issues. Actually, an important aspect of graph-based method is that it does not require deep linguistic knowledge, nor domain or language specific annotated corpora, which makes it highly portable to other domains, genres, or languages. The development of advanced graph theoretical techniques for social media mining has also enriched this area. However, the development of effective core techniques to mine the information, from text document(s) by using limited linguistic resources is a challenging task of significant interest. Still sincere attentions for improvements in a lot of explored core areas are required. Additionally, the exploring of unexplored/less explored areas can be very useful and key ingredient of several text mining applications. Based on the above discussed facts, we have identified some core issues (and techniques for them) like: (i) meaningful phrase identification (ii) differentiating role and sense of words, preferably via a single measure, (iii) handling information gap at the phrase level by using unsupervised scheme, (iv) integrating the importance of words as a core feature and (v) identifying group semantics and/or logically related features, (vi) sentence abstraction and so on. These techniques are very useful for multiple text mining applications like: (a) Document summarization, (b) Summarization Evaluation, (c) Document Clustering, (d) Key phrase Extraction and (e) Automatic Question Answering. The effective improvement in the results of our devised applications, over state-of-the-arts supervised, unsupervised applications, which use linguistic support and domain knowledge etc., prove the effectiveness of the proposed techniques. Our contributions related to the development in the core techniques for domain independent traditional text mining include: (i) Phrase Identification: Identifying useful phrases are still an open and challenging task, as, available linguistic and statistical state-of the art techniques, still suffer a lot of problems. The performance of several text mining tasks depends upon the quality of the identified phrases. We introduce the centrality measures based technique for phrase identification having accuracy more than 90%. We effectively apply this technique to key-phrase extraction (which is itself treated as core task for several applications like: document categorization, indexing, skimming etc.) and document clustering. (ii) Differentiating between role and sense of words: Often times words having same sense may have different roles in document(s). Neglecting such information may misguide us, especially when we compare two different texts having matching words, like: summarization evaluation, and evaluation of descriptive answers and essays, etc. We introduce the use of graph based mapping of co-occurring words and closeness centrality score for this. (iii) Reducing information gap between documents: We introduce the Wikipedia anchor text community detection based scheme, to reduce the information gap between N-grams that are conceptually-related, despite not having a match owing to differences in writing scheme or strategies. We successfully applied this scheme in document clustering. (iv)Integrating the importance of words as a core feature: Most of the traditional text mining techniques treat word/phrases as point/ “raw data” and thus ignore their importance. We believe that treating every word or phrase as a separate data point by language independent text mining techniques may be inappropriate and even known data mining techniques may not be applicable straightaway. This is becau

Abstract

One of the main challenges that prevent the large-scale deployment of Wireless Sensor Networks (WSNs) is providing the applications with the required quality of service (QoS) given the sensor nodes limited energy supplies. WSNs are an important tool in supporting applications ranging from environmental and industrial monitoring, to battlefield surveillance and traffic control, among others. Most of these applications require sensors to have a longer lifetime without human intervention and battery replacement. Therefore energy conservation is one of the main goals for implementing WSNs. To maximize the network lifetime, approaches such as duty cycling and low power listening modes have been proposed. In this thesis, I explore the possibility of further energy savings through the applying the mobility patterns in the network. In this thesis as part of my research, I propose a new mobility patterns in the network, which increase the lifetime of the network as well as reduces the random flooding of the messages in the network, thus improving the bandwidth of the entire network. Hence to validate my proposal, I conclude my thesis with the results obtained through the simulations. The simulation is carried on open source network simulator called “Network Simulator 2 (NS2)”. NS2 is popular simulator for wired, wireless network based on IEEE 802.11 and also for Wireless Sensor Network based on IEEE 802.15.4. The results obtained from the simulations closely mirror the results obtained theoretically.

Abstract

Kabaddi is a popular and an intense game played in Indian sub-continent. The key feature of the game is simultaneous embodiment of cooperation and competition among the players. In particular, the player has to implicitly or explicitly cooperate and coordinate with in a team, while competing with opponent team. The game is played on the principle - capture the raider, while not getting caught by the raider. This principle of capture sounds similar to pursuit domain, a domain used in study of multi-agent systems. There were many strategies that were proposed for pursuit domain but none of them are suitable for Kabaddi due to the game rules and constraints on field space and time. The rules and regulations of the game makes it more interesting and challenging to develop strategies for a game. The major challenges involved in the game of Kabaddi are cooperation between players, decision making by a team (which strategy to use and when), competing against the opponent team. Thus Kabaddi can provide an environment and a framework for Multi-Robot Systems and MAS researchers to evaluate strategies involving both cooperation and competition. In this thesis, we present a Kabaddi game simulator which assists the user to program strategies and evaluate them on simulated games. The Kabaddi simulator package (KSP) is built in Java and can be imported as a Java library. All the game rules of Kabaddi are incorporated into the simulator. By observing many international games, we analyzed strategies deployed by a team in various scenarios and came up with a generic solution for the game. Formations play a key role in the anti-raiders game. We introduce the concept of risk that assists the anti-raiders to get into a formation through implicit cooperation. We also use the risk factor to avoid collision among agents. Three strategies straight line formation, semi-circular formation, circular formation are developed, tested and evaluated against pursuit domain strategy. Though the intermediate goal of anti-raiders is to capture the raider they also should compete in a game. That is, the team might need to change their strategy depending upon the state of a game and must seek to increase their score. To develop a strategy that is competitive we use MDP (Markov Decision Process) which considers multiple strategies as actions and deploys them based on the state of a game. This thesis also discusses on building robots that can play Kabaddi and a few simulations of Kabaddi strategies on a robot simulator.

Abstract

The search and retrieval of relevant images and videos from large repositories of multimedia, is acknowledged as one of the hard challenges of computer science. With existing pattern recognition solutions, one cannot obtain detailed, semantic description for a given multimedia document. Several limitations exist in feature extraction, classification schemes, along with the incompatibility of representations across domains. The situation will most likely remain so, for several years to come. Towards addressing this challenge, we observe that several multimedia collections contain similar parallel information that are: i) semantic in nature, ii) weakly aligned with the multimedia and iii) available freely. For example, the content of a news broadcast is also available in the form of newspaper articles. If a correspondence could be obtained between the videos and such parallel information, one could access one medium using the other, which opens up immense possibilities for information extraction and retrieval. However, it is challenging to find the mapping between the two sources of data due to the unknown semantic hierarchy within each medium and the difficulty to match information across the different modalities. In this thesis, we propose novel algorithms that address these challenges. Different < Multimedia, Parallel Information > pairs, require different alignment techniques, depending on the granularity at which entities could be matched across them. We choose four pairs of multimedia, along with parallel information obtained in the text domain, such that the data is both challenging and available on a large scale. Specifically, our multimedia consists of movies, broadcast sports videos and document images, with the parallel text coming from scripts, commentaries and language resources. As we proceed from one pair to the next, we discover an increasing complexity of the problem, due to a relaxation of the temporal binding between the parallel information and the multimedia. By addressing this challenge, we build solutions that perform increasingly fine-grained alignment between multimedia and text data. The framework that we propose begins with an assumption that we could segment the multimedia and the text into meaningful entities that could correspond to each other. The problem then, is to identify features and learn to match a text-entity to a multimedia-segment (and vice versa). Such a matching scheme could be refined using additional constraints, such as temporal ordering and occurrence statistics. We build algorithms that could align across i) movies and scripts, where sentences from the script are aligned to their respective video-shots and ii) document images with lexicon, where the words of the dictionary are mapped to clusters of word-images extracted from the scanned books. Further, we relax the constraint in the above assumption, such that the segmentation of the multimedia is not available apriori. The problem now, is to perform a joint inference of segmentation and annotation. We address this problem by building an over-complete representation of the multimedia. A large number of putative segmentations are matched against the information extracted from the parallel text, with the joint inference achieved through dynamic programming. This approach was successfully demonstrated on i) Cricket videos, which were segmented and annotated with information from online commentaries and ii) word-images, where sub-words called Character N-Grams, are accurately segmented and labelled using the text-equivalent of the word. As a consequence of the approaches proposed in this thesis, we were able to demonstrate text-based retrieval systems over large multimedia collections. The semantic level at which we can retrieve information was made possible by the annotation with parallel text information. Our work also results in a large set of labeled multimedia, which could be used by sophisticated machine learning algorithms for learning new concepts.