Abstract

Consider a scenario wherein a bank with a large database of customer information intends to identify the set of customers to whom a credit line could be extended. For this, the bank might need various other information, apart from its own database, such as tax information from the income tax department, criminal history of the customers from the law enforcement authorities etc. Although all the other parties might be willing to share their respective information (databases) in order for the banking organization to compute the result, they might not be willing to compromise on the privacy of their databases. To preserve the privacy of the individual data, in an idealistic world, all parties could send their data to a Trusted Third Party (TTP) which would then apply any of the data mining techniques to compute the intended result and share it with the banking organization. The bank would only get to know the final set of customers to whom a line of credit could be extended and any local information with other parties would not be revealed other than what could be computed from the final result itself. However, in the real world, in many instances it would be infeasible to find such a Trusted third party with whom all the other sources of data would be willing to share their information. To overcome such problems, Privacy Preserving Data Mining techniques have been developed which allow the computation of a function on various databases distributed across a set of players, with out either party learning anything about the data of the other parties other than that can be derived from the final result itself. In other words, these techniques simulate the functionality of a TTP. In this thesis, we consider the problem of Privacy Preserving outlier Detection(PPOD) over vertically partitioned data. The computational and communication complexities of the proposed PPOD algorithm are sub-quadratic in the size of the dataset as opposed to the quadratic complexities of the previously known results. In order to achieve efficient algorithms in the private setting, we first develop an approximation algorithm for outlier detection in the centralized setting and then extend it to the case of privacy preserving outlier detection.

Abstract

Identification of static and/or dynamic roles of different non-canonical base pairs is essential for a comprehensive understanding of the sequence-structure-function space of RNA. In the past combined structural bioinformatic and quantum mechanical (QM) approach provided insights into occurrence context and conservation and covariation pattern of non-canonical A:G W:W Cis base pair in RNAs. In this work we have investigated structural and functional occurrence context of reverse Watson-Crick purine-purine base pairs (A:A, G:G and A:G W:W Trans) which constitute an interesting class of non-canonical base pairs in RNA due to their characteristic C10-C10 distance (highest among all base pairing geometries) and parallel local strand orientation. In contrast to canonical base pairs, intrinsic interaction energies and frequencies of occurrence in a nonredundant set of RNA crystal structures of these base pairs do not correlate with each other. Therefore, it is expected that, occurrence of these base pairs will be associated with specific structural folds or functional roles. We have identified the occurrences of these base pairs in a non-redundant set of RNA crystal structures and performed structural alignments of the corresponding homologous sites followed by a detailed context analysis. Our studies reveal that occurrences of purine-purine W:W Trans pairs exhibit a bimodal distribution with respect to the corresponding local backbone geometry. One mode is populated by both A:A and G:G W:W Trans pairs and characterized by a special fold in backbone. We call it a ‘Sharp-turn’ motif. We have observed ‘Sharp-turn’ to be of significant biological importance as it acts as binding site for proteins, metabolites and ions in RNAs. It remains conserved across species with some variation in its composition and often mediates structural folds crucial for the function as in the case of HIV-1 dimerization initiation site. The other mode in distribution is explicitly associated to A:A W:W Trans pairs involved in mediating higher order interactions. A:A W:W Trans mediates in these higher order interactions by participating in specific kinds of triple/quartet formation. We also have analyzed structural context of previously undetected A:G W:W Trans base pair. It has been found to be involved in maintaining translational fidelity at A site in the ribosome via type II A-minor and G-minor interactions with codon:anticodon bases. We rationalize our observations on the basis of quantum chemical calculations performed at M05-2X/6-3++(2d,2p) level of theory. The general trends obtained from analyzing X-ray crystal structures are also consistent with trends observed in available solution NMR structures.

Abstract

