Abstract

Active learning is a rapidly growing field of machine learning which aims at reducing the labeling effort of the oracle (human expert) in acquiring informative training samples in domains where the cost of labeling is high. The major difference between this and traditional passive learners lies in the fact that passive classifiers do not query to seek training examples to learn from. However, this non trivial active learning methodology is distinctly preferred in certain domains and applications. Such applications include where either the amount of unlabelled data is voluminous or the cost of labeling is high. Few examples of such applications include video annotation, speech recognition and information extraction. The main actors in active learning are the oracle, sampling framework being used and assessment metrics. The current literature boasts of many innovative and different settings for active learning but most of these are highly statistical based approaches. In this thesis, we devise new active learning strategies which rely on heuristic and pattern mining strategies heavily. The crux of our work revolves on efficiently embedding such emerging data mining models in active learning. The two algorithms which we propose in this context are the Ensemble based active learner and Associative active learner. We present variants of each of these algorithms which can also be applied for real time application purposes with a manual oracle. In addition, we also propose a novel dynamic rule based sampling framework which is used by our Associative active learner.

Abstract

As VLSI circuits move into the era of deep sub-micron (DSM) technologies and gigahertz frequencies, the system performance is increasingly becoming dominated by the interconnect delay. While several delay models exist in literature, they are, by and large, applicable to technologies at and above 130nm. Thus there is a need to evolve techniques that can estimate the interconnect delay with a reasonable accuracy in DSM technologies such as 90nm. The objectives of this thesis are three fold. (i) To develop a novel model order reduction (MOR) to reduce the complexity of large integrated circuits and therefore simplify the estimation of signal delay in interconnects and (ii) To develop novel analytical and statistical techniques for delay modeling of inductance-dominated (RLC) interconnects. The first contribution of the thesis is the development of a novel MOR technique to reduce the complexity of large integrated circuits. The purpose of any MOR technique is to replace a model by its approximation, which, while simplifying the analysis, also preserves essential properties like stability and passivity of the original model within a certain accuracy. The MOR technique proposed in this thesis satisfies these conditions and an analysis of the technique indicates that it performs better than any of the existing techniques. Once the reduced model of large circuit is derived, then analytical or statistical techniques can be applied to estimate the signal delay in interconnect. The second contribution of the thesis is the development of an Erlang distribution-based statistical technique to estimate the delay in inductance-dominated interconnects. It is shown that this technique performs better than other similar techniques for estimation of delay. The third and final contribution of the thesis is the development of a novel analytical delay model based on difference model approach. The model has been applied to an interconnect tree with various combinations of source and load parameters under step input excitation. It is found that the delay estimates obtained using the proposed analytical model are within 2% of SPICE-computed delays. The techniques proposed in this thesis are expected to be useful for efficient interconnect delay analysis.

Abstract

