Abstract

Units within a piece of text are not meant to be understood independently but understood by linking them with other units in the text. These units maybe clauses, sentences or even complete paragraphs. Establishing relations between units present in a text allows the text to be semantically well structured and understandable. Understanding the internal structure of text and the identification of discourse relations is called discourse analysis. A fully automated shallow discourse parser would greatly aid discourse analysis and improve performance of NLP applications such as question-answering and text summarization. Given a text, a shallow discourse parser would extract discourse relations, each between two spans of text. Discourse relations whose presence is explicitly marked by a discourse connective are called Explicit discourse relations and those which are not are called Implicit discourse relations. This thesis covers the experiments and research conducted to build a shallow discourse parser for explicit discourse relations in Hindi. The pipeline proposed achieves state of the art performance.

Abstract

Papillary renal cell carcinoma (PRCC) is the second most common subtype of renal cell carcinoma accounting for 10 − 15% cases. PRCC is a heterogeneous disease with variations in disease progression and clinical outcomes. The advent of next generation sequencing techniques (NGS) has led to the creation of multi-omics data of PRCC. In this thesis, multi-omics data involving gene expression and DNA methylation of PRCC is analyzed to identify biomarkers, develop predictive models of tumor (with Group Lasso) using both gene expression and DNA methylation features showed the overall best performance on test data with MCC and PR AUC of 0.77 and 0.82, respectively, across different rep-resentations of methylation data and feature sets. Our study not only generates insights into the gene regulation but also develops models that will have diagnostic applications. stage prediction and understand the relationship between them. We first developed a machine learning pipeline incorporating different feature selection algorithms and classification models for tumour stage prediction using RNA sequencing dataset (RNASeq). To get a reliable feature set, we extracted features from different partitions of the training dataset and aggregated them into feature sets for classification. We evaluated the performance of different algorithms on the basis of 10-fold cross validation (CV) and independent test dataset. 10-fold CV was also performed on a microarray dataset of PRCC. A random forest based feature selection yielded minimum number of features (104) and a best performance with area under Precision Recall curve (PR AUC) of 0.80, MCC (Matthews Correlation Coefficient) of 0.71 and accuracy of 88% with Shrunken Centroid classifier on a test dataset. We identified 80 genes that are consistently altered between stages by different feature selection algorithms. The extracted features are related to cellular components -centromere, kinetochore and spindle, and biological process mitotic cell cycle. The interactions between features also reveal the systems-level alteration driving the progression from early stage to late stage of PRCC. The potential mechanisms for an increase in chromosome instability in the late stage of PRCC has been proposed. We then investigated the methylation patterns of PRCC and its relationship with the gene expression using Illumina methylation 450K array. We found that both the promoter and body of tumor suppressor genes, microRNAs and gene clusters and families including cadherins, protocadherins, claudins and collagens are hypermethylated in PRCC. Hypomethylated genes in PRCC are associated with the immune function. The gene expression of several novel candidate genes including interleukin receptor IL17RE and immune checkpoint genes HHLA2, SIRPA and HAVCR2 shows significant correlation with the DNA methylation. A significant correlation within the tumor samples was also observed for genes RRM2, NCAPG and SLC7A11, which we found to be potential biomarkers for stage progression in the first part of our study. Further, we developed predictive models based on single- and multi-omics data to distinguish early and late stages of PRCC. A comparative study of predictive models, data in- tegration techniques and representations of methylation data was performed. Multiple kernel learning (with Group Lasso) using both gene expression and DNA methylation features showed the overall best performance on test data with MCC and PR AUC of 0.77 and 0.82, respectively, across different rep- resentations of methylation data and feature sets. Our study not only generates insights into the gene regulation but also develops models that will have diagnostic applications.

Abstract

