The analysis of sequential data is important in business, science, and engineering, for tasks such as signal processing, user behavior mining, and commercial transactions analysis. In this dissertation, we build upon the Collective Dynamical Modeling and Clustering (CDMC) framework for discrete time series modeling, by making contributions to clustering initialization, dynamical modeling, and scaling. We first propose a modified Dynamic Time Warping (DTW) approach for clustering initialization within CDMC. The proposed approach provides DTW metrics that penalize deviations of the warping path from the path of constant slope. This reduces over-warping, while retaining the efficiency advantages of global constraint approaches, and without relying on domain dependent constraints. Second, we investigate the use of semi-Markov chains as dynamical models of temporal sequences in which state changes occur infrequently. Semi-Markov chains allow explicitly specifying the distribution of state visit durations. This makes them superior to traditional Markov chains, which implicitly assume an exponential state duration distribution. Third, we consider convergence properties of the CDMC framework. We establish convergence by viewing CDMC from an Expectation Maximization (EM) perspective. We investigate the effect on the time to convergence of our efficient DTW-based initialization technique and selected dynamical models. We also explore the convergence implications of various stopping criteria. Fourth, we consider scaling up CDMC to process big data, using Storm, an open source distributed real-time computation system that supports batch and distributed data processing. We performed experimental evaluation on human sleep data and on user web navigation data. Our results demonstrate the superiority of the strategies introduced in this dissertation over state-of-the-art techniques in terms of modeling quality and efficiency.

Intelligent agents are designed to interact with, and learn about, their environment so that they can act purposefully towards a goal. One class of problems encountered in building such agents is learning how to respond to dynamic systems with a continuous state space. The goals of this dissertation are to develop a framework for understanding the behaviour of partitioned dynamic systems with continuous underlying state and to translate this framework into algorithms which adaptively form a partition of the continuous space such that the partitioned system is more easily learned and controlled, and such that the control law may be easily explained in intuitive ways. Currently, algorithms which learn a control policy for partitioned continuous state space systems treat the partitioned system as an approximation to a Markov chain. I give conditions for the partitioned system to be a Markov chain, a semi-Markov process and a new class of system, a weak-semi-Markov process. The weak-semi-Markov model is shown to model partitioned dynamic systems with greater economy than other surveyed models. The behaviour of a partitioned state space system in the area around the region boundaries is also considered. I use the theory of sliding surfaces, and some heuristic arguments to recommend region boundary shape and position. The concept of 'staying on the boundary' then becomes a robust and relatively easy subgoal within the control algorithm. The concept of 'reaching the sliding surface' as a subgoal is used as the basis for an intuitive explanation of the learnt controller. I present an algorithm based on this concept which explains the behaviour of a learnt controller in ways not previously available to a machine learning algorithms. Finally, the Markov Property and the theory of Sliding Mode Control are used as the basis of a class of recursive algorithms. These algorithms adaptively find a partition, and simultaneously use this partition in conjunction with one of five reinforcement learning algorithms to find a control policy based on that partition. This technique is shown to work very well in learning, controlling and explaining a variety of physical systems, from a monorail to a container crane.