n the past recent years, there has been a growing need to understand the semantics in sports games. Use of technology in analyzing player movements and understanding the action on a sports field has been growing in the past few years. Most of the systems today make use of certain tracking devices worn by players or markers with sensors placed around the play area. These trackers or markers are electronic devices that communicate with the cameras or cameramen. Other technologies such as the goal line technology popularly used in soccer helps game referees to make accurate decisions that are often misjudged by mere human perception. The primary challenges in these techniques is to make it cost effective and ease of installation and use. It is not convenient to setup markers and sensors around the playing field or to force players to wear certain recording or communication devices without affecting their natural style of playing. Placing a sensor in the game ball also poses a tricky problem of not altering the physical properties of the ball. Sports recorders and broadcasters are now looking for simple and yet effective solutions to get semantic information from a sports game. The big question here is - Can we get sufficient important data only from a video capture just as a human would without relying on external aids of markers and sensors? With advances in various computer vision algorithms and techniques the goal for the future is to analyze everything from captured video. This kind of solution is obviously more attractive to broadcasting and game recording companies as they dont need to setup extra equipment, or influence the authorities to change the match ball or players outfits. We propose a set of algorithms that does the task of automatic analysis for broadcast videos for the sports of Cricket and Soccer.. Using our approach we can automatically detect salient events in Soccer, Temporally align Cricket video with corresponding text commentaries, Localize/Register a soccer image and others. We also compare our algorithms with other state of the art approaches extensively on different datasets for a variety of tasks.

Abstract

With the scaling of CMOS feature size into sub-100 nm technology nodes, data rates in the order of giga hertz per second are possible. Input / Output (I/O) interfaces and communication media are the mains bottlenecks to achieve high data rates of the communication systems. The main limitation of the communication media is its limited bandwidth, due to which a high frequency signal passing through it experiences intersymbol interference (ISI) thereby distorting the transmitted data. The limitations imposed by the communication media are overcome by the use of additional circuitry and better communication schemes in the interface devices. Additional circuitry such as equalizers are used in the transceivers to nullify the ISI and distortions due to the communication media. Also, better signaling schemes are also employed in the interfaces to reduce the effects of communication media on the data transmitted through it. Therefore, these techniques allow us to achieve high data rates with the existing communication media. In this work, circuits to nullify the ISI and distortions of the communication media (low loss and high loss) and the use a different signaling scheme to increase the throughput through communication media are discussed. Initially, an analog front-end transceiver for enhanced data rate MIL-STD-1553B, called E-MIL-STD-1553 suitable for avionics and military applications is proposed. This work proposes an analog front-end transceiver supporting 100-Mbps data rate in a multi-drop bus environment, over a cable length of 100 meters for a target bit error rate (BER) of 10 −12 , while retaining all other specifications of MIL-STD-1553B. Complete E-MIL-STD-1553 transceiver is designed and implemented in a 3.3 V, 65 nm CMOS technology. E-MIL-STD-1553 analog transceiver is implemented in Verilog-A and Verilog-HDL respectively. Performance results shows a power consumption of 12.85 mW at 100-Mbps data rate for a 100 percent transmitter duty cycle, occupying an area of 199017 μm 2 , for a target BER of 10 −12 . Secondly, a new current mode continuous time linear equalizer (CTLE) with charge mode pole-zero adaptation scheme is proposed. The proposed equalizer is realized with common gate (CG) topology using switched capacitor based pole-zero adaptation to suit varying channel characteristics. The input impedance of the CG-CTLE is made equal to the characteristic impedance of the off-chip link, hence eliminating the need for a separate resistive termination. Since the proposed CG-CTLE acts as the first stage of the current mode receiver, there is no need for a separate trans-impedance amplifier or a pre-amplifier. The proposed CG-CTLE is implemented in a 1.1 V, 65 nm CMOS technology. The performance results show that it achieves a data rate of 15-Gbps while equalizing the loss of a 7.5 inch FR4 PCB trace. It also offers an input impedance of 44.6 ohm, SNR of 23 dB and a bandwidth of 7.575 GHz and consumes a power of 13.9 mW. Lastly, a new hybrid circuit topology for simultaneous bidirectional signaling across global short (3-mm) and long (10-mm) on-chip interconnects in a multi-channel signaling environment is proposed. The proposed hybrid circuit transmits the outbound signal and simultaneously receives the inbound signal from the combined signal, which is a superposition of the outbound and inbound signals. This work is implemented in 1.1 V, 65-nm CMOS technology. Post-layout results show that the proposed hybrid circuit operates at a data rate of 16-Gbps/ch over a 3-mm and 10-mm on-chip interconnects in a eight parallel channel environment and it achieves a transmitted signal swing of 520 mV and a received signal swing of 108 mV for a power consumption of 35.65 mW. In summary, interface circuits such as equalizers are proposed to nullify the adverse effects of high loss communications channels and hybrid circuit is proposed to increase the overall throughput of the system.