In today’s world, users prefer getting a precise answer to their questions rather than a set of relevant documents provided by search engines. It has led to the immense popularity of Community Question Answering( CQA ) forums, where forum users respond directly to questions with targeted answers. Users ask question to other members of community and expect domain experts to answer questions. Questions asked on community Question answering are generally different in nature than traditional search queries due to specific user needs. A user may have a query about the general topic to a most specific one. Hence, user uses CQA platforms to express users query in more verbose form. Recently, Community Question Answering forums are gaining huge popularity in the health-care domain. The impact of the health-care industry on a day to day patient care and on biomedical research is immense. Owing to an exponential growth of online information seekers in the health domain, there is a particularly great and growing demand for QA systems that can effectively and efficiently aid consumers in their information search. However, in order to get better and quick responses to questions on health forums, it is important to categorize questions and direct them to appropriate experts based on question types. Due to huge popularity of CQA’s, people get noisy, non-relevant responses as well along with relevant one. In order to improve the quality of CQAs, it is important to filter out noisy answers and present only relevant answers. In this thesis, we propose a model to classify question-based on user intentions. We also introduce a model which predicts relevance of answers with respect to the question. After defining relevance of answers, our model also predicts polarity of answers with respect to question. In the first model, we propose a novel approach for classifying questions capturing a unique user intent posted on health forums. Our proposed model combines deep learning based features along with domain based knowledge and statistical features. We further added weak supervision to improve performance. We also proposed a unique model of weak supervision, called ”Self-training with Lookups”. Our best performing model for question classification provides an accuracy of 71.13%, which beats the state-of-the-art method with a margin of 3.13%. In the second model, we work towards finding the relevance and polarity of responses to questions. When questions get thousands of responses, it becomes difficult for the user to read every response and he or she might lose some important response. The dataset consists of questions and corresponding responses having some inherent implicit opinions. First, we devise a model to find if the answer is relevant to the question. In the next step, model categorizes relevant answers based on their polarity. Our Final model takes ensemble representation of TF-IDF vector and Doc2Vec vector as features. Traditional machine learning model like multinomial naive Bayes performed superior to other models in ensemble environment

Abstract

A smart grid is an efficient and sustainable energy system that integrates diverse generation entities,distributed storage capacity, and smart appliances and buildings. Smart grids also indirectly facilitate end-user involvement in grid stability. The brokers, supplying electricity to end-users, represent large population of customers in the electricity markets, and incentivization of such brokers to reduce their supply-demand imbalance can lead to utilization of sustainable but intermittent sources of energy like solar and wind energy. Overall, this will reduce grid operationalization costs by reducing peak demand, and reduce broker costs, and in-turn reduce energy costs for the end-users. Most of the electricity markets consist of Periodic Double Auctions (PDAs), where trillions of dollars worth electricity is traded. Any broker participating in these PDAs has to plan for bids in the current auction as well as for the future auctions, which highlights the necessity of good bidding strategies. Since the complexity and dimensionality of the actions taken by such brokers is huge, it opens avenues for deployment of autonomous energy brokers. Smart grids also bring new kind of participants in the energy markets, whose effect on the grid can only be determined through high fidelity simulations. Power TAC offers one such simulation platform using real-world weather data and complex state-of-the-art customer models. In Power TAC, autonomous energy brokers compete to make profits across tariff, wholesale and balancing markets while maintaining the stability of the grid. We make the following contributions to the areas of smart grid, autonomous agents, game theory and machine learning applications: (1) We do a Nash Equilibrium analysis of single unit single-shot double auctions with a certain clearing price and payment rule, which we refer to as ACPR, and find it intractable to analyze as number of participating agents increase. We further derive the best response for a bidder with complete information in a double auction with ACPR. (2) Leveraging the theory developed for single-shot double auction, we proceed by modeling the PDA of Power TAC wholesale market as a Markov Decision Process (MDP), and solve it using dynamic programming. Based on that, we propose a novel bidding strategy, namely MDPLCPBS. We empirically show that MDPLCPBS follows the equilibrium strategy for double auctions that we previously analyze. In addition, we benchmark our strategy against the baseline and the state-of-the art bidding strategies for the Power TAC wholesale market PDAs, and show that MDPLCPBS outperforms most of them consistently. (3) We design a electricity usage predictor, which uses customer usage patterns and weather data, using neural networks. This is the first usage predictor which utilizes weather data in the Power TAC scenario. (4) We use an MDP based formulation for the tariff market, and solve it using Q-learning to generate tariffs. The novelty lies in defining the reward functions for the MDP, solving the MDP, and the transformation of the solution into a tariff in the tariff market. We also propose a few heuristics which convert nearoptimal fixed tariffs to time-of-use tariffs aimed at mitigating transmission capacity fees. (5) We discuss the architecture of our autonomous energy broker VidyutVanika, which was the runner-up in Power TAC 2018 Finals. VidyutVanika implements our learning strategies for the tariff and wholesale market, along with a few heuristic ideas. We have also released VidyutVanika’s binary for offline testing and research purposes. (6) We do an empirical analysis of VidyutVanika’s performance during Power TAC 2018 Finals, using Power TAC 2018 tournament data. We also illustrate the efficacy of its sub-modules and strategies using controlled experiments.