<p>I denna avhandling studerar vi nödvändiga och tillräckliga villkor för svag konvergens av första-sällan-händelsetider för semi-Markovska processer.</p><p>I introduktionen ger vi nödvändiga grundläggande definitioner och beskrivningar av modeller som betraktas i avhandlingen, samt ger några exempel på situationer i vilka metoder av första-sällan-händelsetider kan vara lämpliga att använda. Dessutom analyserar vi publicerade resultat om asymptotiska problem för stokastiska funktionaler som definieras på semi-Markovska processer.</p><p>I artikel A betraktar vi första-sällan-händelsetider för semi-Markovska processer med en ändlig mängd av lägen. Vi ger också en sammanfattning av våra resultat om nödvändiga och tillräckliga villkor för svag konvergens, samt diskuterar möjliga tillämpningar inom aktuarie-området.</p><p>I artikel B redovisar vi i detalj de resultat som annonseras i artikel A och bevisen för dem. Vi ger också nödvändiga och tillräckliga villkor för svag konvergens av första-sällan-händelsetider för semi-Markovska processer med en ändlig mängd av lägen i ett icke-triangulärt tillstånd. Dessutom beskriver vi med hjälp av Laplacetransformationen klassen av alla möjliga gränsfördelningar.</p><p>I artikel C studerar vi villkor av svag konvergens av flöden av sällan-händelser i ett icke-triangulärt tillstånd. Vi formulerar nödvändiga och tillräckliga villkor för konvergens, och beskriver klassen av alla möjliga gränsflöden. Vi tillämpar också våra resultat i asymptotisk analys av icke-ruin-sannolikheten för störda riskprocesser.</p><p>I artikel D ger vi nödvändiga och tillräckliga villkor för svag konvergens av första-sällan-händelsetider för semi-Markovska rocesser med en ändlig mängd av lägen i ett triangulärt tillstånd, samt beskriver klassen av alla möjliga gränsfördelningar. Resultaten utvidgar slutsatser från artikel B till att gälla för ett allmänt triangulärt tillstånd.</p><p>I artikel E ger vi nödvändiga och tillräckliga villkor för svag konvergens av flöden av sällan-händelser för semi-Markovska processer i ett triangulärt tillstånd. Detta generaliserar resultaten från artikel C till att beskriva ett allmänt triangulärt tillstånd. Vidare ger vi tillämpningar av våra resultat på asymptotiska problem av störda riskprocesser och till kösystemen med snabb service.</p> / <p>In this thesis we study necessary and sufficient conditions for weak convergence of first-rare-event times for semi-Markov processes, we describe the class of all possible limit distributions, and give the applications of the results to risk theory and queueing systems.</p><p>In paper <b>A</b>, we consider first-rare-event times for semi-Markov processes with a finite set of states, and give a summary of our results concerning necessary and sufficient conditions for weak convergence of first-rare-event times and their actuarial applications.</p><p>In paper <b>B</b>, we present in detail results announced in paper <b>A</b> as well as their proofs. We give necessary and sufficient conditions for weak convergence of first-rare-event times for semi-Markov processes with a finite set of states in non-triangular-array mode and describe the class of all possible limit distributions in terms of their Laplace transforms.</p><p>In paper <b>C</b>, we study the conditions for weak convergence for flows of rare events for semi-Markov processes with a finite set of states in non-triangular array mode. We formulate necessary and sufficient conditions of convergence and describe the class of all possible limit stochastic flows. In the second part of the paper, we apply our results to the asymptotical analysis of non-ruin probabilities for perturbed risk processes.</p><p>In paper <b>D</b>, we give necessary and sufficient conditions for the weak convergence of first-rare-event times for semi-Markov processes with a finite set of states in triangular array mode as well as describing the class of all possible limit distributions. The results of paper <b>D</b> extend results obtained in paper <b>B</b> to a general triangular array mode.</p><p>In paper <b>E</b>, we give the necessary and sufficient conditions for weak convergence for the flows of rare events for semi-Markov processes with a finite set of states in triangular array case. This paper generalizes results obtained in paper <b>C</b> to a general triangular array mode. In the second part of the paper, we present applications of our results to asymptotical problems of perturbed risk processes and to queueing systems with quick service</p>

Commercial video game developers constantly strive to create intelligent humanoid characters that are controlled by computers. To ensure computer opponents are challenging to human players, these characters are often allowed to cheat. Although they appear skillful at playing video games, cheating characters may not behave in a human-like manner and can contribute to a lack of player enjoyment if caught. This work investigates the problem of predicting opponent positions in the video game Counter-Strike: Source without cheating. Prediction models are machine-learned from records of past matches and are informed only by game information available to a human player. Results show that the best models estimate opponent positions with similar or better accuracy than human experts. Moreover, the mistakes these models make are closer to human predictions than actual opponent locations perturbed by a corresponding amount of Gaussian noise.

