Matrix Decomposition Methods for Data Mining : Computational Complexity and Algorithms

Matrix decompositions, where a given matrix is represented as a product of two other matrices, are regularly used in data mining. Most matrix decompositions have their roots in linear algebra, but the needs of data mining are not always those of linear algebra. In data mining one needs to have results that are interpretable -- and what is considered interpretable in data mining can be very different to what is considered interpretable in linear algebra. --- The purpose of this thesis is to study matrix decompositions that directly address the issue of interpretability. An example is a decomposition of binary matrices where the factor matrices are assumed to be binary and the matrix multiplication is Boolean. The restriction to binary factor matrices increases interpretability -- factor matrices are of the same type as the original matrix -- and allows the use of Boolean matrix multiplication, which is often more intuitive than normal matrix multiplication with binary matrices. Also several other decomposition methods are described, and the computational complexity of computing them is studied together with the hardness of approximating the related optimization problems. Based on these studies, algorithms for constructing the decompositions are proposed. Constructing the decompositions turns out to be computationally hard, and the proposed algorithms are mostly based on various heuristics. Nevertheless, the algorithms are shown to be capable of finding good results in empirical experiments conducted with both synthetic and real-world data.

Analytic Methods for the Logic of Proofs

The logic of proofs (lp) was proposed as Gdels missed link between Intuitionistic and S4-proofs, but so far the tableau-based methods proposed for lp have not explored this closeness with S4 and contain rules whose analycity is not immediately evident. We study possible formulations of analytic tableau proof methods for lp that preserve the subformula property. Two sound and complete tableau decision methods of increasing degree of analycity are proposed, KELP and preKELP. The latter is particularly inspired on S4-proofs. The crucial role of proof constants in the structure of lp-proofs methods is analysed. In particular, a method for the abduction of proof constant specifications in strongly analytic preKELP proofs is presented; abduction heuristics and the complexity of the method are discussed.

Identifying mechanisms of treatment effects and recovery in rehabilitation of schizophrenia: longitudinal analytic methods

The longitudinal dimension of schizophrenia and related severe mental illness is a key component of theoretical models of recovery. However, empirical longitudinal investigations have been underrepresented in the psychopathology of schizophrenia. Similarly, traditional approaches to longitudinal analysis of psychopathological data have had serious limitations. The utilization of modern longitudinal methods is necessary to capture the complexity of biopsychosocial models of treatment and recovery in schizophrenia. The present paper summarizes empirical data from traditional longitudinal research investigating recovery in symptoms, neurocognition, and social functioning. Studies conducted under treatment as usual conditions are compared to psychosocial intervention studies and potential treatment mechanisms of psychosocial interventions are discussed. Investigations of rehabilitation for schizophrenia using the longitudinal analytic strategies of growth curve and time series analysis are demonstrated. The respective advantages and disadvantages of these modern methods are highlighted. Their potential use for future research of treatment effects and recovery in schizophrenia is also discussed.

A study of matrix analysis methods for inelastic structures. Project no. 1467, Task no. 146701, prepared under Contract no. AF 33 (657)-8717 by Massachusetts Institute of Technology, Aeroelastic and Structures Research Laboratory.

Cover title.

Genetic algorithms for discovery of matrix multiplication methods

We present a parallel genetic algorithm for nding matrix multiplication algo-rithms. For 3 x 3 matrices our genetic algorithm successfully discovered algo-rithms requiring 23 multiplications, which are equivalent to the currently best known human-developed algorithms. We also studied the cases with less mul-tiplications and evaluated the suitability of the methods discovered. Although our evolutionary method did not reach the theoretical lower bound it led to an approximate solution for 22 multiplications.

Algorithmic Methods in Queues and in the Exploration of Point Processes

This is a review of methodology for the algorithmic study of some useful models in point process and queueing theory, as discussed in three lectures at the Summer Institute at Sozopol, Bulgaria. We provide references to sources where the extensive details of this work are found. For future investigation, some open problems and new methodological approaches are proposed.

Developing brownfields ranking models using decision analytic methods

The redevelopment of Brownfields has taken off in the 1990s, supported by federal and state incentives, and largely accomplished by local initiatives. Brownfields redevelopment has several associated benefits. These include the revitalization of inner-city neighborhoods, creation of jobs, stimulation of tax revenues, greater protection of public health and natural resources, the renewal and reuse existing civil infrastructure and Greenfields protection. While these benefits are numerous, the obstacles to Brownfields redevelopment are also very much alive. Redevelopment issues typically embrace a host of financial and legal liability concerns, technical and economic constraints, competing objectives, and uncertainties arising from inadequate site information. Because the resources for Brownfields redevelopment are usually limited, local programs will require creativity in addressing these existing obstacles in a manner that extends their limited resources for returning Brownfields to productive uses. Such programs may benefit from a structured and defensible decision framework to prioritize sites for redevelopment: one that incorporates the desired objectives, corresponding variables and uncertainties associated with Brownfields redevelopment. This thesis demonstrates the use of a decision analytic tool, Bayesian Influence Diagrams, and related decision analytic tools in developing quantitative decision models to evaluate and rank Brownfields sites on the basis of their redevelopment potential.

