图 书 馆
在非负最大堆上的投影Projection onto A Nonnegative Max-Heap |
|
| 课程网址: | http://videolectures.net/nips2011_ye_maxheap/ |
| 主讲教师: | Jieping Ye |
| 开课单位: | 密歇根大学 |
| 开课时间: | 2012-09-06 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | We consider the problem of computing the Euclidean projection of a vector of length $p$ onto a non-negative max-heap - an ordered tree where the values of the nodes are all nonnegative and the value of any parent node is no less than the value(s) of its child node(s). This Euclidean projection plays a building block role in the optimization problem with a non-negative max-heap constraint. Such a constraint is desirable when the features follow an ordered tree structure, that is, a given feature is selected for the given regression/classification task only if its parent node is selected. In this paper, we show that such Euclidean projection problem admits an analytical solution and we develop a top-down algorithm where the key operation is to find the so-called \emph{maximal root-tree} of the subtree rooted at each node. A naive approach for finding the maximal root-tree is to enumerate all the possible root-trees, which, however, does not scale well. We reveal several important properties of the maximal root-tree, based on which we design a bottom-up algorithm with merge for efficiently finding the maximal root-tree. The proposed algorithm has a (worst-case) linear time complexity for a sequential list, and $O(p^2)$ for a general tree. We report simulation results showing the effectiveness of the max-heap for regression with an ordered tree structure. Empirical results show that the proposed algorithm has an expected linear time complexity for many special cases including a sequential list, a full binary tree, and a tree with depth 1. |
| 关 键 词: | 欧几里得投影; 非负最大堆; 顺序列表 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-09-06：lxf |
| 阅读次数: | 60 |