Abstract

A hand-drawn sketch is a convenient way to search for an image or a video from a database where examples are unavailable or textual queries are too difficult to articulate. In this thesis, we have tried to propose solutions for some problems in sketch-based multimedia retrieval. In case of image search, the queries could be approximate binary outlines of the actual objects. In case of videos, we consider the case where the user can specify the motion trajectory using a sketch, which is provided as a query. However there are multiple problems associated with this paradigm. Firstly, different users sketch the same query differently according to their own perception of reality. Secondly, sketches are sparse and abstract representations of images and the two modalities can not be compared directly. Thirdly, compared to images, datasets of sketches are rare. It is very difficult, if not impossible to train a system with sketches of every possible category. The features should be robust enough to retrieve classes that were not a part of training. In this thesis, the work can be broadly divided into three parts. First, we develop a motion-trajectory based video retrieval strategy and propose a representation for sketches that aims to reduce the perceptual variability among different users. We also propose a novel retrieval strategy, which combines multiple feature representations for a final result using a cumulative scoring mechanism. In order to tackle the problem of multiple modalities, we propose a sketch-based image retrieval strategy by mapping the two modalities into a lower dimensional sub-space where they are maximally correlated. We use Cluster Canonical Correlation Analysis (c-CCA), a modified version of standard CCA, for the mapping. Finally, we investigate the use of semantic features derived from a Convolutional Neural Network, and extend the idea of sketch-based image retrieval to the task of zero-shot learning or unknown class retrieval. We define an objective function for the network such that, while training, a close miss is penalized less than a distant miss. Our training encodes semantic similarity among the different classes. We perform experiments to evaluate our algorithms on well known datasets and our results show that our features perform reasonably well in challenging scenarios.

Abstract

Software Quality has been an important economic factor for every successful Software Product. It is quite challenging for large-scale software products, especially integrated software products to maintain its quality after every version release. Integrated Software Product is a software that combines two or more sub-products to achieve a similar business goal. These sub-products are interconnected to each other and share common packages of programs to form one application. Unlike non-integrated software products, integrated software products are complex in design. They require detailed exploration on the spread of a defect across entire integrated product suite along with causal analysis so as to improve overall product quality. Either due to security constraints or due to complicated workflow, quality engineers may not be able to access and analyze the source code of all sub-products together in a large scale integrated software product. Thus investigating defect dependency in large scale integrated software product is difficult. In this thesis, we present our efforts towards exploring various ways to estimate defect widespread or defect dependency of a defect in a large scale integrated software product. Current approaches are mostly non-generic and are developed for a specific product design with domain constraints and with predefined conditions. Very few approaches were found to be adaptable for large software products. However, they were neither evaluated nor validated using a real-time defect dataset of a large scale integrated software product. This motivated us to present a few approaches to estimate the defect widespread or defect dependency of a defect in a large scale integrated software product. Our approaches are heuristic by design, this is to achieve a generalized way to study the defect dependency in a software product of any domain and size. These approaches help product owners of an integrated software product to prioritize defects based on its widespread across the large software product and also help quality teams to evaluate the defect dependency so as to address dependent defects based on artifacts accessible to them. As part of our initial research, we examined Defect Dependency calculation using the concept of Generalized Dependency Degree method which is measure a of studying the dependency of an element over another. This method was primarily inspired by dependency degree approach from Rough Set Theory. We formulated this method into an approach by representing all recorded defects per sub product in a large scale integrated software product as onevset. We calculated Generalized Dependency Degree between defect sets of each sub-product so as to estimate the defect dependency over another. We implemented this approach on a real-time industrial defect dataset of a large scale integrated Human vi vii Resource Management product. Also captured significant results across various version releases. This is a simple and a generic approach to implement on a large software products. However, the level of abstraction on defect dependency calculation for a large software was limited to defects recorded at sub-product only. This prompted us to explore new ways to study defect dependency at a deeper level of abstraction in a large software product. Correlation analysis in statistics is one of the efficient way to understand the independence or dependency of elements in a given relation. We explored various ways on implementing correlation analysis on a defect dataset and formulated an approach based on correlation to study defect dependency between defects recorded in a large software product. For a better level of generalization, we have grouped defects recorded per feature in a large software product and performed defect correlation analysis to understand the defect dependency among defect sets of available software features. We evaluated this approach against Open Source (NetBeans IDE) defect dataset and captured noteworthy observations. We were able to record list of most defective features which are unstable when deployed together in a large software product.These results help product managers to prioritize defects recorded in defective features and focus towards building a stable software. However, product managers still may not be able to isolate the exact cause-effect of a single defect over entire large software product i.e. with the above proposed methods to study defect dependency, it is difficult to estimate the dependency of a single defect over entire large software product. This stimulated us towards exploring defect dependency at the lowest level of abstraction in a large software product. We composed another approach with a model framework as basis to evaluate defect dependency so as to fill this gap. We have implemented our approach using an i* modelling framework on a few real time software projects and have recorded notable observations. The approaches composed as part of th

