etd@IISc Collection:http://hdl.handle.net/2005/182014-12-12T02:16:19Z2014-12-12T02:16:19ZGraph Models For Query Focused Text Summarization And Assessment Of Machine Translation Using StopwordsRama, Bhttp://hdl.handle.net/2005/22942014-04-09T10:57:00Z2014-04-08T18:30:00ZTitle: Graph Models For Query Focused Text Summarization And Assessment Of Machine Translation Using Stopwords
Authors: Rama, B
Abstract: Text summarization is the task of generating a shortened version of the original text where core ideas of the original text are retained. In this work, we focus on query focused summarization. The task is to generate the summary from a set of documents which answers the query. Query focused summarization is a hard task because it expects the summary to be biased towards the query and at the same time important concepts in the original documents must be preserved with high degree of novelty.
Graph based ranking algorithms which use biased random surfer model like Topic-sensitive LexRank have been applied to query focused summarization. In our work, we propose look-ahead version of Topic-sensitive LexRank. We incorporate the option of look-ahead in the random walk model and we show that it helps in generating better quality summaries.
Next, we consider assessment of machine translation. Assessment of a machine translation output is important for establishing benchmarks for translation quality. An obvious way to assess the quality of machine translation is through the perception of human subjects. Though highly reliable, this approach is not scalable and is time consuming. Hence mechanisms have been devised to automate the assessment process. All such assessment methods are essentially a study of correlations between human translation and the machine translation.
In this work, we present a scalable approach to assess the quality of machine translation that borrows features from the study of writing styles, popularly known as Stylometry. Towards this, we quantify the characteristic styles of individual machine translators and compare them with that of human generated text. The translator whose style is closest to human style is deemed to generate a higher quality translation. We show that our approach is scalable and does not require actual source text translations for evaluation.2014-04-08T18:30:00ZAlgorithms For Stochastic Games And Service SystemsPrasad, H Lhttp://hdl.handle.net/2005/23012014-04-23T06:02:50Z2014-04-22T18:30:00ZTitle: Algorithms For Stochastic Games And Service Systems
Authors: Prasad, H L
Abstract: This thesis is organized into two parts, one for my main area of research in the field of stochastic games, and the other for my contributions in the area of service systems. We first provide an abstract for my work in stochastic games.
The field of stochastic games has been actively pursued over the last seven decades because of several of its important applications in oligopolistic economics. In the past, zero-sum stochastic games have been modelled and solved for Nash equilibria using the standard techniques of Markov decision processes. General-sum stochastic games on the contrary have posed difficulty as they cannot be reduced to Markov decision processes. Over the past few decades the quest for algorithms to compute Nash equilibria in general-sum stochastic games has intensified and several important algorithms such as stochastic tracing procedure [Herings and Peeters, 2004], NashQ [Hu and Wellman, 2003], FFQ [Littman, 2001], etc., and their generalised representations such as the optimization problem formulations for various reward structures [Filar and Vrieze, 1997] have been proposed. However, they suffer from either lack of generality or are intractable for even medium sized problems or both. In our venture towards algorithms for stochastic games, we start with a non-linear optimization problem and then design a simple gradient descent procedure for the same. Though this procedure gives the Nash equilibrium for a sample problem of terrain exploration, we observe that, in general, it need not be true. We characterize the necessary conditions and define KKT-N point. KKT-N points are those Karush-Kuhn-Tucker (KKT) points which corresponding to Nash equilibria. Thus, for a simple gradient based algorithm to guarantee convergence to Nash equilibrium, all KKT points of the optimization problem need to be KKT-N points, which restricts the applicability of such algorithms.
We then take a step back and start looking at better characterization of those points of the optimization problem which correspond to Nash equilibria of the underlying game. As a result of this exploration, we derive two sets of necessary and sufficient conditions. The first set, KKT-SP conditions, is inspired from KKT conditions itself and is obtained by breaking down the main optimization problem into several sub-problems and then applying KKT conditions to each one of those sub-problems. The second set, SG-SP conditions, is a simplified set of conditions which characterize those Nash points more compactly. Using both KKT-SP and SG-SP conditions, we propose three algorithms, OFF-SGSP, ON-SGSP and DON-SGSP, respectively, which we show provide Nash equilibrium strategies for general-sum discounted stochastic games. Here OFF-SGSP is an off-line algorithm while ONSGSP and DON-SGSP are on-line algorithms. In particular, we believe that DON-SGSP is the first decentralized on-line algorithm for general-sum discounted stochastic games. We show that both our on-line algorithms are computationally efficient. In fact, we show that DON-SGSP is not only applicable for multi-agent scenarios but is also directly applicable for the single-agent case, i.e., MDPs (Markov Decision Processes).
The second part of the thesis focuses on formulating and solving the problem of minimizing the labour-cost in service systems. We define the setting of service systems and then model the labour-cost problem as a constrained discrete parameter Markov-cost process. This Markov process is parametrized by the number of workers in various shifts and with various skill levels. With the number of workers as optimization variables, we provide a detailed formulation of a constrained optimization problem where the objective is the expected long-run averages of the single-stage labour-costs, and the main set of constraints are the expected long-run average of aggregate SLAs (Service Level Agreements). For this constrained optimization problem, we provide two stochastic optimization algorithms, SASOC-SF-N and SASOC-SF-C, which use smoothed functional approaches to estimate gradient and perform gradient descent in the aforementioned constrained optimization problem. SASOC-SF-N uses Gaussian distribution for smoothing while SASOC-SF-C uses Cauchy distribution for the same. SASOC-SF-C is the first Cauchy based smoothing algorithm which requires a fixed number (two) of simulations independent of the number of optimization variables. We show that these algorithms provide an order of magnitude better performance than existing industrial standard tool, OptQuest. We also show that SASOC-SF-C gives overall better performance.2014-04-22T18:30:00ZReliability Modelling Of Whole RAID Storage SubsystemsKarmakar, Prasenjithttp://hdl.handle.net/2005/23232014-06-05T10:18:31Z2014-06-04T18:30:00ZTitle: Reliability Modelling Of Whole RAID Storage Subsystems
Authors: Karmakar, Prasenjit
Abstract: Reliability modelling of RAID storage systems with its various components such as RAID controllers, enclosures, expanders, interconnects and disks is important from a storage system designer's point of view. A model that can express all the failure characteristics of the whole RAID storage system can be used to evaluate design choices, perform cost reliability trade-offs and conduct sensitivity analyses.
We present a reliability model for RAID storage systems where we try to model all the components as accurately as possible. We use several state-space reduction techniques, such as aggregating all in-series components and hierarchical decomposition, to reduce the size of our model. To automate computation of reliability, we use the PRISM model checker as a CTMC solver where appropriate.
Initially, we assume a simple 3-state disk reliability model with independent disk failures. Later, we assume a Weibull model for the disks; we also consider a correlated disk failure model to check correspondence with the field data available. For all other components in the system, we assume exponential failure distribution. To use the CTMC solver, we approximate the Weibull distribution for a disk using sum of exponentials and we first confirm that this model gives results that are in reasonably good agreement with those from the sequential Monte Carlo simulation methods for RAID disk subsystems.
Next, our model for whole RAID storage systems (that includes, for example, disks, expanders, enclosures) uses Weibull distributions and, where appropriate, correlated failure modes for disks, and exponential distributions with independent failure modes for all other components. Since the CTMC solver cannot handle the size of the resulting models, we solve such models using hierarchical decomposition technique. We are able to model fairly large configurations with upto 600 disks using this model.
We can use such reasonably complete models to conduct several "what-if" analyses for many RAID storage systems of interest. Our results show that, depending on the configuration, spanning a RAID group across enclosures may increase or decrease reliability. Another key finding from our model results is that redundancy mechanisms such as multipathing is beneficial only if a single failure of some other component does not cause data inaccessibility of a whole RAID group.2014-06-04T18:30:00ZDesign Of Truthful Allocation Mechanisms For Carbon Footprint ReductionUdaya Lakshmi, Lhttp://hdl.handle.net/2005/23222014-06-05T07:34:41Z2014-06-04T18:30:00ZTitle: Design Of Truthful Allocation Mechanisms For Carbon Footprint Reduction
Authors: Udaya Lakshmi, L
Abstract: Global warming is currently a major challenge faced by the world. Reduction of carbon emissions is of paramount importance in the context of global warming. There are widespread ongoing efforts to find satisfactory ways of surmounting this challenge. The basic objective of all such efforts can be summarized as conception and formation of protocols to reduce the pace of global carbon levels. Countries and global companies are now engaged in understanding systematic ways of achieving
well defined emission targets. In this dissertation, we explore the specific problem faced by a global industry or global company in allocating carbon emission reduction units to its different divisions and supply chain partners in achieving a required target of reductions in its carbon reduction program. The problem becomes a challenging one since the divisions and supply chain partners are often autonomous and could exhibit strategic behavior. Game theory and mechanism design provide a natural modeling tool for capturing the strategic dynamics involved in this problem.
DSIC (Dominant Strategy Incentive Compatibility), AE (Allocative Efficiency), and SBB (Strict Budget Balance) are the key desirable properties for carbon reduction allocation mechanisms.
But due to an impossibility result in mechanism design, DSIC, AE, and SBB can never be simultaneously achieved. Hence in this dissertation, we offer as contributions, two elegant solutions to this carbon emission reduction allocation problem. The first contribution is a mechanism which is DSIC and AE. We first propose a straightforward Vickrey-Clarke-Groves (VCG) mechanism based solution to the problem, leading to a DSIC and AE reverse auction protocol for allocating carbon reductions among the divisions. This solution, however, leads to a high level of budget imbalance. To reduce budget imbalance, we use redistribution mechanisms, without affecting the key properties of DSIC and AE. The Cavallo-Bailey redistribution mechanism, when applied to the above reverse auction protocol leads to reduced budget imbalance. To reduce the imbalance further, we propose an innovative forward auction protocol which achieves less imbalance when combined with the Cavallo-Bailey redistribution mechanism. The forward auction protocol also has the appealing feature of handsomely rewarding divisions that reduce emissions and levying appropriate penalties on divisions that do not participate in emission reductions.
The second contribution is a DSIC and SBB mechanism. Even though the first mechanism tries to reduce the budget imbalance, there is always a surplus which cannot be distributed among divisions and is wasted. So, in this part, by slightly compromising on efficiency, we propose a mechanism which is DSIC and SBB. The SBB property guarantees that there is no need for any monetary support from an external agency for implementing the mechanism and there is no leakage of revenue.2014-06-04T18:30:00Z