Circumscribed-Polyhedron Approximation for Maximum-Hypersphere-Search in High-Dimensional Region

点击翻译按钮获取中文摘要

In this research, we proposed "circumscribed-polyhedron approximation method", which is based on a novel geometric reasoning, for maximum-hypersphere-search in active learning. The effectiveness of the method was evaluated from theoretical and practical points of view. We also formalized the method as a behavior model of an agent and demonstrated its effectiveness by experiments.First, we realized the algorithm of circumscribed-polyhedron approximation method. The algorithm consists of the following elements.1) Construction of an initial circumscribed polyhedron from a given initial design point, which consists of determination of initial search direction, line search, construction of a polyhedron, and measures for failures of the construction.2) Generation of a maximum hypersphere of the circumscribed polyhedron, which is based on a linear programming using the duality of the problem.3) Determination of the successive direction of line search, which is based on binary search of the circumscribed polyhedron and the center of the hypersphere.Next, we assumed various operational costs in the algorithm and analyzed it theoretically. Results of the analysis show that the proposed method is, when high precision is required for the maximum hypersphere, more efficient than the conventional method, inscribed-polyhedron approximation.Then, we implemented our algorithm on a PC, and evaluated it using relatively simple regions. The results show high reduction of computational time especially when high precision is required for the maximum hypersphere.Finally, we formalized our method, from the point of view of active learning, as a behavior model of an agent, who accomplishes his/her task by modeling an unknown environment. We demonstrated its effectiveness through experiments, and clarified its advantages and application possibilities through discussions.