Queues with retrial/self-generation of priorities /postponement of work and some related reliability problems

Application of Queueing theory in areas like Computer networking, ATM facilities, Telecommunications and to many other numerous situation made people study Queueing models extensively and it has become an ever expanding branch of applied probability. The thesis discusses Reliability of a ‘k-out-of-n system’ where the server also attends external customers when there are no failed components (main customers), under a retrial policy, which can be explained in detail. It explains the reliability of a ‘K-out-of-n-system’ where the server also attends external customers and studies a multi-server infinite capacity Queueing system where each customer arrives as ordinary but can generate into priority customer which waiting in the queue. The study gives details on a finite capacity multi-server queueing system with self-generation of priority customers and also on a single server infinite capacity retrial Queue where the customer in the orbit can generate into a priority customer and leaves the system if the server is already busy with a priority generated customer; else he is taken for service immediately. Arrival process is according to a MAP and service times follow MSP.

Queueing Models with Vacations and Working Vacations

The thesis entitled “Queueing Models with Vacations and Working Vacations" consists of seven chapters including the introductory chapter. In chapters 2 to 7 we analyze different queueing models highlighting the role played by vacations and working vacations. The duration of vacation is exponentially distributed in all these models and multiple vacation policy is followed.In chapter 2 we discuss an M/M/2 queueing system with heterogeneous servers, one of which is always available while the other goes on vacation in the absence of customers waiting for service. Conditional stochastic decomposition of queue length is derived. An illustrative example is provided to study the effect of the input parameters on the system performance measures. Chapter 3 considers a similar setup as chapter 2. The model is analyzed in essentially the same way as in chapter 2 and a numerical example is provided to bring out the qualitative nature of the model. The MAP is a tractable class of point process which is in general nonrenewal. In spite of its versatility it is highly tractable as well. Phase type distributions are ideally suited for applying matrix analytic methods. In all the remaining chapters we assume the arrival process to be MAP and service process to be phase type. In chapter 4 we consider a MAP/PH/1 queue with working vacations. At a departure epoch, the server finding the system empty, takes a vacation. A customer arriving during a vacation will be served but at a lower rate.Chapter 5 discusses a MAP/PH/1 retrial queueing system with working vacations.In chapter 6 the setup of the model is similar to that of chapter 5. The signicant dierence in this model is that there is a nite buer for arrivals.Chapter 7 considers an MMAP(2)/PH/1 queueing model with a nite retrial group

Discrete Time Inventory Models with/without Positive Service Time

In everyday life different flows of customers to avail some service facility or other at some service station are experienced. In some of these situations, congestion of items arriving for service, because an item cannot be serviced Immediately on arrival, is unavoidable. A queuing system can be described as customers arriving for service, waiting for service if it is not immediate, and if having waited for service, leaving the system after being served. Examples Include shoppers waiting in front of checkout stands in a supermarket, Programs waiting to be processed by a digital computer, ships in the harbor Waiting to be unloaded, persons waiting at railway booking office etc. A queuing system is specified completely by the following characteristics: input or arrival pattern, service pattern, number of service channels, System capacity, queue discipline and number of service stages. The ultimate objective of solving queuing models is to determine the characteristics that measure the performance of the system

Investigations on Stochastic Storage Systems with Positive Service Time

In this thesis the queueing-inventory models considered are analyzed as continuous time Markov chains in which we use the tools such as matrix analytic methods. We obtain the steady-state distributions of various queueing-inventory models in product form under the assumption that no customer joins the system when the inventory level is zero. This is despite the strong correlation between the number of customers joining the system and the inventory level during lead time. The resulting quasi-birth-anddeath (QBD) processes are solved explicitly by matrix geometric methods

Queueing Models with Vacations and Working Vacations

The objective of the study of \Queueing models with vacations and working vacations" was two fold; to minimize the server idle time and improve the e ciency of the service system. Keeping this in mind we considered queueing models in di erent set up in this thesis. Chapter 1 introduced the concepts and techniques used in the thesis and also provided a summary of the work done. In chapter 2 we considered an M=M=2 queueing model, where one of the two heterogeneous servers takes multiple vacations. We studied the performance of the system with the help of busy period analysis and computation of mean waiting time of a customer in the stationary regime. Conditional stochastic decomposition of queue length was derived. To improve the e ciency of this system we came up with a modi ed model in chapter 3. In this model the vacationing server attends the customers, during vacation at a slower service rate. Chapter 4 analyzed a working vacation queueing model in a more general set up. The introduction of N policy makes this MAP=PH=1 model di erent from all working vacation models available in the literature. A detailed analysis of performance of the model was provided with the help of computation of measures such as mean waiting time of a customer who gets service in normal mode and vacation mode.

On Queues with Interruption and Protection

Cochin University Of Science And Technology