Pipelines are common transportation means for oil and natural gas, which always act as an important lifeline facility for any nation. Generally, these pipelines laid underground for safety and economical reasons. While running through the length and breadth of country pipeline expose to diverse soil conditions. Presently India operates and maintains about 25,000km of gas and other petroleum product pipelines, which are expected to be the double in coming years. Because of major port Kandla and other international ports with refineries at Koyali near Baroda and Jamnagar, western state of India, Gujarat have many major pipeline network which run towards other part of the country and boost up after dreamed Iran Pakistan India pipeline. On the other hand, same region is one of the most seismically active regions (equally like plate boundary region) of the stable continental part of the Indian tectonic plate that has many active faults. Many major pipelines of this region are in vicinity of such active faults e.g. Mundra-Panipat pipeline is in vicinity of the Kachhach Mainland fault. Majority of the sub-ducting Indian tectonic plant’s faults are of thrust in nature hence the pipelines crossing such fault are subjected to compression. Contradictory to this previous work for pipeline fault crossing is done for tension case mainly. Vulnerability of the pipeline due to seismic hazards can be divided in to three categories i.e. hazard due to ground vibration, hazard due to faulting and hazard due to permanent ground deformation (PGD). Though there are no severe damage were observed due ground vibration in the modern buried pipeline. In view of the fact that Indian pipeline network has been developed in recent years and there is no synthetic data of pipeline damage, which is recorded for earlier earthquakes, these notify performance of Indian pipeline as well. Though there are many events of pipeline failure all over the world during past seismic events. In 1971 San Fernando earthquake, over 80-transmission line failures occurred due to shaking and approximately 10 failures occur due to PGD. In 1989, Loma Prieta earthquake has resulted in a program of extensive cast iron pipe replacement using Polyethylene. In1994, Northridge earthquake has lead to 209 repairs to metallic distribution lines and 27 to polyethylene lines. During 1999, Chi-Chi (Taiwan) earthquake 2000mm diameter pipe destroyed by rupture at Chelungpu fault. During 1999, Izmit, Turkey earthquake pipe buckled which was crossing the Anatolian strike slip fault. There are many more acknowledged instances of pipeline damages during an earthquake which includes 1906 San Francisco to recent 2010 Haiti earthquakes. Predominant study for seismic hazard of pipeline started after the 1971 San Fernando earthquake. Newmarks and Hall did the pioneer work for pipeline crossing the fault by assuming pipe as cable model in analytical study to determine the axial strain in the pipe crossing strike slip fault. Numbers of modification were further suggested by many authors in past like Kennedy, Wang and Yeh and recently by Karamitros. However, these models gives satisfactory results for the pipeline crossing strike slip fault under tension but cannot incorporates the large geometric changes. With continuous advancement in computation power and the numerical method recently many researchers are using numerical method to simulate phenomena, which can easily takes care the nonlinear material behaviour. Recently, Takada (1998), LIU (2004) et al are used spring-shell element model to simulate the pipeline fault crossing. However, these models are fine to pipeline but too harsh to the soil behaviour, nevertheless the behaviour of soil has significant impact on the pipeline response. Many analytical models were developed for transverse PGD were pipeline modelled with the assumption of small deformation. For the case of transverse PGD pipeline mainly subjected to the bending. While in case of longitudinal PGD pipeline, expose to the longitudinal tension and compression strains, which is less studied in past. Pipeline subjecting to the large ground deformation itself is a problem of large geometric changes. Especially in case of the pipeline under compression cause to undergo the geometric failure in addition to material failure. Generally, Newton-Raphson technique of nonlinear numerical analysis diverges at snap back and snaps through point. Analysis can be extended by using advance nonlinear techniques like Arc-length method; the same is implemented here for analysis. In this study, more significance is given to the understanding pipeline performance in terms of geometric changes with material nonlinearity. Hence, to reduce the computation efforts and complexity in the analysis it is assumed that bond between the pipe and soil is perfect, which can be added in future study. In this work, a numerical study is carr

Abstract

Security experts often say, users are the weakest link in a security system. Users misunderstand how to use security mechanisms and do not realize the protection and are happy to circumvent the security measures, if security measures try to impede their primary tasks. Attackers on the other hand are experts in usability: they exploit user’s lack of understanding and their tendencies not to comply with security protocols and policies by developing simple yet effective social engineering attacks. Below we explain two main important problems the users are facing in the social networking sites. The first one is identifying between strangers and friends and the second one is adding the people who are interested in the community. Current social networking sites protect user data by making it available only to the restricted set of people often friends. However, the concept of ‘friend’ in social networks is illusory. Adding a person to the friends list without verifying her identity can lead to many serious consequences like identity theft, privacy loss, etc. We propose a novel verification paradigm to ensure that the person who sends you a friend request is actually your friend and not someone who is faking her identity. Our solution is based on what a person might know and can verify about the other person. We work on a premise that a friend can say about her friend’s preferences better than the stranger. The preferences include the interests of a particular person and the big five personality traits 1 . To verify our premise, we did a two stage user study. Results of the user study are quite encouraging. The lifeline of a social networking site is its community relationship model. A community is a group of people having similar tastes, interests and lifestyle. Communities can take the form of an online forum, discussion group where the active participation of a user is required. As of now there is no provision in the social networking sites to measure the interest of the members of a particular community. Inclusion of uninterested users into the community will negatively impact the quality of the community and its activities. Often it so happens that attackers disguised as normal users try to join all the communities even if they are not interested in them. These users

Abstract

