The anomaly detection task is to recognize the presence of an unusual (and potentially hazardous) state within the behaviors or activities of a computer user, system, or network with respect to some model of normal behavior which may be either hard-coded or learned from observation. An anomaly detection agent faces many learning problems including learning from streams of temporal data, learning from instances of a single class, and adaptation to a dynamically changing concept. The domain is complicated by considerations of the trusted insider problem (recognizing the difference between innocuous and malicious behavior changes on the part of a trusted user). This study introduces the anomaly detection in web applications and formulates it as a machine learning task on temporal sequence data. In this study the goal is to develop a model or profile of normal working state of web application user and to detect anomalous conditions as deviations from the expected behavior patterns. We focus, here, on learning models of normality at the user behavioral level, as observed through a web application. In this study we introduce some sensors intended to function as a focus of attention unit at the lowest level of a classification hierarchy using Finite State Markov Chains and Hidden Markov Models and discuss the success of these sensors.

The fields of statistical physics, discrete probability, combinatorics, and theoretical computer science have converged around efforts to understand random structures and algorithms. Recent activity in the interface of these fields has enabled tremendous breakthroughs in each domain and has supplied a new set of techniques for researchers approaching related problems. This thesis makes progress on several problems in this interface whose solutions all build on insights from multiple disciplinary perspectives. First, we consider a dynamic growth process arising in the context of DNA-based self-assembly. The assembly process can be modeled as a simple Markov chain. We prove that the chain is rapidly mixing for large enough bias in regions of Z^d. The proof uses a geometric distance function and a variant of path coupling in order to handle distances that can be exponentially large. We also provide the first results in the case of fluctuating bias, where the bias can vary depending on the location of the tile, which arises in the nanotechnology application. Moreover, we use intuition from statistical physics to construct a choice of the biases for which the Markov chain M_mon requires exponential time to converge. Second, we consider a related problem regarding the convergence rate of biased permutations that arises in the context of self-organizing lists. The Markov chain M_nn in this case is a nearest-neighbor chain that allows adjacent transpositions, and the rate of these exchanges is governed by various input parameters. It was conjectured that the chain is always rapidly mixing when the inversion probabilities are positively biased, i.e., we put nearest neighbor pair x<y in order with bias 1/2 <= p_{xy} <= 1 and out of order with bias 1-p_{xy}. The Markov chain M_mon was known to have connections to a simplified version of this biased card-shuffling. We provide new connections between M_nn and M_mon by using simple combinatorial bijections, and we prove that M_nn is always rapidly mixing for two general classes of positively biased {p_{xy}}. More significantly, we also prove that the general conjecture is false by exhibiting values for the p_{xy}, with 1/2 <= p_{xy} <= 1 for all x< y, but for which the transposition chain will require exponential time to converge. Finally, we consider a model of colloids, which are binary mixtures of molecules with one type of molecule suspended in another. It is believed that at low density typical configurations will be well-mixed throughout, while at high density they will separate into clusters. This clustering has proved elusive to verify, since all local sampling algorithms are known to be inefficient at high density, and in fact a new nonlocal algorithm was recently shown to require exponential time in some cases. We characterize the high and low density phases for a general family of discrete {it interfering binary mixtures} by showing that they exhibit a "clustering property' at high density and not at low density. The clustering property states that there will be a region that has very high area, very small perimeter, and high density of one type of molecule. Special cases of interfering binary mixtures include the Ising model at fixed magnetization and independent sets.

No description available.