Abstract

Speech communication carries message at two levels, the explicit message and implicit message. The explicit message corresponds to the linguistic information. The implicit message consists of information regarding the speaker’s signature, underlying emotion of the speaker, gender, etc. The speech production of basic linguistic sound units is generally understood using factors like voicing, place and manner of articulation. The implicit information like gender and speaker’s signature is due to physiological constraints of the speaker. In different emotional states, the linguistic sound units are produced by changes in the production mechanism in such a way that they do not effect the linguistic information. The state-of-the-art approaches for automatic emotion recognition use common features for representation. The feature representations can be categorized into spectral, voice quality, and prosody features. Along with the emotion-related characteristics, the voice quality features carry information of speaker’s signature, and the spectral features carry sound unit information. Also due to sharing of similar properties across emotions, the performance of emotion classification systems developed using these features is generally low. The main challenge in emotional speech analysis is to identify and extract emotion-specific features, i.e., independent of speaker and sound units. The objective of this thesis is to study the features of speech production that contribute for emotion characteristics in speech, and develop methods to extract the emotion-specific features. The speech production mechanism is a combination of several components such as the vocal tract system, excitation source, and prosody-related information (intonation and duration). In this thesis, the relative contribution of different components of speech production for perception of emotion is studied. It is observed that the components related to the excitation source and prosody carry emotion characteristics predominantly. The significant excitation of the vocal tract system occurs around the instants of glottal closure (GCIs). The region around the GCI corresponds to high signal-to-noise ratio (SNR) region. Excitation source-related parameters such as the abruptness of glottal closure, strength of excitation, and energy of excitation extracted around the GCIs are examined for emotion classification. These excitation source-related parameters are also observed to be speaker-dependent, and hence they are expressed relative to the neutral speech for emotion classification. For extraction of features which are independent of speaker and sound units, a hierarchical approach is considered for detailed analysis. An important characteristic of emotional speech is that it carries inherent voice qualities. Voice qualities of speech such as arousal and rhythm are different for different emotions. In view of inherent voice qualities of emotion, the following studies are identified: Discrimination between modal speech and falsetto speech, identification of high arousal speech segments in modal speech, and discrimination between angry speech and happy speech in high arousal case. All the above studies have been carried out using excitation source information at various levels of speech. The excitation source information related to the abruptness of glottal closure at subsegmental level discriminates modal and falsetto speech. But this subsegmental information is inadequate for discrimination of high arousal and neutral speech. It is observed that the excitation source information of the entire glottal cycle is useful for identification of high arousal speech segments. For discrimination between angry speech and happy speech, the excitation source information at the suprasegmental level appears to be useful. The studies carried out in this thesis highlight the importance of analysis of the glottal vibration characteristics, and the need for different sets of features for different emotions. The key contributions of the this thesis are: • Discrimination between falsetto and modal utterances using the excitation source information at the instants of significant excitation • Identification of high arousal regions in the speech signal using the excitation source information of the entire glottal cycle. • Reference based emotion recognition system using the excitation source parameters extracted at subsegmental level of speech. • Collection of resourceful emotional speech database.

