Seit 1983 begründet die Publikationsreihe "Graph Minors" von N. Robertson und P.D. Seymour im Wesentlichen die Minorentheorie mit mächtigen Hilfsmitteln wie der Baumzerlegung und weitreichenden Resultaten wie dem Minorensatz. Für gerichtete Graphen existiert allerdings noch keine einheitliche Minorentheorie und verschiedene Ansätze werden in dieser Arbeit systematisiert. Einige gerichtete Versionen der Baumzerlegung (gerichtete Baumzerlegung nach B. Reed, arboreale, D- und DAG-Zerlegung) werden unter einheitlichen Aspekten untersucht. Die D-Weite ist dabei besonders vielversprechend. Enge Verbindungen zu zwei gerichteten Räuber-und-Gendarmen-Spielen werden unter analogen Aspekten betrachtet und sind wichtige Hilfsmittel. Der zentrale Begriff des Minoren ist im Wesentlichen für ungerichtete Graphen definiert und eine gerichtete Version wirft einige Probleme auf, welche untersucht werden. In \"Directed Tree-Width\" schlugen T. Johnson, N. Robertson, P.D. Seymour und R. Thomas 2001 einen Kompromiss vor. Durch Einschränkung der möglichen Kontraktionen soll der gewonnen Minorenbegriff mit einigen fundamentalen Anforderungen vereinbar sein und trotzdem ein mächtiges Werkzeug darstellen. Dieser Ansatz wird mit einer Anforderungsliste systematisch verfolgt und schrittweise Einschränkungen betrachtet. Die gerichtete Version topologischer Minoren ist dabei besonders vielversprechend. Die Minorentheorie gerichteter Graphen wird auf reduzible Flussgraphen angewandt. Wesentliche Resultate sind Konstruktionen arborealer und D-Zerlegungen mit Weite <2, sowie Gegenbeispiele für die Beschränktheit der DAG-Weite. Analoge Resultate folgen für die jeweiligen gerichteten Räuber-und-Gendarmen-Spiele.

Seit 1983 begründet die Publikationsreihe "Graph Minors" von N. Robertson und P.D. Seymour im Wesentlichen die Minorentheorie mit mächtigen Hilfsmitteln wie der Baumzerlegung und weitreichenden Resultaten wie dem Minorensatz. Für gerichtete Graphen existiert allerdings noch keine einheitliche Minorentheorie und verschiedene Ansätze werden in dieser Arbeit systematisiert. Einige gerichtete Versionen der Baumzerlegung (gerichtete Baumzerlegung nach B. Reed, arboreale, D- und DAG-Zerlegung) werden unter einheitlichen Aspekten untersucht. Die D-Weite ist dabei besonders vielversprechend. Enge Verbindungen zu zwei gerichteten Räuber-und-Gendarmen-Spielen werden unter analogen Aspekten betrachtet und sind wichtige Hilfsmittel. Der zentrale Begriff des Minoren ist im Wesentlichen für ungerichtete Graphen definiert und eine gerichtete Version wirft einige Probleme auf, welche untersucht werden. In \"Directed Tree-Width\" schlugen T. Johnson, N. Robertson, P.D. Seymour und R. Thomas 2001 einen Kompromiss vor. Durch Einschränkung der möglichen Kontraktionen soll der gewonnen Minorenbegriff mit einigen fundamentalen Anforderungen vereinbar sein und trotzdem ein mächtiges Werkzeug darstellen. Dieser Ansatz wird mit einer Anforderungsliste systematisch verfolgt und schrittweise Einschränkungen betrachtet. Die gerichtete Version topologischer Minoren ist dabei besonders vielversprechend. Die Minorentheorie gerichteter Graphen wird auf reduzible Flussgraphen angewandt. Wesentliche Resultate sind Konstruktionen arborealer und D-Zerlegungen mit Weite <2, sowie Gegenbeispiele für die Beschränktheit der DAG-Weite. Analoge Resultate folgen für die jeweiligen gerichteten Räuber-und-Gendarmen-Spiele.:1 Einleitung 1.1 Grundbegriffe der Graphentheorie 1.2 Reduzibilität 2 Über Minoren von Graphen 2.1 Minoren von Graphen 2.2 Topologische Minoren von Graphen 2.3 Baumzerlegung und Baumweite tw(G) 2.4 Wegzerlegung und Wegbreite pw(G) 2.5 Räuber-und-Gendarmen-Spiele auf Graphen 2.6 Resultate und Anwendungen 3 Über Minoren von Digraphen 3.1 Übertragung der Minorenrelation auf Digraphen 3.2 Hindernisse bei der De?nition einer gerichteten Baumweite 3.3 Arboreale Weite dtw(D) 3.3.1 Arboreale Weite und Räuber-und-Gendarmen-Spiele 3.3.2 Resultate und Anwendungen 3.4 Gerichtete Baumweite dtwR(D) 3.5 D-Weite dw(D) 3.6 DAG-Weite dgw(D) 3.6.1 DAG-Weite und Räuber-und-Gendarmen-Spiele 3.6.2 Resultate und Anwendungen 3.7 Räuber-und-Gendarmen-Spiele auf Digraphen 3.8 Eingeschränkte Minorenrelation für Digraphen 3.8.1 Die Teilgraphenrelation für Digraphen 3.8.2 Die topologische Minorenrelation für Digraphen 3.8.3 Die Minorenrelation auf Digraphen nach JRST 3.8.4 Eingeschränkte Minorenrelationen 4 Verbindungen zwischen Reduzibilität und Minoren von Digraphen 4.1 Reduzibilität und initiale Wurzeldigraphen 4.2 Charakterisierung der Reduzibilität durch eingeschränkte Minoren 4.3 Resultate der Minorentheorie für reduzible initiale Wurzeldigraphen 5 Zusammenfassung und Ausblick Literaturverzeichnis Abbildungsverzeichnis