Vad karaktäriserar en kristall? Svaret på denna till synes enkla fråga blir kanske att det är en anordning av atomer uppradade i periodiska mönster. Så ordnade strukturer kan studeras genom att det uppträder så kallade Braggtoppar i röntgendiffraktionsmönstret. Om frågan gäller elektrontäthetsfördelningen, kanske svaret blir att denna är periodisk och grundar sig på elektronvågor som genomtränger hela kristallen. I och med att nya typer av ordnade system, så kallade kvasikristaller, upptäcks och framställs på artificiell väg blir svaren på dessa frågor mer intrikata. En kristall behöver inte bestå av enheter upprepade periodiskt i rummet, och den klassiska metoden att karaktärisera strukturer via röntgendiffraktionsmönstret kanske inte alls är den allena saliggörande. I denna avhandling visas att ett ordnat gitter vars röntgendiffraktionsmönster saknar inre struktur, dvs är av samma diffusa typ som vad ett oordnat material uppvisar, fortfarande kan ha elektronerna utsträckta över hela strukturen. Detta implicerar att det inte finns något enkelt samband mellan diffraktionsmönstret från gittret och dess fysikaliska egenskaper såsom t ex lokalisering av vågfunktionerna. Man talar om lokalisering när en vågfunktion är begränsad inom en del av materialet och inte utsträckt över hela dess längd, vilket är av betydelse när man vill avgöra huruvida ett material är en isolator, halvledare eller ledare. Det vittnar samtidigt om behovet av att söka efter andra karakteristika när man försöker beskriva skillnaden mellan ett ordnat och ett oordnat material, där den senare kategorin kan uppvisa lokalisering. Resultaten utgör en klassificering av det svåröverskådliga området aperiodiska gitter i en dimension. Det leder till hypotesen att ideala kvasikristaller, genererade med bestämda regler, har kontinuerligt energispektrum av fraktal natur. I reella material spelar korrelation en viktig roll. Vid icke-linjär återkoppling till gittret kan man erhålla intrinsiskt lokaliserade vågor, som i många avseenden beter sig som partiklar, solitoner, vilka har visat sig ha viktiga tillämpningar inom bl a optisk telekommunikation. Sådana vågors roll for lagring och transport av energi har undersökts i teoretiska modeller for optiska vågledare och kristaller där ljuset har en förmåga att manipulera sig självt. / Spectral and dynamical properties of electrons, phonons, electromagnetic waves, and nonlinear coherent excitations in one-dimensional modulated structures with long-range correlations are investigated from a theoretical point of view. First a proof of singular continuous electron spectrum for the tight-binding Schrödinger equation with an on-site potential, which, in analogy with a random potential, has an absolutely continuous correlation measure, is given. The critical behavior of such a localization phenomenon manifests in anomalous diffusion for the time-evolution of electronic wave packets. Spectral characterization of elastic vibrations in aperiodically ordered diatomic chains in the harmonic approximation is achieved through a dynamical system induced by the trace maps of renormalized transfer matrices. These results suggest that the zero Lebesgue measure Cantor-set spectrum (without eigenvalues) of the Fibonacci model for a quasicrystal is generic for deterministic aperiodic superlattices, for which the modulations take values via substitution rules on finite sets, independent of the correlation measure. Secondly, a method to synthesize and analyze discrete systems with prescribed long-range correlated disorder based on the conditional probability function of an additive Markov chain is effectively implemented. Complex gratings (artificial solids) that simultaneously display given characteristics of quasiperiodic crystals and amorphous solids on the Fraunhofer diffraction are designated. A mobility edge within second order perturbation theory of the tight-binding Schrödinger equation with a correlated disorder in the dichotomic potential realizes the success of the method in designing window filters with specific spectral components. The phenomenon of self-localization in lattice dynamical systems is a subject of interest in various physical disciplines. Lattice solitons are studied using the discrete nonlinear Schrödinger equation with on-site potential, modeling coherent structures in, for example, photonic crystals. The instability-induced dynamics of the localized gap soliton is found to thermalize according to the Gibbsian equilibrium distribution, while the spontaneous formation of persisting intrinsic localized modes from the extended out-gap soliton reveals a phase transition of the solution.

Powder mixing is an essential operation in various industrial fields, such as pharmaceuticals, agro-food, cements, etc. Continuous powder mixing, as an alternative to conventional batch mixing, has attracted a lot of interest mainly due to its capacity in handling high volume manufacturing. This work aims at the contribution to the implementation of process control applications for powder mixing in a pilot-scale continuous mixer. Prior to developing process control strategies, new developments have been presented for better understanding continuous mixing of two components. Hold-up weight and relative hold-up weight distribution of each component in the whole mixer have been experimentally investigated under different operating conditions. An improved Markov chain model has been finally presented to predict the mean concentration of the mixtures obtained at the mixer's outlet. The implementation of a proportional-integral-derivative (PID) controller has been experimentally performed as an initial attempt to real-time control the homogeneity of the mixture produced. The rotational speed of the stirrer, identified as an important deciding factor towards the mixer's efficiency, has been considered as the manipulated variable. The closed-loop control is based on either the mean concentration or the relative standard deviation. The performances of the proposed closed-loops have been evaluated for continuous mixing subjected to step changes in feed rates of the mixer. Four case studies have been defined and presented. The main challenge in the process control system is the tuning of PID parameters. The performance of closed-loop control of either the mean concentration or the relative standard deviation has been compared to open-loop operation.