Two classes of networks that have been extensively studied in the dynamical analysis of spatially extended systems are: (i) regular networks, wherein each node interacts with a specified number of neighbouring nodes on geometrical lattices, and (ii) random networks, wherein each pair of nodes has a fixed probability of interacting with each other. Recently much attention is being focused on a class of network models that are neither strictly regular nor completely random, but are somewhere in between and exhibit properties of both. Such networks are called small-world networks. Examples for small-world networks are found to occur widely across biological (e.g., neural connection patterns), social (e.g., friendship network, co-authorship) and technological (e.g., the World Wide Web) domains. It has also been observed that a large number of real complex systems such as protein contact networks, protein-protein interaction networks, metabolic networks, exhibit power-law behaviour in their degree distribution, i.e., a few nodes have a very high degree. Such networks are referred to as scale-free networks. To model real physical and biological systems governed by dynamical processes, on such networks the nodes are defined by dynamical systems and the connection between them may be fixed or changing in response to the local dynamics of the nodes, e.g., neuronal excitations. Such networks are called ‗Dynamical Networks‘. Thus, from the point of view of dynamical systems, we have a coupled system of dynamical equations, and we are interested in controlling or manipulating the resulting global dynamics of the system emerging from the interactions between the local dynamics of the individual elements. We propose to use concepts from Graph theory to analyze the coupling structure and its influence in attaining global control of the resulting dynamics in the event of the system exhibiting complex chaotic or excitable dynamics. In an earlier study by Parekh et al, robust control (both global and local) of spatiotemporal dynamics on coupled map lattice (CML) models by applying a constant external perturbation or “pinning‖ has been shown. The advantage of this control approach is that neither any a priori knowledge of the system dynamics, such as stable or unstable fixed points and periodic orbits nor any modification/tracking of the system parameters/variables explicitly is required to suppress chaos. In this study we use the same control approach and analyse the role of connection topologies in achieving global control of the dynamics on small-world and scale-free networks. The analyses have been carried out for dynamics on the nodes governed by (a) logistic map (a one-dimensional nonlinear map exhibiting a wide variety of dynamical behaviour including chaos), and (b) neuron map (a two-dimensional nonlinear map modelling an excitable system, e.g., neuron). The two dynamical systems have been modelled on four different network topologies, viz., regular, random, small-world and scale-free. Since it is practically infeasible to pin all the nodes of the network, here we exploit the geometrical/topological properties of networks to choose nodes for exerting control. We observe that in the case of small-world networks, wherein the connection topology is predominantly local, with a few long range interactions, regularly-spaced controllers provide better control for low pinning densities ~ 20% compared to hubs and other centrality measures which require pinning ~ 50% nodes at similar pinning strengths. The long-range connections only seem to have the effect of spatial noise on small-world network. However, in case of controlling dynamics on the scale-free network, centrality nodes do provide significant advantage in achieving global control. We observe that high-betweenness and high-closeness nodes at very low pinning densities ~ 10 – 15% suffice in suppressing spatiotemporal chaos.

Abstract

Hindi is a morphologically rich, free word order language. Parsing morphologically rich, free word order languages (MoR-FWO) is a challenging task. In this work we present our experiments which lead to state-of-the-art dependency parser for Hindi. We do a series of experiments exploring the role of different morphological and syntactic features in Hindi dependency parsing using two data-driven parsers, Malt and MST. With just 1500 sentences training data, we are able to build a dependency parser with state-of-the-art accuracy of 74.5% Labeled Attachment Score (LAS) and 90.1% Unlabeled Attachment Score (UAS). We also do a detailed error analysis and suggest possible remedies for these problems. During the course of experiments, we realized that some of the basic linguistic constraints were violated by these data driven parsers. We built a linguistically sound parser without compromising on the accuracy. Consider a simple linguistic constraint that a verb should not have multiple karta karakas (roughly, subjects) as its children in the dependency tree. We propose two approaches to handle this constraint and evaluate them on the state-of-the-art Hindi dependency parser. After building state-of-the-art inter-chunk dependency parser for Hindi, we also present our preliminary work on sentence level parsing of Hindi. We extract 1000 sentences, which are word level annotated, from a new multi-layered and multi-representational Hindi Treebank which is being developed. We do a step by step analysis of the importance of different features like, Part-Of-Speech, morph and chunk information for sentence level parsing of Hindi. We could achieve 75.4% Labeled Attachment Score (LAS) and 85.5% Unlabeled Attachment Score (UAS), which is the state-of-the-art performance for sentence level parsing. We also propose an new error detection tool for Treebank validation. Majority of the available error detection tools don’t work for small treebanks, or for the treebanks which are under development. But our tool handles the data sparsity issues and also helps in validation of the treebanks which are being developed. Based on the nature of errors, the proposed tool uses either rule-based or hybrid or both systems to detect errors. We present our results on Hindi dependency treebank data. With our preliminary experiments, we are able to detect 75%, 62.5% and 76.63% of errors in POS, chunk and dependency annotation respectively.