Abstract

This thesis is mainly divided into two parts, first we formulate the optimal coalition formation in federated clouds as an integer linear programming problem under the cloud service brokerage model proposed by Mashayekhy et al [14]. Then we propose a fast polynomial time greedy algorithm to find a near optimal coalition. The profit generated by the federation obtained using the greedy algorithm is within a negligible 0.06 percent of the optimal on an average. The greedy algorithm finds a federation 200 times faster on an average when compared with the Merge-Split algorithm. The payoff distribution within a federation is determined using exact Banzhaf index computation whereas the Merge-Split algorithm arrives at a payoff using an estimate of Banzhaf values. By computing the payoff distribution after the federation formation, we are able to achieve 66x speedup when compared with the Merge-Split algorithm. Finally, we describe an ensemble of problem instances wherein the ratio between the value of an optimal federation and that of the federation generated by the Merge-Split algorithm is unbounded. In the second part, we study how an oligopolist influences the coalition structure in federated cloud markets. Specifically, we use cooperative game theory to model the circumstances under which a cloud provider prefers to join a cloud federation vis-a-vis consider taking a price offer made by an oligopolist.

Abstract

The need for the more and more number of devices, in turn higher numbers of functions in a single Integrated Circuit (IC) and greater operating speed are the prime reason for the continuous downsizing of CMOS technology. However, such progressive miniaturization of device dimensions in CMOS circuits has also imported an enormous increase in process variability and therefore, performances figures like propagation delays and power dissipation notably the leakage power are severely degraded. Downscaling the technology nodes in CMOS integrated circuits at or below 45nm have fastened the performance of the circuits but at the cost of the power consumption. CMOS Integrated Circuits have expelled the barrier to achieve minimum power consumption undoubtedly, though it is getting quite difficult to achieve desired performances in the circuits in ultra-deep sub-micron regime. This expeditious scaling in IC causes the dominating behaviour of static power over dynamic power. Enormous increase in process variations (due to progressive CMOS technology scaling) along-with the temperature and supply voltage variations are severely degrading the fabrication outcome of digital circuits i.e. circuits are not accomplishing the specification bounds of the required performances. Therefore, process and operating variations aware optimization has become a very essential task in VLSI design. Moreover, many specifications in a circuit have challenging trade-offs, hence demand effective optimization skills. With this vision, this thesis presents various optimization algorithms based robust transistor sizing calculation for various nanoscale CMOS digital circuits. The algorithms used to optimize the fitness function along with constraints set are meta heuristics such as evolutionary based Genetic Algorithm, thermo based Simulated Annealing algorithm, swarm based Artificial Bee Colony and Particle Swarm Optimization algorithm. The objective is to minimize the static i.e. leakage power without degrading the operating frequency (i.e. keeping the propagation delays in bound) and area. Statistical variation aware robust transistor sizing (width/length) is calculated for the various 2 input and 3 input basic logic gates such as AND, OR, NOT, NAND, NOR, XOR, Full-adder etc. and the obtained sizing is used to size the various other complex cells such 32-bit ripple carry adder, carry select adder, carry save adder and multiplier and few ISCAS benchmark circuits. Notably, our methodology targets semi-custom digital design: once the cell library layout are designed, they can be placed wherever needed in a semi-custom design by technology mapping tools. Monte Carlo simulations have been performed for all the logic cells with 50,000 random statistical samples to check the circuit’s yield,which is found to be around 99.8%. The leakage power is reduced up to 88% without giving any penalty to the propagation delay. Also, the author has proposed two novel techniques to minimize the stand by mode leakage power of 1 bit full adder cell and compared their results with the nominal one. The optimization is done for 45nm, 32nm and 22nm metal gate high-k productive technology model. The obtained PVT variations aware transistor sizing (width/length) are used to optimize other full adder based cells.

