On Robustness and Consistency of Support Vector Machines for non-i.i.d. Observations

Titelangaben

Strohriegl, Katharina:
On Robustness and Consistency of Support Vector Machines for non-i.i.d. Observations.
Bayreuth , 2018 . - IV, 147 S.
( Dissertation, 2018 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Abstract

In recent years it becomes more and more important to learn hidden and complex structures from a given data set in an automatic and efficient way. Here statistical machine learning and in particular support vector machines are located. A lot of theoretical work on machine learning has been done under the assumption that the observations are realisations of independent and identically distributed (i.i.d.) random variables. This assumption might be mathematically convenient but it is often violated in practice or at least a doubtful assumption. Recently some work has been done to generalize statistical machine learning theory to non-i.i.d. stochastic processes, which also is the topic of this thesis.
Throughout this work we examine statistical robustness and consistency of estimators, in particular of support vector machines, for data generating stochastic processes with different dependence structures.
To get reasonable results, we first introduce stochastic processes which provide convergence of their empirical measures to a limiting distribution. We call such processes weak respectively strong Varadarajan processes. Examples are many $\alpha$-mixing processes, many Markov chains, and several weakly dependent processes. Concerning qualitative robustness, we prove a generalization of Hampel's famous theorem to Varadarajan processes. Estimators which are continuous and can be represented by a statistical operator on the space of probability measures are qualitatively robust if the data generating stochastic process is a weak Varadarajan process. It is not even necessary to strengthen the assumptions on the estimator, compared to those in Hampel's theorem for the i.i.d. case.
Further, qualitative robustness of bootstrap approximations is a desirable property, as the true distribution of the estimator is unknown in all cases of practical importance and therefore often replaced by a bootstrap approximation. Dropping the assumption of identical distributions, we show that the bootstrap approximation is still qualitatively robust if the empirical bootstrap is used and if the assumptions on the input space are strengthened. Compared to the results of the i.i.d. case, we have the same assumptions on the estimators, but require the process to be a strong Varadarajan process. Assuming uniform continuity instead of continuity of the statistical operator and assuming the input space to be compact, we achieve qualitative robustness for some $\alpha$-mixing stochastic processes if the blockwise bootstrap is used.
Besides statistical robustness, consistency is of course also an important property of a sequence of estimators. Therefore the second part of this thesis focusses on consistency of support vector machines. We achieve consistency under common assumptions on the loss function and on the kernel. The stochastic process is assumed to be asymptotically mean stationary, which is implied by the Varadarajan property, and it is assumed to fulfil an almost sure convergence condition, similar to a law of large numbers. We show that many asymptotically mean stationary C-mixing, weakly dependent, and $\alpha$-mixing processes provide this assumption and therefore support vector machines are consistent for such processes. Compared to the i.i.d. case, our assumption on the convergence rate of the sequence of regularization parameters is only slightly stronger.

Abstract in weiterer Sprache

Heutzutage wird es immer wichtiger, versteckte und komplexe Strukturen in Datensätzen möglichst automatisch und effizient zu finden. Oft werden hierzu Methoden der maschinellen Lerntheorie, zum Beispiel Support Vector Machines, eingesetzt.
Die meisten theoretischen Ergebnisse zu Support Vector Machines sind allerdings für den Fall von unabhängig identisch verteilten (u.i.v.) stochastischen Prozessen hergeleitet. Dieser ist zwar mathematisch geeignet, in der Praxis ist die u.i.v.-Annahme aber häufig verletzt oder es ist unklar ob diese gilt. Deswegen versuchen wir zwei wichtige Eigenschaften von Schätzern, statistische Robustheit und Konsistenz, für datenerzeugende stochastische Prozesse zu zeigen, die nicht der u.i.v.-Annahme unterliegen. Dazu führen wir zunächst die sogenannten Varadarajan-Prozesse ein, diese garantieren Konvergenz ihres empirischen Maßes gegen eine Grenzverteilung. Beispiele für solche Prozesse sind einige $\alpha$-mixing-Prozesse, Markov-Ketten und schwach abhängige Prozesse. Angelehnt an das bekannte Theorem zur qualitativen Robustheit von Hampel betrachten wir Schätzer, die stetig sind und durch einen statistischen Operator auf dem Raum der Wahrscheinlichkeitsmaße repräsentiert werden können. Für solche Schätzer und schwache Varadarajan-Prozesse erhalten wir die qualitative Robustheit des Schätzers. Im Vergleich zu Hampels Theorem für den u.i.v.-Fall ändert sich nur die Voraussetzung an den stochastischen Prozess, die an die Schätzer bleibt gleich.
Zusätzlich ist die Verteilung der datenerzeugenden Prozesse oft unbekannt und wird mit Hilfe eines Bootstrap-Verfahrens angenähert. Auch hierfür ist qualitative Robustheit eine wünschenswerte Eigenschaft. Für den empirischen Bootstrap und stochastische Prozesse, die zwar unabhängig aber nicht identisch verteilt sind, erhalten wir qualitative Robustheit unter den gleichen Voraussetzungen an die Schätzer wie im u.i.v.-Fall, der stochastische Prozess muss die Varadarajan Eigenschaft besitzen und die Voraussetzungen an den zugrundeliegenden Datenraum muss verstärkt werden. Auch für einige $\alpha$-mixing-Prozesse zeigen wir qualitative Robustheit der Bootstrap-Approximation. Hierzu nehmen wir gleichmäßige Stetigkeit der Schätzer sowie einen kompakten Datenraum an. Die Approximation wird hierbei durch einen "Block-Bootstrap" erreicht, dieser eignet sich besser für abhängige Daten als der klassische empirische Bootstrap.
Neben der Robustheit ist auch Konsistenz eine zentrale Eigenschaft von Schätzern. Im zweiten Teil der Arbeit zeigen wir Konsistenz für Support Vector Machines. Zusätzlich zu den üblichen Voraussetzungen an den Kern und die Verlustfunktion, benötigen wir einen stochastischen Prozess, der asymptotisch mittelwertstationär ist. Diese Eigenschaft wird zum Beispiel durch die Varadarjan Eigenschaft impliziert. Weiterhin muss der Prozess eine Konvergenzbedingung, ähnlich dem starken Gesetz der großen Zahlen, erfüllen. Für solche Prozesse sind Support Vector Machines konsistent. Wir zeigen, dass einige schwach abhängige, $\alpha$- und C-mixing Prozesse diese Konvergenzbedingung erfüllen. Verglichen mit u.i.v. stochastischen Prozessen muss die Folge der Regularisierungsparameter nur unmerklich langsamer konvergieren, diese Voraussetzungen sind also fast identisch.