Hierarchical Markovian Models (HMMs) are composed of multiple low level models (LLMs) and high level model (HLM) that defines the interaction among LLMs. The essence of the HMM approach is to model the system at hand in the form of interacting components so that its (larger) underlying continous-time Markov chain (CTMC) is not generated but implicitly represented as a sum of Kronecker products of (smaller) component matrices. The Kronecker structure of an HMM induces nested block partitionings in its underlying CTMC. These partitionings may be used in block versions of classical iterative methods based on splittings, such as block SOR (BSOR), to solve the underlying CTMC for its stationary vector. Therein the problem becomes that of solving multiple nonsingular linear systems whose coefficient matrices are the diagonal blocks of a particular partitioning. This paper shows that in each HLM state there may be diagonal blocks with identical off-diagonal parts and diagonals differing from each other by a multiple of the identity matrix. Such diagonal blocks are named candidate blocks. The paper explains how candidate blocks can be detected and how the can mutually benefit from a single real Schur factorization. It gives sufficient conditions for the existence of diagonal blocks with real eigenvalues and shows how these conditions can be checked using component matrices. It describes how the sparse real Schur factors of candidate blocks satisfying these conditions can be constructed from component matrices and their real Schur factors. It also demonstrates how fill in- of LU factorized (non-candidate) diagonal blocks can be reduced by using the column approximate minimum degree algorithm (COLAMD). Then it presents a three-level BSOR solver in which the diagonal blocks at the first level are solved using block Gauss-Seidel (BGS) at the second and the methods of real Schur and LU factorizations at the third level. Finally, on a set of numerical experiments it shows how these ideas can be used to reduce the storage required by the factors of the diagonal blocks at the third level and to improve the solution time compared to an all LU factorization implementation of the three-level BSOR solver.

Kronecker structured representations are used to cope with the state space explosion problem in Markovian modeling and analysis. Currently an open research problem is that of devising strong preconditioners to be used with projection methods for the computation of the stationary vector of Markov chains (MCs) underlying such representations. This paper proposes a block SOR (BSOR) preconditioner for hierarchical Markovian Models (HMMs) that are composed of multiple low level models and a high level model that defines the interaction among low level models. The Kronecker structure of an HMM yields nested block partitionings in its underlying continuous-time MC which may be used in the BSOR preconditioner. The computation of the BSOR preconditioned residual in each iteration of a preconditioned projection method becoms the problem of solving multiple nonsingular linear systems whose coefficient matrices are the diagonal blocks of the chosen partitioning. The proposed BSOR preconditioner solvers these systems using sparse LU or real Schur factors of diagonal blocks. The fill-in of sparse LU factorized diagonal blocks is reduced using the column approximate minimum degree algorithm (COLAMD). A set of numerical experiments are presented to show the merits of the proposed BSOR preconditioner.

Orientador: Ali Messaoudi / Banca: Vanderlei Minori Horita / Banca: Daniel Smania Brandão / Banca: Christian Mauduit / Banca: Glauco Valle da Silva Coelho / Resumo: Em 2000, Killeen e Taylor definiram a máquina de somar estocástica em base 2. Eles mostraram que o espectro do op erador de transi cão (agindo em l∞( N)), associado a essa máquina, e igual ao conjunto de Julia cheio de uma função quadrática. Nesse trabalho, estudamos outras propriedades espectrais e topológicass da máquina de Killeen e Taylor, e também das suas extensões à l∞(Z) e a outras bases não constantes. Esse estudo envolve conjuntos de Julia de funções quadráticas e também conjuntos de Julia cheios de endomor smos de C2 . Finalmente estudamos algumas propriedades aritméticas e topológicas de uma classe de fractais de Rauzy. Em particular estudamos o azulejamento periódico do plano complexo C induzido por eles. / Abstract: In 2000, Killeen and Taylor de ned the sto hastic adding machine in base 2. They proved that the sp ectrum of the transition op erator (acting in l∞(N )) asso ciated to this machine is equal to the lled Julia set of a quadratic polynomial map. In this work, we study other sp ectral and top ological prop erties of Killeen and Taylor machine, and also of its extensions to l∞( Z) and to other non constant bases. This study envolves Julia sets of quadratic maps and also lled Julia sets of endomorphisms of C2 . Finally we study some arithmetical and topological prop erties of a class of Rauzy fractals. In particular we study the p erio dictiling of complex plane C induced by this class. / Doutor

