Elastic principal manifoldsand--论文代写范文精选

该算法被实现为独立的一部分数据,在网络上可用。我们描述的应用程序的方法,并提供几个例子和速度性能特征。这种直觉概念,对应于人类的大脑泛化能力,得到了一个数学概念的自洽性。在数据集的情况下只有一个或零数据点。下面的essay代写范文进行详述。

Abstract 
Principal manifolds defined as lines or surfaces passing through “the middle” of the data distribution serve as useful objects for many practical applications. We propose a new algorithm for fast construction of grid approximations of principal manifolds with given topology. One advantage of the method is a new form of the functional to be minimized, which becomes quadratic at the step of the vertexes positions refinement. This makes the algorithm very effective, especially for parallel implementations. Another advantage is that the same algorithmic kernel is applied to construct principal manifolds of different dimensions and topologies. We demonstrate how flexibility of the approach allows easily numerous adaptive strategies like principal graph constructing, etc. The algorithm is implemented as a C++ package elmap and as a part of stand-alone data visualization tool VidaExpert, available on the web. We describe the approach and provide several examples of it’s applications with speed performance characteristics.

Introduction 
Principal manifolds were introduced by Hastie and Stueltze in 1989 as lines or surfaces passing through “the middle” of the data distribution [Hastie and Stuetzle, 1989]. This intuitive notion, corresponding to the human brain generalization ability, was supported by a mathematical notion of self-consistency: every point of the principal manifold is a conditional mean of all points that are projected into this point. In the case of datasets only one or zero data points are projected in a typical point of the principal manifold, thus, one has to introduce smoothers that become an essential part of the principal manifolds construction algorithms. 

Since the pioneer work of Hastie, many modifications and alternative definitions of the principal manifolds appeared in the literature. Theoretically, existence of self-consistent principal manifold is not guaranteed for any probability distribution, and because of this many alternative definitions were introduced (see, for example, [Kégl, 1999]), allowing constructing principal curves (manifolds), given that the distribution of points has several finite first moments. The idea of using elastic energy functional for principal manifolds construction in the context of neural networks methodology was proposed in [Gorban and Rossiev, 1999]. This idea was developed and tested on practical applications in [Gorban, Zinovyev, 2000, 2001, 2002; Zinovyev, 2000; Zinovyev, Pitenko and Popova, 2002]. A computationally effective and robust algorithmic kernel for principal curves construction, called Polygonal algorithm, was proposed in [Kégl et al., 1999]. Also a variant of strategy for constructing principal graphs was formulated in [Kégl and Krzyzak, 2002] in the context of the skeletonization of hand-written digits. Another interesting approach we would like to mention is constructing principal manifold in a piece-wise manner by fitting unconnected line segments [Verbeek et al., 2000].

Outline of the method 
Lets define elastic net as a connected unordered graph G(Y,E), where Y = {y (i), i=1..p} denotes collection of graph nodes, and E={E(i) , i=1..s} is the collection of graph edges. Let’s combine some of the incident edges in pairs R(i) = {E(i) ,E(k) } and denote by R={R(i) , i=1..r} the collection of elementary ribs. Every edge E(i) has the beginning node E(i) (0) and the ending node E(i) (1). Elementary rib is a pair of incident edges. It has beginning node R(i) (1), ending node R(i) (2) and the central node R(i) (0) (see Fig. 1). 

Introducing edges is simply introducing connectivity on the graph; this connectivity defines a topology of principal manifold to be constructed, as well as it’s dimension. Ribs together with edges are used to define smoothness penalty function, in such a way defining a “natural” form of the graph. Figure 2 illustrates some examples of the graphs practically used. The first is a simple polyline, the second is planar rectangular grid, third is planar hexagonal grid, forth – non-planar graph with nodes arranged on sphere (spherical grid), then a 3D cubical grid, torus and hemisphere. Elementary ribs at these graphs are incident edges touching with a blunt angle.

Discussion 
We introduced a new algorithmic kernel for calculating grid approximations for principal manifolds of different topologies and dimensions. The main advantages of the method are speed and good performance. The optimization criterion we formulated has particular simple form and natural physical interpretation. Together with usual mean square node-to-point distance term our minimized functional contains two penalizing terms: U(E) and U(R) , both quadratic with respect to the grid nodes positions. As one can see from (3) and (4) they are similar to the sum of squared grid approximations of the first and second derivatives, in the directions, guided by natural choice of ribs 2 . 

The U(E) term penalizes the total length (or square, volume) of the principal manifold and, indirectly, makes the grid regular by penalizing non-equidistant distribution of nodes along the grid. The U(R) term is a smoothening factor, chosen to be quadratic instead of using cosine function as in the algorithm of Kégl [Kégl et. al, 1999]. Good characteristics of the method such as its universality, speed and inherited parallelism open new fields to the applications of principal manifolds, especially for the analysis of huge datasets with hundreds of thousands of points with dimensionality of order of hundreds. The algorithm we described with its C++ implementation provide a way to construct a principal manifolds for these datasets approximated by number of nodes of order of 10000 in a reasonable time. In applications of principal manifolds to 3D-surfaces modeling, one can find similar “physicsbased” new methods in surface modeling in computer graphics (see, for example [Mandal, Qin and Vemuri, 2000; Xie and Qin, 2002]). The ideology of constructing the elastic energy functional considered here can be compared with approach described in [Xie and Qin, 2002]. Our functional contains only restricted subset of elastic energies proposed there; we utilize such a “physics-based” model, which allows quadratic description, thus leads to quadratic optimization problem. In this way we significantly speed-up the optimization step. One important application of principal manifolds is dimension reduction and data visualization. In this field they compete with multidimensional scaling methods and recently introduced advanced algorithms of dimension reduction, such as locally linear embedding (LLE) [Roweis and Saul, 2000] and ISOMAP [Tenenbaum, de Silva and Langford, 2000] algorithms. The difference between two approaches is that the later ones seek for new point coordinates directly and do not use any intermediate geometrical objects. This has several advantages, the main are that a) there is a unique solution for the problem (the methods are not iterative in their nature, there is no problem of grid initialization) and b) there is no problem of choosing a good way to project points onto non-linear manifold. Another advantage is that the methods are not limited by several first dimensions in dimension reduction (it is difficult in practice to manipulate with non-linear manifolds of dimension more than three). 

Using principal manifold as a non-linear low-dimensional screen to project data on it gives other benefits. First, the manifold approximates data and can be used itself, without applying projection, to visualize different functions defined in data space (for example, density estimation). Also the manifold as an intermediate, “fixing” the structure of learning dataset, can be used in visualization of data points that were not used in the learning process, for example, for visualization of dataflow “on the fly”. Constructing manifolds does not use point-to-point distance matrix that is particularly useful for large datasets. Also using principal manifolds is expected to be more robust to additive noise than the methods based on the local properties of point-to-point distances. To conclude this short comparison, LLE and ISOMAP methods are more suitable if the low-dimensional structure in multidimensional data space is complicated but is expected to exist, and the data points are situated rather tightly on it. Principal manifolds are more applicable for visualization of real-life noisy observations, appearing in economics, biology, medicine and other sciences, and for constructing data screens showing not only the data but different related functions defined in data space.（essay代写)

51Due网站原创范文除特殊说明外一切图文著作权归51Due所有；未经51Due官方授权谢绝任何用途转载或刊发于媒体。如发生侵犯著作权现象，51Due保留一切法律追诉权。（essay代写)
更多essay代写范文欢迎访问我们主页 www.51due.com 当然有essay代写需求可以和我们24小时在线客服 QQ:800020041 联系交流。-X（essay代写)