Abstract

With the rapid growth of camera-based mobile devices, applications that answer questions such as, “What does this sign say?" are becoming increasingly popular. This is related to the problem of optical character recognition (OCR) where the task is to recognize text occurring in images. The OCR problem has a long history in the computer vision community. However, the success of OCR systems is largely restricted to text from scanned documents. Scene text, such as text occurring in images captured with a mobile device, exhibits a large variability in appearance. Recognizing scene text has been challenging, even for the state-of-the-art OCR methods. Many scene understanding methods recognize objects and regions like roads, trees, sky in the image successfully, but tend to ignore the text on the sign board. Towards filling this gap, we devise robust techniques for scene text recognition and retrieval in this thesis. This thesis presents three approaches to address scene text recognition problems. First, we propose a robust text segmentation (binarization) technique, and use it to improve the recognition performance. We pose the binarization problem as a pixel labeling problem and define a corresponding novel energy function which is minimized to obtain a binary segmentation image. This method makes it possible to use standard OCR systems for recognizing scene text. Second, we present an energy minimization framework that exploits both bottom-up and top-down cues for recognizing words extracted from street images. The bottom-up cues are derived from detections of individual text characters in an image. We build a conditional random field model on these detections to jointly model the strength of the detections and the interactions between them. These interactions are top-down cues obtained from a lexicon-based prior, i.e., language statistics. The optimal word represented by the text image is obtained by minimizing the energy function corresponding to the random field model. The proposed method significantly improves the scene text recognition performance. Thirdly, we present a holistic word recognition framework, which leverages scene text image and synthetic images generated from lexicon words. We then recognize the text in an image by matching the scene and synthetic image featureswith our novel weighted dynamic time warping approach. This approach does not require any language statistics or language specific character-level annotations. Finally, we address the problem of image retrieval using textual cues, and demonstrate large-scale text-to-image retrieval. Given the recent developments in understanding text in images, an appealing approach to address this problem is to localize and recognize the text, and then query the database, as in a text retrieval problem. We show that this approach, despite being based on state-of-the art methods, is insufficient, and propose an approach without relaying on an exact localization and recognition pipeline. We take a query-driven search approach, where we find approximate locations of characters in the text query, and then impose spatial constraints to generate a ranked list of images in the database. We evaluate our proposed methods extensively on a number of scene text benchmark datasets, namely, street view text, ICDAR 2003, 2011 and 2013, and a new dataset IIIT 5K-word, we introduced, and show better performance than all the comparable methods. The retrieval performance is evaluated on public scene text datasets as well as three large datasets, namely, IIIT scene text retrieval, Sports-10K and TV series-1M, we introduced.

