Margin Trees for Highdimensional Classification Tibshirani and Hastie 1 Errata confirmed by Tibshirani Section 2 a about the property of single link age M should be M0 Section 2 1 close to the last line of second pa ragraph at least should be at most The statements about complete single linkage are misleading In fact they use standard defi nition of complete single linkage except the di stance metric is replaced with margin betwee n pairwise classes I traced their code to confirm this 2 Targeted Problem Multi class class 2 High dimensional few samples features data linear separable already good accuracy need interpretable model Ex micro array data feature gene expression measurement class type of cancer Instances patients 3 Learn a Highly Interpretable Structure for Domain Experts x Check certain genes Sign T x 0 Help create the link of gene to cancer 4 Higher Interpretability Multi class problems reduce to binary 1vs1 voting not meaningful tree representation Non linear separable data single non linear classifier organized teams of linear classifiers Solution Margintree Hierarchical Tree max margin classifier Feature Selection interpretation minimize risk limited feature split 5 Using margin Tree Training 1 Construct tree structure 2 Train max margin classifier at each splitter 1 vs 2 3 2 vs 3 Testing 1 Start from root node 2 Going down following the prediction of classifiers at splitting points ex Right Right class 3 6 Tree Structure 1 2 Top down Construction Greedy 7 Greedy 1 3 1 2 3 1 Starting from root with all classes 1 2 3 2 find maximum margin among all partitions 1 vs 2 3 2 vs 1 3 3 vs 1 2 2n 1 partitions 8 Greedy 2 3 1 2 3 2 3 3 Repeat in child nodes 9 Greedy 2 3 1 2 3 2 3 4 Done Warning Greedy not necessary lead to global optimum i e find out the global maximal margin 10 Tree Structure 2 2 Bottom up Tree iteratively merge closest groups Single linkage distance nearest pair Complete linkage distance farthest pair 11 Complete Tree 12 Complete Tree Height subtree distance the farthest pair of classes Margin cutting through the subtree When looking for a Margin Height substree never break classes in the subtree 13 Efficient Greedy Tree Construction 1 Construct a complete linkage tree T 2 Estimate current lower bound of maximal marg in M0 max Margin individual class rest 3 To find a margin M0 We only need to consider partition between 5 4 6 1 2 3 M0 14 Comparable testing performances also 1vs1 voting Complete linkage tree more balance more interpretable 15 Recall the cutting plane Decision Sign T x 0 is the weight of features in decision function T x 0 0 16 Feature Selection Hard thresholding at each split Discard n features with low abs i by setting i 0 Proportional to margin n Margin chosen by cross validation error unavailable using non linear kernel Alternative methods L1 norm SVM force i to zero 17 T x 0 0 Setting i 0 Decision Sign T x 0 18 Feature Selection Result 19 Discussion Good for multi class high dimensional data Bad for non linear separable data Each node will contain impure data impure Testing performance comparable to traditional m ulti class max margin classifiers SVMs 20
View Full Document
Unlocking...