[pt] O objetivo desta dissertação é apresentar algumas técnicas e ferramentas para a obtenção de cotas superiores e inferiores para tempos de mistura de cadeias de Markov. Para que isso se torne mais interessante, apresentaremos estes conceitos através de cadeias de Markov que atuam sobre o grupo simétrico, que podem ser vistas como embaralhamentos de cartas. Ademais, usaremos um destes embaralhamentos como toy model para o processo de exclusão simples simétrico, o que nos ajudará a determinar os tempos de mistura do embaralhamento e do famoso sistema de partículas. / [en] The aim of this dissertation is to introduce some techniques and tools to obtain upper and lower bounds for Markov chains mixing times. To make it more interesting, we introduce these concepts through Markov chains that act on the symmetric group, which can be seen as card shuffles. Furthermore, we use one of these shuffles as a toy model for the symmetric simple exclusion process, which helps us to determine mixing times for the shuffle and for the famous particle system.

La transition démographique bouleverse les équilibres de population du monde. Si la croissance des populations a été soulignée par les démographes durant la seconde moitié du XXe siècle, le vieillissement est également une conséquence de ce changement de régime démographique. Néanmoins, les études démographiques et géoprospectives ne sont pas si nombreuses sur le sujet. Il semble pertinent de dépasser les cadres nationaux pour adopter une échelle infranationale pour comprendre les évolutions observées. Nous étudions ici le futur du vieillissement démographique des sociétés méditerranéennes dans sa dimension dynamique. La Méditerranée constitue un laboratoire intéressant pour l'étude du vieillissement : on y trouve une grande pluralité de situations démographiques. Les enjeux de cette étude dépassent son cadre thématique : pour la mener à bien, plusieurs défis méthodologiques ont dû être relevés. Des données démographiques aux échelles infranationales, issues de sources nombreuses et disparates, ont été collectées et harmonisées pour l'ensemble de l'espace méditerranéen. Elles ont servi à établir des scénarios prospectifs et des projections pour les 50 années à venir. Il a fallu adapter des méthodes issues d'autres disciplines pour mesurer le processus de convergence, et même en proposer de nouvelles. La thèse met en avant la diversité des convergences à l’œuvre dans le vieillissement des populations méditerranéennes. Les différents scénarios analysés décrivent tous une convergence globale des vieillissements mais rappellent aussi que l’hétérogénéité observée dans la répartition spatiale du phénomène devrait perdurer encore longtemps et pourrait se renforcer localement. / The demographic transition upsets population balances worldwide. If population growth has been studied by demographers throughout the second half of the 20th century, ageing is an equally significant consequence of this demographic change. Nevertheless, studies demographic and geoprospective are not so many. In order to understand the observed changes, it seems appropriate to look beyond national borders for choose the level of sub-national territories. We study the future of Mediterranean societies' ageing in its dynamic dimension. The Mediterranean is an interesting laboratory because we found a great plurality of situations. To reach our goal, several challenges had to be overcome regarding the collection of data, their harmonization, their projection and analysis. For the whole Mediterranean area, we have collected and harmonized geo-demographic data to sub-national scales from many disparate sources. They were then used to establish future scenarios and projections for the next 50 years. Finally, we had to adapt methods from other disciplines (especially econometrics) to establish convergence of measures. We even propose news methods to answer our questions. The Ph.D. highlights the diversity of convergence proccess involved in the ageing populations of the Mediterranean. Territorial convergence and spatial convergence are taking part in the approximation of the regions' characteristics in terms of ageing. All the different scenarios analyzed describe future that highlight the global convergence of ageing but also remind that the observed heterogeneity in the spatial distribution of the phenomenon should last a long time and could strengthen locally.