Computational principal on how parts and wholes cooperate and conflict

从计算理论的角度研究了部分与整体如何合作与冲突的计算原理。在本项目所取得的成果中，我们认为以下是重要的：1。本文的主要工作如下：1.利用G-熵，设计了一种高效的Boosting算法，该算法采用自顶向下的决策树学习算法，其分裂准则基于G-熵。通过引入每个选项的风险有多高的信息，在最坏情况下的在线框架中的一组选项之间的动态分配资源的问题进行了研究。我们将聚集算法应用于该问题，并给出了一个严格的性能界.我们提出了三种随机投影的方法，随机映射数据表示为向量到一个低维空间，使利润率近似保留。我们的算法比基于Johnson-Lindenstrauss引理的随机投影算法更有效.我们推导出一个超多项式下界的大小的布尔电路，计算团函数与 *（loglog n）否定门。证明了在所有公平函数中，单变量函数f（x）= xj与多数函数的相关性最小，其中布尔函数f与g的相关性定义为1- 2 Pr [f（x）<$g（x）]，若Pr[f（x）=1]=1 - 2，则布尔函数f定义为公平函数.

Computational principals on how parts and wholes cooperate and conflict are investigated from the view point of computation theory. Among the results obtained in this project there are followings which we consider important :1. Using G-entropy, introduced in our paper, we develop an efficient boosting algorithm which is designed by using the top-down decision tree learning algorithm with its splitting criterion based on the G-entropy.2. The problem of dynamically apportioning resources among a set of options in a worst-case online framework is investigated by introducing information on how high the risk of each option is. We apply the Aggregating Algorithm to this problem and give a tight performance bound.3. We propose three methods of random projection which randomly maps data represented as vectors to a low dimensional space so that the margin is approximately preserved. Our algorithm turns out to be more efficient than the well known random projection method based on the Johnson-Lindenstrauss Lemma.4. We derive a superpolynomial lower bound on the size of Boolean circuits that compute the clique function with *(loglog n) negation gates.5. We show that a single variable function f(x)=x_j has the minimum correlation with the majority function among all fair functions, where the correlation between Boolean functions f and g is defined to be 1-2Pr[f(x)≠g(x)], and a Boolean function f is defined to be fair if Pr[f(x)=1]=1/2.