I denna avhandling studerar vi nödvändiga och tillräckliga villkor för svag konvergens av första-sällan-händelsetider för semi-Markovska processer. I introduktionen ger vi nödvändiga grundläggande definitioner och beskrivningar av modeller som betraktas i avhandlingen, samt ger några exempel på situationer i vilka metoder av första-sällan-händelsetider kan vara lämpliga att använda. Dessutom analyserar vi publicerade resultat om asymptotiska problem för stokastiska funktionaler som definieras på semi-Markovska processer. I artikel A betraktar vi första-sällan-händelsetider för semi-Markovska processer med en ändlig mängd av lägen. Vi ger också en sammanfattning av våra resultat om nödvändiga och tillräckliga villkor för svag konvergens, samt diskuterar möjliga tillämpningar inom aktuarie-området. I artikel B redovisar vi i detalj de resultat som annonseras i artikel A och bevisen för dem. Vi ger också nödvändiga och tillräckliga villkor för svag konvergens av första-sällan-händelsetider för semi-Markovska processer med en ändlig mängd av lägen i ett icke-triangulärt tillstånd. Dessutom beskriver vi med hjälp av Laplacetransformationen klassen av alla möjliga gränsfördelningar. I artikel C studerar vi villkor av svag konvergens av flöden av sällan-händelser i ett icke-triangulärt tillstånd. Vi formulerar nödvändiga och tillräckliga villkor för konvergens, och beskriver klassen av alla möjliga gränsflöden. Vi tillämpar också våra resultat i asymptotisk analys av icke-ruin-sannolikheten för störda riskprocesser. I artikel D ger vi nödvändiga och tillräckliga villkor för svag konvergens av första-sällan-händelsetider för semi-Markovska rocesser med en ändlig mängd av lägen i ett triangulärt tillstånd, samt beskriver klassen av alla möjliga gränsfördelningar. Resultaten utvidgar slutsatser från artikel B till att gälla för ett allmänt triangulärt tillstånd. I artikel E ger vi nödvändiga och tillräckliga villkor för svag konvergens av flöden av sällan-händelser för semi-Markovska processer i ett triangulärt tillstånd. Detta generaliserar resultaten från artikel C till att beskriva ett allmänt triangulärt tillstånd. Vidare ger vi tillämpningar av våra resultat på asymptotiska problem av störda riskprocesser och till kösystemen med snabb service. / In this thesis we study necessary and sufficient conditions for weak convergence of first-rare-event times for semi-Markov processes, we describe the class of all possible limit distributions, and give the applications of the results to risk theory and queueing systems. In paper <b>A</b>, we consider first-rare-event times for semi-Markov processes with a finite set of states, and give a summary of our results concerning necessary and sufficient conditions for weak convergence of first-rare-event times and their actuarial applications. In paper <b>B</b>, we present in detail results announced in paper <b>A</b> as well as their proofs. We give necessary and sufficient conditions for weak convergence of first-rare-event times for semi-Markov processes with a finite set of states in non-triangular-array mode and describe the class of all possible limit distributions in terms of their Laplace transforms. In paper <b>C</b>, we study the conditions for weak convergence for flows of rare events for semi-Markov processes with a finite set of states in non-triangular array mode. We formulate necessary and sufficient conditions of convergence and describe the class of all possible limit stochastic flows. In the second part of the paper, we apply our results to the asymptotical analysis of non-ruin probabilities for perturbed risk processes. In paper <b>D</b>, we give necessary and sufficient conditions for the weak convergence of first-rare-event times for semi-Markov processes with a finite set of states in triangular array mode as well as describing the class of all possible limit distributions. The results of paper <b>D</b> extend results obtained in paper <b>B</b> to a general triangular array mode. In paper <b>E</b>, we give the necessary and sufficient conditions for weak convergence for the flows of rare events for semi-Markov processes with a finite set of states in triangular array case. This paper generalizes results obtained in paper <b>C</b> to a general triangular array mode. In the second part of the paper, we present applications of our results to asymptotical problems of perturbed risk processes and to queueing systems with quick service