給定兩個隨機變數的條件機率矩陣A和B，相容性問題的主要課題包 含：(一)如何判斷他們是否相容？若相容，則如何檢驗聯合分配的唯一性 或找出所有的聯合分配；(二)若不相容，則如何訂定測量不相容程度的方 法並找出最近似聯合分配。目前的文獻資料有幾種解決問題的途徑，例 如Arnold and Press (1989)的比值矩陣法、Song et al. (2010)的不可約 化對角塊狀矩陣法及Arnold et al. (2002)的數學規劃法等，經由這些方法 的啟發，本文發展出創新的特徵向量法來處理前述的相容性課題。 當A和B相容時，我們觀察到邊際分配分別是AB′和B′A對應特徵值1的 特徵向量。因此，在以邊際分配檢驗相容性時，特徵向量法僅需檢驗滿足 特徵向量條件的邊際分配，大幅度減少了檢驗的工作量。利用線性代數中 的Perron定理和不可約化對角塊狀矩陣的概念，特徵向量法可圓滿處理相 容性問題(一)的部份。 當A和B不相容時，特徵向量法也可衍生出一個測量不相容程度的簡單 方法。由於不同的測量方法可得到不同的最近似聯合分配，為了比較其優 劣，本文中提出了以條件分配的偏差加上邊際分配的偏差作為評量最近似 聯合分配的標準。特徵向量法除了可推導出最近似聯合分配的公式解外， 經過例子的驗證，在此評量標準下特徵向量法也獲得比其他測量法更佳的 最近似聯合分配。由是，特徵向量法也可用在處理相容性問題(二)的部份。 最後，將特徵向量法實際應用在兩人零和有限賽局問題上。作業研究的 解法是將雙方採取何種策略視為獨立，但是我們認為雙方可利用償付值表 所提供的資訊作為決策的依據，並將雙方的策略寫成兩個條件機率矩陣， 則賽局問題被轉換為相容性問題。我們可用廣義相容的概念對賽局的解進 行分析，並在各種測度下討論賽局的解及雙方的最佳策略。 / Given two conditional probability matrices A and B of two random variables, the issues of the compatibility include: (a) how to determine whether they are compatible? If compatible, how to check the uniqueness of the joint distribution or find all possible joint distributions; (b) if incompatible, how to measure how far they are from compatibility and find the most nearly compatible joint distribution. There are several approaches to solve these problems, such as the ratio matrix method(Arnold and Press, 1989), the IBD matrix method(Song et al., 2010) and the mathematical programming method(Arnold et al., 2002). Inspired by these methods, the thesis develops the eigenvector approach to deal with the compatibility issues. When A and B are compatible, it is observed that the marginal distributions are eigenvectors of AB′ and B′A corresponding to 1, respectively. While checking compatibility by the marginal distributions, the eigenvector approach only checks the marginal distributions which are eigenvectors of AB′ and B′A. It significantly reduces the workload. By using Perron theorem and the concept of the IBD matrix, the part (a) of compatibility issues can be dealt with the eigenvector approach. When A and B are incompatible, a simple way to measure the degree of incompatibility can be derived from the eigenvector approach. In order to compare the most nearly compatible joint distributions given by different measures, the thesis proposes the deviation of the conditional distributions plus the deviation of the marginal distributions as the most nearly compatible joint distribution assessment standard. The eigenvector approach not only derives formula for the most nearly compatible distribution, but also provides better joint distribution than those given by the other measures through the validations under this standard. The part (b) of compatibility issues can also be dealt with the eigenvector approach. Finally, the eigenvector approach is used in solving game problems. In operations research, strategies adopted by both players are assumed to be independent. However, this independent assumption may not be appropriate, since both players can make decisions through the information provided by the payoffs for the game. Let strategies of both players form two conditional probability matrices, then the game problems can be converted into compatibility issues. We can use the concept of generalized compatibility to analyze game solutions and discuss the best strategies for both players in a variety of measurements.

