エネルギー複雑度を用いた線形決定木の下界導出 Lower Bounds for Linear Decision Trees via An Energy Complexity Argument

Search this Article

Abstract

線形決定木とは,各内部ノードにおける分類規則が線形しきい値関数によって指定される二分決定木である.本論文では,線形決定木 T の各内部ノードの線形しきい値関数の重みw1, w2, ...,wn が,∑i|wi|≦w を満たし,かつ T が,非有界通信複雑性の大きい関数 (例えば 2 を法とする内積関数) を計算するならば,T は 2Ω(√n)/w 枚の葉を持つことを示す.証明には,線形決定木の葉の枚数と,しきい値回路のエネルギー複雑度の間にある密接な関係を利用する.ここで,しきい値回路 C のエネルギー複雑度とは,C の計算過程で "1" を出力する素子数の最大値として定義される.さらに我々は,深さが ω(1) でエネルギー複雑度が小さいしきい値回路の素子数について,2 種類の指数下界を与える.これらは深さが定数で抑えられないしきい値回路に対する,初めての超多項式下界である.A linear decision tree is a binary decision tree in which a classification rule at each internal node is defined by a linear threshold function. In this paper, we consider a linear decision tree T where the weights w1, w2, ...,wn of each linear threshold function satisfy ∑i|wi|≦w for an integer w, and prove that if T computes an n-variable Boolean function of large unbounded-error communication complexity (such as the Inner-Product function modulo two), then T must have 2Ω(√n)/w leaves. To obtain the lower bound, we utilize a close relationship between the size of linear decision trees and the energy complexity of threshold circuits; the energy of a threshold circuit C is defined to be the maximum number of gates outputting "1," where the maximum is taken over all inputs to C. In addition, we consider threshold circuits of depth ω(1) and bounded energy, and provide two exponential lower bounds on the size (i.e., the number of gates) of such circuits.

Journal

  • 研究報告アルゴリズム(AL)

    研究報告アルゴリズム(AL) 2011-AL-136(10), 1-7, 2011-08-30

Codes

  • NII Article ID (NAID)
    110008601841
  • NII NACSIS-CAT ID (NCID)
    AN1009593X
  • Text Lang
    ENG
  • Article Type
    Technical Report
  • Data Source
    NII-ELS 
Page Top