Abstract

Cooperative regenerating codes are regenerating codes designed to trade off storage for repair band-width in case of multiple node failures. Minimum storage cooperative regenerating codes (MSCR) are a class of cooperative regenerating codes which achieve the minimum storage point of the trade off. The main limitation in the practical implementation of these codes is its very large sub-packetization level. -MSR codes are a class of codes introduced to trade off sub-packetization level for a slight increase in the repair bandwidth for the case of single node failures. In this work, we introduce the framework of -MSCR codes which allow for a similar trade off for the case of multiple erasures. We present a construction of -MSCR codes, which can recover from two node failures, by concatenating a class of MSCR codes and scalar linear codes. We give two different repair procedures to repair the -MSCR codes in the event of two node failures (a) in a cooperative manner and (b) in a centralized manner. In cooperative method, repair takes places in two rounds and the failed nodes are allowed to communicate between themselves. The failed nodes do not communicate between themselves in a centralized repair model and there is a central node that recovers the contents of all the failed nodes. We calculate the repair bandwidth for each repair procedure and characterize the increase in repair bandwidth incurred by the method in comparison with the optimal repair bandwidth given by the respective cut-set bound for each case. We then show that the sub-packetization level of -MSCR codes scales logarithmically in the number of nodes and require a field size of the order of the number of nodes. The repair problem can be simplified with the help of codes with constant repairing subspaces. The existence of these codes have been proven for the case of single erasures. However, no such existence was proven for the case of multiple erasures. We prove the existence of such codes for the recovery of two failed nodes namely (a) for the failure of two systematic nodes, (b) for the failure of a systematic node and a parity node. We also give the rank conditions which need to be satisfied for successful recovery of the failed nodes for each case.

Abstract

IoT domains such as health-care, automation and control, augmented and virtual reality etc are incubating novel applications and devices everyday. The data generated in these domains must be processed under strict delay requirements. Beyond the processing deadlines, the information loses its value. Apart from that, processing resources are required to be available all the time and Cloud’s or communication failure must not hinder the services provided by such IoT applications. So, reliability is one of the major concerns for all these IoT applications. Considering all these requirements, it is been observed that instead of processing such data at the far Cloud, it is beneficial to process it closer to the source. This led to a new paradigm called Edge Computing. Edge computing has emerged as an effective solution for delay sensitive IoT applications. In the Edge-Cloud hierarchy, reliability and fault tolerance are the major issues. This thesis proposes a novel fault-tolerant and reliable hierarchical IoT-Cloud architecture which can survive the failures of the Cloud Server and the Edge Server(s). In the proposed architecture, the sensed data processing is distributed over four levels (Cloud-Fog- Mist-Dew) based on the level processing power and distance from the end IoT devices. This hierarchical architecture is an advancement over the existing IoT-Cloud architecture. The proposed system becomes reliable by replicating the model-files (generated after data training) and some relevant data at the Edge Server from the Cloud. It allows the Edge to generate feedback after receiving the sensed data, in case of any event happens. It indeed improves the reliability of IoT applications by providing them services in the case of unavailability of the processing resources especially due to the communication failure with the Cloud Server. Although, hierarchical Edge-Cloud architecture resolves the problems of resource unavailability and feedback delays, what if the Edge Server fails? It induces unheard issues of reliability and fault tolerance at the Edge. The system can not be completely reliable until the reliability issues at the edge of the network are resolved. This thesis proposes a novel mechanism using connection switching to deal with Edge Servers’ failures. In case of an Edge failure, IoT application is redirected to an alternate available Edge Server. If there are multiple alternate Edge Servers available, redirection to a new Edge is decided based on the delay-tolerance of the IoT applications. It makes the entire system reliable and fault-tolerant. The proposed IoT-Cloud architecture with Reliable-Edge has been implemented as an extension of Landslide Early Warning System (LEWS) to improve its reliability. LEWS is one of the most suitable applications to apply the proposed mechanism(s). During laboratory experiments, results demonstrate that the system attains maximum availability of the computation resources. Along with this, results prove its efficiency when the proposed system is analyzed theoretically and simulated using Matlab. The thesis also contributes to the construction of a Reliable Edge Controller (EC) that reliably assigns any type of computational resources available at the edge to the IoT applications. A variety of devices available at the network access layer have been considered to be utilized to serve IoT applications. This includes the use of devices available with private users, dedicated Edge Servers and Cloud infrastructure. The proposed system learns the optimal operating parameters during initial runs. Using the knowledge acquired in the learning phase, an integer linear programming problem is formulated to minimize the Mean Time To Complete (MTTC) the request for all the IoT nodes. The solution of the formulated problem provides optimized resource allocation for all the IoT nodes. Later, considering the unreliable nature of the privately owned devices, the learning and formulation has been extended to incorporate probability of failure of these devices. This evolves the EC into a reliable one. Keywords: Internet of Things (IoT), Edge Computing, Real-time Applications, Reliability, Fault Tolerance, Cloud Computing, SDN