Abstract

Digitization can provide a means of preserving the content of the materials by creating an accessible facsimile of the object in order to put less strain on already fragile originals such as out of print books. The document analysis community formed to address this by digitizing the content thus, making it easily shareable over Internet, making it searchable and, enabling language translation on them. In this thesis, we have tried to see optical character recognition as a mapping problem. We proposed extensions to two method and reduced its limitations. We proposed an application for sequence to sequence learning architecture which removed two limitations of previous state of art method based of connectionist temporal classification output layer. This method also gives representations which can be used for efficient retrieval. We also proposed an extension to profile features which enabled us to use same idea but by learning features from data. In first work, we propose an application of sequence to sequence learning approach for printed text Optical Character Recognition. In contrast to present day existing state-of-art OCR solution which uses Connectionist Temporal Classification (CTC) output layer our approach makes minimalistic assumptions on the structure and length of the sequence. We use a two step encoder-decoder approach – (a) A recurrent encoder reads a variable length printed text word image and encodes it to a fixed dimensional embedding. (b) This fixed dimensional embedding is subsequently comprehended by decoder structure which converts it into a variable length text output. The learnt deep word image embedding from encoder can be used for printed text based retrieval systems. The expressive fixed dimensional embedding for any variable length input expedites the task of retrieval and makes it more efficient which is not possible with other recurrent neural network architectures. Thus single model can do predictions and features learnt with supervision can be used for efficient retrieval. In the second work, we investigate the possibility of learning an appropriate set of features for designing OCR for a specific language. We learn the language specific features from the data with no supervision. In this work, we learn features using a unsupervised feature learning and use it with the RNN based recognition solution. We learn features using a stacked Restricted Boltzman Machines (RBM). These features can be interpreted as deep extension of projection profiles. These features can be used as a plug and play features to get improvements where profile feature are used. We validate these features on five different languages. In addition, these novel features also resulted in better convergence rate of the RNNs.

Abstract

After Bell’s celebrated work in 1964, demonstrating the incompatibility of Quantum Mechanics with the notion of local realism, there have been numerous conceptual and technical developments for studying nonlocality in quantum systems. The Bell inequality and Bell-type inequalities, set an upper bound on the correlations between measurement statistics of many particle systems that cannot be explained by local hidden variable models. Quantum entanglement has proven to be a key resource for various information theoretic protocols such as dense coding, teleportation, etc. Their numerous applications makes it consequential to pinpoint their behaviour. In the first chapter, a cursory delineation of the historical events in the development of Quantum theory, is followed by a concise introduction to the theory and mathematical tools needed for this thesis. The landmark papers of EPR and John Bell are discussed, so as to provide an understanding of the significance of Bell’s theorem and thus the Bell’s inequalities. Quantum Entanglement is discussed, and in particular, measures that are used later to quantify tripartite correlations are described in greater detail. The second chapter discusses Bell-CHSH inequality for two qubit systems and Bell-type inequalities for multi-qubit systems; and the theory independent derivation of Bell-CHSH inequality, known as the Device Independent scenario, where the characteristics of the probability distributions shared between two or more parties are sufficient to define different kinds of nonlocal correlations, without recourse to any underlying theory. The third chapter briefly goes over the disjoint sets of genuinely entangled three qubit pure states that constitute the GHZ and W classes of states. It also introduces a new class of states called the Maximally Bell-Inequality Violating (MBV) class of states. This is followed by the description of the analytical calculations for the maximum bipartite Bell Inequality violations of the three classes. For each of the three classes a complementary relation is then established between the maximum bipartite Bell Inequality Violation and tripartite correlation measures - Generalized Geometric Measure (GGM), Tangle and Discord Monogamy Score (DMS). Numerical evidence for this is also provided. The fourth chapter discusses first the convex roof extension of the complementary relations described above and then it goes on to discuss the results of the obvious next step, comparing tripartite nonlocality with tripartite correlation measures. The analysis is put forth as a future problem which possibly has quite a few fascinating insights in store.

