权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

高维区域最大超球面搜索的外接多面体近似

基本信息

批准号：
11680382
负责人：
SUZUKI Einoshin
金额：
$ 1.73万
依托单位：
Yokohama National University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1999
资助国家：
日本
起止时间：
1999 至 2000
项目状态：
已结题

项目摘要

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.

在本研究中，我们提出了一种新的几何推理的“外接多面体近似法”，用于主动学习中的最大超球搜索。从理论和实践的角度评价了该方法的有效性。我们还将该方法形式化为智能体的行为模型，并通过实验验证了其有效性。该算法由以下几部分组成：1）从给定的初始设计点出发构造初始外切多面体，包括初始搜索方向的确定、线搜索、多面体的构造和构造失败的度量; 2）生成外切多面体的最大超球面，其基于使用问题的对偶性的线性规划。3）确定线搜索的连续方向，其基于外切多面体和超球面的中心的二分搜索。接下来，我们在算法中假设了各种操作成本，并从理论上对其进行了分析。分析结果表明，当对最大超球面有较高精度要求时，该方法比传统的内接多面体逼近方法更有效。然后，在PC机上实现了该算法，并使用相对简单的区域对其进行了评价。结果表明，特别是当需要高精度的最大hypersphere.Finally，我们形式化我们的方法，从主动学习的角度来看，作为一个代理的行为模型，谁完成他/她的任务，通过建模一个未知的环境的计算时间减少。通过实验验证了该方法的有效性，并通过讨论阐明了该方法的优点和应用可能性。