Abstract

Advances in medical device technology have resulted in a plethora of devices that sense, record, transform and process digital data. Images are a key form of diagnostic data, and many devices have been designed and deployed that capture high-resolution in-vivo images in different parts of the spectrum. Computers have enabled complex forms of reconstruction of cross-sectional/ 3D structure (and temporal data) non-invasively, by combining views from multiple projections. Images thus present valuable diagnostic information that may be used to make well-informed decisions. Computer aided diagnosis is a contemporary exploration to apply computers to process digital data with the aim of assisting medical practitioners in interpreting diagnostic information. This thesis takes up a specific disease: diabetic retinopathy, which has visual characteristics manifesting in different stages. Image analysis and pattern recognition have been used to design systems with the objective of detecting and quantifying the extent. The quantitative information can be used by the practitioner to stage the disease and plan treatment, track drug efficacy, or make decisions on course of treatment or prognosis. The generic task of image understanding is known to be computationally ill-posed. However adding domain constraints and restricting the size of the problem make it possible to attempt solutions that are useful. Two basic tasks in image understanding : detection and segmentation, are used. A system is designed to detect a type of vascular lesion called microaneurysm, which appear in the retinal vasculature at the advent of diabetic retinopathy. As the disease progresses it manifests visually as exudative lesions, which are to be segmented, and a system has been developed for the same. The developed systems are tested with image datasets that are in the public domain, as well as a real dataset (from a local speciality hospital) collected during the course of the research, to compare performance indicators against the prior art and elicit better understanding of the factors and challenges involved in creating a system that is ready for clinical use.

Abstract

In Very Long Instruction Word (VLIW) processors, based on the available instruction-level parallelism in programs, compilers schedule operations onto different functional units. By assuming all the functional units of same kind and having the same latency, the conventional list-scheduling algorithm selects the first available (free) functional unit to schedule an operation. But, in advanced process technologies due to process variation, functional units of same kind may have different latencies. In such situation, conventional scheduling algorithms may not yield good performance. Process variations in components like adders, multipliers, etc., of different Integer Functional Units (IFUs) in VLIW processors may cause these units to operate at different speeds, resulting in non-uniform latency IFUs. Pessimistic/conservative techniques dealing with the non-uniform latency IFUs may incur significant performance and/or leakage energy loss. In this work, We propose three process variation-aware compile-time techniques to handle non-uniform latency IFUs. In the first technique, namely `turn-off', we turn of all the process variation affected high latency IFUs. In the second technique, namely `on-demand turn-on', we use some of the process variation affected high latency IFUs by turning them on whenever there is a requirement. Our experimental results show that with these techniques, the non-uniform latency IFU can be tackled without much performance penalty. The proposed techniques also achieve significant reduction in leakage energy consumption as some of the IFUs are turned of. In variation affected situation, conventional scheduling algorithms may not yield good performance. We propose third technique, namely `mobility-list-scheduling' algorithm to schedule operations on non-uniform latency functional units and compare our algorithm with the conventional list-scheduling algorithm.

Abstract