Abstract

Scientific method of finding a new law pertains to three sequential steps. First we guess a law, second we compute its consequences and third we compare the consequences with experiments. On top of these lies the pillar of science, if these consequences disagree with observation the guessed law is wrong. Science can never assert that any theory, or law explains nature. It can only tell which ones cannot. The twentieth century saw Humankind asking one of the most fundamental question regarding the nature of reality and determinism. EPR in 1935 questioned the completeness of Quantum Mechanics (a proba- bilistic theory as a fundamental theory). Bell’s framework developed to answer the question, introduced first notions of theory independent tests. While we cannot say whether there exists a deterministic ex- planation to every prediction of QM, but we can reject a subclass of deterministic explanation, local deterministic explanation. This experimentally verified departure of predictions of QM or any theory from any local deterministic explanation is referred to as non-locality. In first chapter origins and mathematical formalism of quantum mechanics is presented. Followed by presentation of EPR argument, Bell’s theorem, implications and applications in the second chapter. Fol- lowing chapters contain the main contributions from the author. In third chapter, we study the consequences of both answers set in a device (theory) independent frame- work, based only on observed statistics. We start with taking up post-selection as an assumption and model the same using independent devices governed by Boolean functions. We establish analogy be- tween the post selection functions and the general probabilistic games in a two party binary input-output scenario. As an observation, we categorize all possible post-selection functions based on the effect on a uniform input probability distribution. We find that post-selection can transform simple no signaling probability distributions to signaling. Similarly, solving NP complete problems is easy independent of classical or quantum computation (in particular we prove that Post RP = NP). Finally, we demonstrate an instance of the violation of the pigeon hole principle independent of underlying theory. As result of our theory independent modeling we conclude that post-selection as an assumption adds power to the underlying theory. In particular, quantum mechanics benefits more with the post-selection assumption, only because it admits a more general set of allowed probabilities as compared to the local hidden vari- able model. Without the assumption we associate a device independent efficiency factor to quantify the cost of post selection. Our study shows that in the real world post-selection is not efficient enough to be of any advantage. But from an adversarial perspective it is still of significance. As an application, we obtain robust bounds on faking the bell violation in terms of minimum efficiency required using post selection. In fourth chapter we study a semi device-independent protocol wherein the knowledge of success prob- ability of the associated dimension witness and the observed efficiency of the detectors (η a vg) are suf- ficient to determine the security. We consider practically possible, individual attacks with and without eavesdropper having access to quantum memory. We find critical detection efficiencies required for security in both cases. In fifth chapter we introduce generalizations to PR and (2 → 1) RAC and study their inter-convertibility. We introduce generalizations based on the number of inputs provided to Alice, B n -BOX and (n → 1) RAC. We show that a B n -BOX is equivalent to a no-signaling (n → 1) RACBOX (RB). Further we introduce a signaling (n → 1) RB which cannot simulate a B n -BOX. Finally to quantify the same we provide a resource inequality between (n → 1) RB and B n -BOX, and show that it is saturated. As an application we prove that one requires atleast (n − 1) PRs supplemented with a bit of communication to win a (n → 1) RAC. We further introduce generalizations based on the dimension of inputs provided to Alice and the mes- sage she sends, B n d (+)-BOX, B n d (−)-BOX and (n → 1, d) RAC (d > 2). We show that no-signaling condition is not enough to enforce strict equivalence in the case of d > 2. We introduce classes of no-signaling (n → 1, d) RB, one which can simulate B n d (+)-BOX, second which can simulate B n d (−)- BOX and third which cannot simulate either. Finally to quantify the same we provide a resource in- equality between (n → 1, d) RB and B n d (+)-BOX, and show that it is saturated. In sixth chapter we introduce the measurement-device-independent randomness certification task where one has trusted quantum state preparation device but the mesurement devices are completely unspec- ified. Interestingly we show that there exist entangled states, w