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

在这项研究中，我们提出了基于一种新的几何推理的“限定多面体逼近方法”，用于主动学习中的最大超球搜索。从理论和实践两方面对该方法的有效性进行了评价。我们还将该方法形式化为agent的行为模型，并通过实验验证了其有效性。首先，实现了边界多面体逼近法的算法。该算法由以下元素组成。1)从给定的初始设计点开始构建初始限定多面体，包括确定初始搜索方向、线搜索、多面体的构建以及构建失败的措施。2)利用问题的对偶性，在线性规划的基础上生成了边界多面体的最大超球。3)确定直线搜索的连续方向，该方向是基于边界多面体和超球中心的二叉搜索。其次，我们假设了算法中的各种运行成本，并对其进行了理论分析。分析结果表明，在对最大超球精度要求较高的情况下，该方法比传统的内嵌多面体逼近方法更有效。然后，我们在PC上实现我们的算法，并使用相对简单的区域对其进行评估。结果表明，当对最大超球的精度要求较高时，计算时间大大减少。最后，从主动学习的角度，我们将我们的方法形式化为一个代理的行为模型，代理通过对未知环境建模来完成他/她的任务。通过实验证明了其有效性，并通过讨论阐明了其优势和应用可能性。

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.