Search engines have become a popular medium for people to fulfill their information needs. Studies on search engines reported a high misspelling rate of queries: around 10-15% queries are erroneous. The detection and correction of spelling errors has become an integral part of computer applications since the very beginning; even before the search engines exist. Research on spelling correction has begun in early 1960s. The research focused on correcting the errors in word processors, specifically where errors occurred in well formed sentences. Search engine queries are very short in length; they have about two to three words on average. Moreover, considerable amount of search queries contain valid but Out Of Vocabulary(OOV) terms. Due to this nature of search queries, correcting search engine queries is more complex than correcting errors in word processors. Research on spelling correction for search engines queries began in early 2000s. But, most of the techniques heavily relied on query logs with the intuition that, People who can’t spell a term correctly can be helped by the people who spell it correctly. Moreover, most of the techniques explored till date depend on linguistic resources, training data or hand crafted rules. In this thesis, we explore ways of correcting spelling errors without relying on query logs or linguistic resources. We focused on correcting two types of errors: 1.Isolated-word errors and 2.Context dependent word errors. Our approach to the above two types of errors is handled using a document collection of a search engine. Our approach addresses correction of isolated-word errors in two steps. In thefirst step, candidate suggestions are generated using an Information Retrieval approach. We explain the reasons for failure of traditional tf-idf (term frequency inverse document frequency) ranking and propose to use df (document frequency) instead of idf in the ranking. In addition, we demonstrate the importance of word frequency in the collection. In step two, candidate suggestions are re-ranked using a new string similarity measure that uses the length of the longest common substrings occurring at the beginning and at the end of the words. We obtained very impressive results by re-ranking candidate suggestions using the new similarity measure. The accuracy of first suggestion is 92.3%, 90.0% and 83.5% for Dutch, Danish and Bulgarian language datasets respectively. The system developed for isolated-word errors is extended to address context dependent errors. In case of context dependent errors; we consider each term in query to be a isolated-word and retrieve candidate suggestions for each of those query terms. Candidate suggestions retrieved for all query terms are used to construct a directed acyclic graph with each suggestion as a node and an edge between suggestions of two consecutive query terms. The longest path, computed by adding the weights of its constituent edges, in the graph yields the best correction candidate to misspelt query. We explore how query expansion and pseudo relevance feedback techniques help in improving the suggestion accuracy of the system. Our approach to context dependent errors obtained a first suggestion accuracy of 75.6%, 80.5% and 85.5% for Bulgarian, English and Dutch language data sets respectively. In this thesis we show that, search queries can be corrected even without using any query logs. In order to keep track of newly evolving words we rely completely on document collection of search engine. Moreover, we demonstrate that, tf-df ranking works better than tf-idf when dealing with character n-grams. The results prove that pseudo relevance feedback techniques can be of great help while correcting the spelling errors in search queries.

Abstract

The amount of textual and multimedia information on world wide web has been increasing many folds every year. A user seeking information on the web is often overloaded with colossal amount of related documents by search engines and information retrieval systems to satisfy his information need. In this context, it has become increasingly important to develop information access systems that provide focused and precise answers to the user. Text Summarization is a popular information access solution for information overload problem. Internet allows its users to follow any popular and temporal topic on web. A temporal topic has a lot of publishing sources and the user cannot handle with the huge amount of raw information from news aggregators, blogs. In such scenario it is not sensible to wait for the topic to complete to produce a summary, nor does it make sense to produce an overall summary at every time interval. In this thesis we study a variant of text summarization, “Progressive Summarization”, focusing only on relevant and novel information, and produce an informative, non redundant summary of the topic. We provide progressive summaries at regular time intervals that helps in updating the user knowledge about the topic. In this work we focus only on extractive methods of summarization, where only the text units from document collection are used in producing a summary. Sentence is considered as a basic text unit for the summary. Extractive summarizers generally follow a sequential framework, that include Pre-processing of text for sentence boundary identification and extraction, a Feature Extraction stage where several statistical, linguistic and heuristic models are employed to estimate sentence importance, Sentence Ranking stage that estimates sentence importance through weighted linear combination of the features and finally Summary Extraction, during which a subset of ranked sentences are selected into summary. The most important factor in extracting important items for a progressive summary, is the identification of novel information. Progressive summarization requires differentiating between Relevant and Novel Vs Non-Relevant and Novel Vs Relevant and Redundant information. Since the existing features are successful in capturing only the relevance, We devise multiple new features (NF, NW, HKLID) to capture novelty of a sentence along with its relevance. We build alternative methods to incorporate novelty in conventional summarization framework. We devise a new re-ranking measure, Proximity Re-ranking (ProximRank), that computes the rank of a sentence based on the relevant novelty of its surrounding sentences. We model novelty detection in the context of progressive summarization as an information filtering task. Sentences that possibly contain prior information are filtered out from summary by creating a Novelty Pool (NP). These methods are successfully related to different stages of summarization and evaluated against each other to find the best. In this thesis we also discover the importance of prepositions in determining the salience and relevance of a sentence to the topic. Also, we use a machine learning technique (Regression) to estimate sentence importance from its feature vector. Thus we overcome the problem of determining ideal weight combination that takes ample amount of experiments and human judgment when several features are used. The techniques described in this thesis are used in building a progressive summarization system (Siel 09) that outperformed all other 43 participating systems in Text Analysis Conference (TAC 2009) in manual evaluations.