The probabilistic safety assessment of engineering systems involving high-consequence low-probability events is stochastic in nature due to uncertainties inherent in time to an event. The event could be a failure, repair, maintenance or degradation associated with system ageing. Accurate reliability prediction accounting for these uncertainties is a precursor to considerably good risk assessment model. Stochastic Markov reliability models have been constructed to quantify basic events in a static fault tree analysis as part of the safety assessment process. The models assume that a system transits through various states and that the time spent in a state is statistically random. The system failure probability estimates of these models assuming constant transition rate are extensively utilized in the industry to obtain failure frequency of catastrophic events. An example is core damage frequency in a nuclear power plant where the initiating event is loss of cooling system. However, the assumption of constant state transition rates for analysis of safety critical systems is debatable due to the fact that these rates do not properly account for variability in the time to an event. An ill-consequence of such an assumption is conservative reliability prediction leading to addition of unnecessary redundancies in modified versions of prototype designs, excess spare inventory and an expensive maintenance policy with shorter maintenance intervals. The reason for this discrepancy is that a constant transition rate is always associated with an exponential distribution for the time spent in a state. The subject matter of this thesis is to develop sophisticated mathematical models to improve predictive capabilities that accurately represent reliability of an engineering system. The generalization of the Markov process called the semi-Markov process is a well known stochastic process, yet it is not well explored in the reliability analysis of nuclear power plant systems. The continuous-time, discrete-state semi-Markov process model is a stochastic process model that describes the state transitions through a system of integral equations which can be solved using the trapezoidal rule. The primary objective is to determine the probability of being in each state. This process model ensures that time spent in the states can be represented by a suitable non-exponential distribution thus capturing the variability in the time to event. When exponential distribution is assumed for all the state transitions, the model reduces to the standard Markov model. This thesis illustrates the proposed concepts using basic examples and then develops advanced case studies for nuclear cooling systems, piping systems, digital instrumentation and control (I&C) systems, fire modelling and system maintenance. The first case study on nuclear component cooling water system (NCCW) shows that the proposed technique can be used to solve a fault tree involving redundant repairable components to yield initiating event probability quantifying the loss of cooling system. The time-to-failure of the pump train is assumed to be a Weibull distribution and the resulting system failure probability is validated using a Monte Carlo simulation of the corresponding reliability block diagram. Nuclear piping systems develop flaws, leaks and ruptures due to various underlying damage mechanisms. This thesis presents a general model for evaluating rupture frequencies of such repairable piping systems. The proposed model is able to incorporate the effect of aging related degradation of piping systems. Time dependent rupture frequencies are computed and the influence of inspection intervals on the piping rupture probability is investigated. There is an increasing interest worldwide in the installation of digital instrumentation and control systems in nuclear power plants. The main feedwater valve (MFV) controller system is used for regulating the water level in a steam generator. An existing Markov model in the literature is extended to a semi-Markov model to accurately predict the controller system reliability. The proposed model considers variability in the time to output from the computer to the controller with intrinsic software and mechanical failures. State-of-the-art time-to-flashover fire models used in the nuclear industry are either based on conservative analytical equations or computationally intensive simulation models. The proposed semi-Markov based case study describes an innovative fire growth model that allows prediction of fire development and containment including time to flashover. The model considers variability in time when transiting from one stage of the fire to the other. The proposed model is a reusable framework that can be of importance to product design engineers and fire safety regulators. Operational unavailability is at risk of being over-estimated because of assuming a constant degradation rate in a slowly ageing system. In the last case study, it is justified that variability in time to degradation has a remarkable effect on the choice of an effective maintenance policy. The proposed model is able to accurately predict the optimal maintenance interval assuming a non-exponential time to degradation. Further, the model reduces to a binary state Markov model equivalent to a classic probabilistic risk assessment model if the degradation and maintenance states are eliminated. In summary, variability in time to an event is not properly captured in existing Markov type reliability models though they are stochastic and account for uncertainties. The proposed semi-Markov process models are easy to implement, faster than intensive simulations and accurately model the reliability of engineering systems.

Zugl.: Duisburg, Essen, Univ., Diss., 2009

No description available.

