000254938 001__ 254938
000254938 005__ 20190619041448.0
000254938 0247_ $$2doi$$a10.5075/epfl-thesis-7718
000254938 037__ $$aTHESIS
000254938 041__ $$aeng
000254938 088__ $$a7718
000254938 245__ $$aLow-rank tensor methods for large Markov chains and forward feature selection methods
000254938 260__ $$c2018$$bEPFL$$aLausanne
000254938 269__ $$a2018
000254938 300__ $$a0
000254938 336__ $$aTheses
000254938 502__ $$aProf. Victor Panaretos (président) ; Prof. Daniel Kressner, Prof. António Manuel Pacheco Pires (directeurs) ; Dr Carlos  Alves, Dr Paula Milheiro-Oliveira, Dr Nelson Antunes (rapporteurs)
000254938 500__ $$aCo-supervision with: Instituto Superior Técnico (IST) da Universidade de Lisboa, Doutoramento em Estatistica e Processos Estocásticos
000254938 520__ $$aIn the first part of this thesis, we present and compare several approaches for the determination of the steady-state of large-scale Markov chains with an underlying low-rank tensor structure. Such structure is, in our context of interest, associated with the existence of interacting processes. The state space grows exponentially with the number of processes. This type of problems arises, for instance, in queueing theory, in chemical reaction networks, or in telecommunications. 

As the number of degrees of freedom of the problem grows exponentially with the number of processes, the so-called \textit{curse of dimensionality} severely impairs the use of standard methods for the numerical analysis of such Markov chains. We drastically reduce the number of degrees of freedom by assuming a low-rank tensor structure of the solution.

We develop different approaches, all considering a formulation of the problem where all involved structures are considered in their low-rank representations in \textit{tensor train} format. 

The first approaches that we will consider are associated with iterative solvers, in particular focusing on solving a minimization problem that is equivalent to the original problem of finding the desired steady state. We later also consider tensorized multigrid techniques as main solvers, using different operators for restriction and interpolation. For instance, aggregation/disaggregation operators, which have been extensively used in this field, are applied. 

In the second part of this thesis, we focus on methods for feature selection. More concretely, since, among the various classes of methods, sequential feature selection methods based on mutual information have become very popular and are widely used in practice, we focus on this particular type of methods. This type of problems arises, for instance, in microarray analysis, in clinical prediction, or in text categorization.

Comparative evaluations of these methods have been limited by being based on specific datasets and classifiers. We develop a theoretical framework that allows evaluating the methods based on their theoretical properties. Our framework is based on the properties of the target objective function that the methods try to approximate, and on a novel categorization of features, according to their contribution to the explanation of the class; we derive upper and lower bounds for the target objective function and relate these bounds with the feature types. Then, we characterize the types of approximations made by the methods, and analyse how these approximations cope with the good properties of the target objective function.

We also develop a distributional setting designed to illustrate the various deficiencies of the methods, and provide several examples of wrong feature selections. In the context of this setting, we use the minimum Bayes risk as performance measure of the methods.
000254938 6531_ $$aMarkov chains
000254938 6531_ $$acurse of dimensionality
000254938 6531_ $$alow-rank structure
000254938 6531_ $$atensor train format
000254938 6531_ $$aentropy
000254938 6531_ $$amutual information
000254938 6531_ $$aforward feature selection methods
000254938 6531_ $$aperformance measure
000254938 6531_ $$aminimum Bayes risk
000254938 700__ $$0246806$$aSantos Paredes Quartin de Macedo, Francisco$$g228856
000254938 720_2 $$g213191$$edir.$$aKressner, Daniel
000254938 720_2 $$g231144$$edir.$$aPacheco Pires, António Manuel
000254938 8564_ $$uhttps://infoscience.epfl.ch/record/254938/files/EPFL_TH7718.pdf$$s1012347
000254938 8564_ $$uhttps://infoscience.epfl.ch/record/254938/files/EPFL_TH7718.gif?subformat=icon$$s8016$$xicon
000254938 8564_ $$uhttps://infoscience.epfl.ch/record/254938/files/EPFL_TH7718.jpg?subformat=icon-180$$s10322$$xicon-180
000254938 8564_ $$uhttps://infoscience.epfl.ch/record/254938/files/EPFL_TH7718.jpg?subformat=icon-700$$s58439$$xicon-700
000254938 8564_ $$uhttps://infoscience.epfl.ch/record/254938/files/EPFL_TH7718.pdf?subformat=pdfa$$s2895336$$xpdfa
000254938 909C0 $$pANCHP
000254938 909CO $$pthesis$$pthesis-public$$pDOI$$pSB$$ooai:infoscience.epfl.ch:254938$$qGLOBAL_SET$$qDOI2
000254938 918__ $$aSB$$cMATHICSE$$dEDMA
000254938 919__ $$aANCHP
000254938 920__ $$a2018-01-08$$b2018
000254938 970__ $$a7718/THESES
000254938 973__ $$sPUBLISHED$$aEPFL
000254938 980__ $$aTHESIS