The Algorithm Design Of L1/L? Norm And Its Application Research

Metric learning based on norm definition becomes one of basic work for current machine learning and pattern recognition research.Typically,Euclidean distance or Mahalanobis distance based on L2 norm is the most popular one for pattern similarity measurement when constructing algorithms because of their differentiability and accordance with human intuition.Following L2 norm,the aforementioned algorithms mainly involving in two parts:one is SVM(Support Vector Machine)and its variants based on Euclidean distance,including traditional(SVM),Proximal Support Vector Machine via Generalized Eigenvalues(GEPSVM),etc.The other is based on Mahalanobis,including Large Margin Nearest Neighbor(LMNN),Maximin Margin Machine(M~4)and Minimax Probability Machine(MPM),etc.However,compared to non-L2 norm,there exists two inherited defeats in L2 norm and its derived algorithms.That is:1)non-robustness of L2 norm.In view of computation,the square root optimization method is usually replaced with L2 norm's square in solving the corresponding problems.Obviously,such replacement would further amplify the effect of noised data;2)difficulties in high-order optimization.Owing to such square operation,the leading problems need to be optimized at least at Quadratic Programing(QP).While for non-L2 norms,for instances,L1 norm or infinite norm,they are robust and the leading problems can be solved just by Linear Programing(LP).Unfortunately,it is well known for both L1 and infinite norm that they are non-differentiable and hard to solve.The reason is that their point-to-plane distances,one of the basic work in similarity,cannot be easily obtained just by SVM-like gradient methods,undoubtedly which is the limit to their applications.Here,we focus on those non-differentiable norm,and by the different utilization in supervision information,such as full supervision,unsupervised and semi-supervision,we discuss machine learning methods The major contributions of this dissertation are highlighted as follows:1.Infinite norm large margin classifier(InfSVM)is proposed.The classical gradient and sub-gradient methods is not suitable to the infinite norm's calculation since infinite norm is non-differentiable.From a dual norm standpoint,we derive the infinite norm point-to-plane distance and infinite norm's projection formula.Based on the infinite norm point-to-plane distance,we design an infinite norm large margin classifier(InfSVM).Its corresponding problem is can be solved by LP.InfSVM aims to reach better generalization by maximizing margin and simultaneously minimizing experience error.Compared with SVM,it has the following characteristics:1)it inherits the SVM's geometric interpretation;2)it has lower time complexity since the corresponding optimization problem is can be solved by LP;3)it is more robust than SVM;4)experiments on some artificial and benchmark datasets shows that its superiorities on test correctness.2.Unsupervised k-plane clustering based on L1 norm(L1kPC)is proposed.Different from classical k-plane clustering(kPC),its objective and constraint is measured by L1 norm rather than L2 norm.Compared to state-of-the-art methods,the advantages of L1kPC lie in 3-fold:1)similar to kPC,it has clear geometric interpretation;2)it is proved that the leading non-convex problem is equivalent to several convex sub-problems.Each sub-problem is can be solved by LP rather than QP,secular equation and a linear system of equations in other related plane clustering methods.To our best knowledge,it opens up a new way for L1 norm optimization;3)experiments on some artificial,benchmark UCI and human face datasets show its superiorities in robustness,training time and clustering accuracy.3.Semi-supervised plane clustering based on L1 norm(Semi-L1kPC)is proposed.Utilizing a few labeled and plenty of unlabeled samples and plane characteristics,based on previous works of 2,we design the foresaid algorithm.From only one labeled samples per class,the experimental comparisons on artificial and benchmark datasets show that:1)on exclusive XOR problem,the clustering accuracies of plane-prototype methods are higher than that of point-prototype ones;2)when introducing fewer supervised information,i.e.,labeled samples,Semi-kPC and Semi-L1kPC outperform the foresaid unsupervised methods in clustering accuracy;3)As for kPC itself,Semi-L1kPC receives more robust than Semi-kPC based on L2norm.4.According to the imbalanced forest fire detection's problem,L1 norm Biased SVM(L1BSVM)is proposed.Different from other traditional classification methods,in the early warning system of forest fire,it is expected to recognize the flame area in the image when the fire area is as small as possible.In addition,there is inevitably exists some noise in the forest fire data due to the process of data acquisition and transmission in the outdoor.According to the noisy and imbalanced forest fire data,utilizing multiple color space information,on the previous work of 1,we design the foresaid L1BSVM algorithm.The experimental results show that:1)its superiorities on training time and test correctness;2)when the ratio is up to 1:50,L1BSVM obtains the highest accuracy.