The probabilistic safety assessment of engineering systems involving high-consequence low-probability events is stochastic in nature due to uncertainties inherent in time to an event. The event could be a failure, repair, maintenance or degradation associated with system ageing. Accurate reliability prediction accounting for these uncertainties is a precursor to considerably good risk assessment model. Stochastic Markov reliability models have been constructed to quantify basic events in a static fault tree analysis as part of the safety assessment process. The models assume that a system transits through various states and that the time spent in a state is statistically random. The system failure probability estimates of these models assuming constant transition rate are extensively utilized in the industry to obtain failure frequency of catastrophic events. An example is core damage frequency in a nuclear power plant where the initiating event is loss of cooling system. However, the assumption of constant state transition rates for analysis of safety critical systems is debatable due to the fact that these rates do not properly account for variability in the time to an event. An ill-consequence of such an assumption is conservative reliability prediction leading to addition of unnecessary redundancies in modified versions of prototype designs, excess spare inventory and an expensive maintenance policy with shorter maintenance intervals. The reason for this discrepancy is that a constant transition rate is always associated with an exponential distribution for the time spent in a state. The subject matter of this thesis is to develop sophisticated mathematical models to improve predictive capabilities that accurately represent reliability of an engineering system. The generalization of the Markov process called the semi-Markov process is a well known stochastic process, yet it is not well explored in the reliability analysis of nuclear power plant systems. The continuous-time, discrete-state semi-Markov process model is a stochastic process model that describes the state transitions through a system of integral equations which can be solved using the trapezoidal rule. The primary objective is to determine the probability of being in each state. This process model ensures that time spent in the states can be represented by a suitable non-exponential distribution thus capturing the variability in the time to event. When exponential distribution is assumed for all the state transitions, the model reduces to the standard Markov model. This thesis illustrates the proposed concepts using basic examples and then develops advanced case studies for nuclear cooling systems, piping systems, digital instrumentation and control (I&C) systems, fire modelling and system maintenance. The first case study on nuclear component cooling water system (NCCW) shows that the proposed technique can be used to solve a fault tree involving redundant repairable components to yield initiating event probability quantifying the loss of cooling system. The time-to-failure of the pump train is assumed to be a Weibull distribution and the resulting system failure probability is validated using a Monte Carlo simulation of the corresponding reliability block diagram. Nuclear piping systems develop flaws, leaks and ruptures due to various underlying damage mechanisms. This thesis presents a general model for evaluating rupture frequencies of such repairable piping systems. The proposed model is able to incorporate the effect of aging related degradation of piping systems. Time dependent rupture frequencies are computed and the influence of inspection intervals on the piping rupture probability is investigated. There is an increasing interest worldwide in the installation of digital instrumentation and control systems in nuclear power plants. The main feedwater valve (MFV) controller system is used for regulating the water level in a steam generator. An existing Markov model in the literature is extended to a semi-Markov model to accurately predict the controller system reliability. The proposed model considers variability in the time to output from the computer to the controller with intrinsic software and mechanical failures. State-of-the-art time-to-flashover fire models used in the nuclear industry are either based on conservative analytical equations or computationally intensive simulation models. The proposed semi-Markov based case study describes an innovative fire growth model that allows prediction of fire development and containment including time to flashover. The model considers variability in time when transiting from one stage of the fire to the other. The proposed model is a reusable framework that can be of importance to product design engineers and fire safety regulators. Operational unavailability is at risk of being over-estimated because of assuming a constant degradation rate in a slowly ageing system. In the last case study, it is justified that variability in time to degradation has a remarkable effect on the choice of an effective maintenance policy. The proposed model is able to accurately predict the optimal maintenance interval assuming a non-exponential time to degradation. Further, the model reduces to a binary state Markov model equivalent to a classic probabilistic risk assessment model if the degradation and maintenance states are eliminated. In summary, variability in time to an event is not properly captured in existing Markov type reliability models though they are stochastic and account for uncertainties. The proposed semi-Markov process models are easy to implement, faster than intensive simulations and accurately model the reliability of engineering systems.

Freiburg i. Br., Univ., Diss., 2005.