Abstract

Even in today’s world, a large number of documents are generated as handwritten documents. This is specially true when the knowledge/expertise is captured conveniently with availability of electronic gad- gets. Information extraction from handwritten document images has numerous applications, especially in digitization of archived handwritten documents, assessing patient medical records and automated evaluation of student handwritten assessments, to mention a few. Document categorization and tar- geted information extraction from various such sources can help in designing better search and retrieval systems for handwritten document images. Information extraction from handwritten medical records written in ambulance for doctor’s interpretation in hospital, reading postal address to automate the let-ter sorting are examples where document image work flow helped in scaling the system with minimal human intervention. In such work flow systems, images flow across subjects who can be in different locations. Our work is motivated with the success of these document image work-flow systems that were put into practice when the handwriting recognition accuracy was unacceptably low. Our goal is to bring scalability in handwritten document processing which can enhance the throughput of the analysis by employing multitude of developments in document image space. In this thesis, we initially focus on presenting a document image workflow system that helps in scal-ing the handwritten student assessments in a typical university setting. We observed that this improves the efficiency since the book keeping time as well as physical paper movement is minimized. An electronic workflow can make the anonymization easy, alleviating the fear of biases in many cases. Also, parallel and distributed assessment by multiple instructors is straightforward in an electronic workflow system. At the heart of our solution, we have (i) a distributed image capture module with a mobile phone (ii) image processing algorithms that improve the quality and readability (iii) image annotation module that process the evaluations/feedbacks as a separate layer. Further, we extend our work by proposing an approach to detect POS and Named Entity tags directly from offline handwritten document images without explicit character/word recognition. We observed that POS tagging on handwritten text sequences increases the predictability of named entities and also brings a linguistic aspect to handwritten document analysis. As a pre-processing step, the document image is binarized and segmented into word images. The proposed approach comprising of a CNN - LSTM model, trained on word image sequences produces encouraging results on challenging IAM dataset. Finally, we describe an effective method for automatically evaluating the short descriptive hand-written answers from the digitized images. Automated evaluation of handwritten answers has been a challenging problem for scaling education system for many years. Speeding up the evaluation still re- mains as the major bottleneck for enhancing the throughput. Our goal is to assign an evaluation score that is comparable to the human assigned scores. Our solution is based on the observation that a human evaluator judges the relevance of the answer using a set of keywords and their semantics. Since reliable handwriting recognizer are not yet available, we attempt this problem in the image space. We model this problem as a self supervised, feature based classification problem, which can fine tune itself for each question without any explicit supervision. We conduct experiments on three different datasets obtained from students. Experiments show that our method performs comparable to that of human evaluators. With these works, we attempted to bring state-of-the-art enhancements in handwritten document analysis and deep learning into scalable applications which can be helpful in the field of education.