<p dir="ltr">The generalization error of a classifier is related to the complexity of the set of functions among which the classifier is chosen. We study a family of low-complexity classifiers consisting of thresholding a random one-dimensional feature. The feature is obtained by projecting the data on a random line after embedding it into a higher-dimensional space parametrized by monomials of order up to k. More specifically, the extended data is projected n-times and the best classifier among those n, based on its performance on training data, is chosen. </p><p dir="ltr">We show that this type of classifier is extremely flexible, as it is likely to approximate, to an arbitrary precision, any continuous function on a compact set as well as any Boolean function on a compact set that splits the support into measurable subsets. In particular, given full knowledge of the class conditional densities, the error of these low-complexity classifiers would converge to the optimal (Bayes) error as k and n go to infinity. On the other hand, if only a training dataset is given, we show that the classifiers will perfectly classify all the training points as k and n go to infinity. </p><p dir="ltr">We also bound the generalization error of our random classifiers. In general, our bounds are better than those for any classifier with VC dimension greater than O(ln(n)). In particular, our bounds imply that, unless the number of projections n is extremely large, there is a significant advantageous gap between the generalization error of the random projection approach and that of a linear classifier in the extended space. Asymptotically, as the number of samples approaches infinity, the gap persists for any such n. Thus, there is a potentially large gain in generalization properties by selecting parameters at random, rather than optimization. </p><p dir="ltr">Given a classification problem and a family of classifiers, the Rashomon ratio measures the proportion of classifiers that yield less than a given loss. Previous work has explored the advantage of a large Rashomon ratio in the case of a finite family of classifiers. Here we consider the more general case of an infinite family. We show that a large Rashomon ratio guarantees that choosing the classifier with the best empirical accuracy among a random subset of the family, which is likely to improve generalizability, will not increase the empirical loss too much. </p><p dir="ltr">We quantify the Rashomon ratio in two examples involving infinite classifier families in order to illustrate situations in which it is large. In the first example, we estimate the Rashomon ratio of the classification of normally distributed classes using an affine classifier. In the second, we obtain a lower bound for the Rashomon ratio of a classification problem with a modified Gram matrix when the classifier family consists of two-layer ReLU neural networks. In general, we show that the Rashomon ratio can be estimated using a training dataset along with random samples from the classifier family and we provide guarantees that such an estimation is close to the true value of the Rashomon ratio.</p>