principal_curve.pptVIP

Learning and Design of Principal Curve Principal Curve f(f1(t),…,fd(t)) is a continuous curve in d-dimensional space decided by the parameter t. projection index : tf(x) denote the largest parameter value t for which the distance between x and f(t) is minimized. Principal Curve with Constraint Length Principal curves as continuous curves of a given length which minimize the expected squared distance between the curve and points of the space randomly chosen according to a given distribution. The expected squared distance between f and X Con’t The reason for the constraint length: for any X with a density and any ε0, there exists a curve f such that Δ(f)≤ε , thus a minimizing f has infinite length. Con’t Polygonal Curve Suppose that n independent copies X1,X2,…,Xn of X are given. the empirical squared error of f on the training data is Sk is the set of polygonal (piecewise linear) curves which have k segments and whose lengths do not exceed L. Con’t The difference between the expected squared loss of fk,n and the optimal expected squared loss of f* The Polygonal Line Algorithm The basic idea is to start with a straight line segment f0,n, the shortest segment of the first principal component line which contains all of the projected data points, and in each iteration of the algorithm, to increase the number of segments by one by adding a new vertex to the polygonal line f k,n produced in the previous iteration. After adding a new vertex, the positions of all vertices are updated in an inner loop. The inner loop consists of a projection step and an optimization step. The Projection Step In the projection step, the data points are partitioned into “nearest neighbor regions” according to which segment or vertex they project. The Vertex Optimization Step In the optimization step, the new position of a vertex vi is determined by minimizing an average squared distance criterion penalized by a measure of the local curvature, while all other v