“布尔线性阈值函数的低权近似及其应用”

n·±±·n.Σ≥−nComput.复杂. 16（2007），180-2091016-3328/07/020180-30DOI 10.1007/s00037-007-0228-7BirkhaüuserVerlag，Basel2007计算复杂度每个线性阈值函数都有一个低权近似器罗科河塞尔韦迪奥抽象。给定n个布尔变量上的任意线性阈值函数f，我们构造一个线性阈值函数g，它至多在输入的1/4分数上与f不一致你最好去看看2O（1/2）。我们如何让这些限制变得简单项的依赖n通过证明下界的（n）上的近似特定线性阈值函数所需的权重。我们给出两个应用程序。第一个是一个确定性的算法，用于近似计算满足分配的分数，以零-一背包问题为例，在一个加法器内。该算法在n中以时间多项式运行（但在1 /102中以指数方式运行）。在我们的第二个应用中，我们证明了任何线性阈值函数f都被其Chow参数（0阶和1阶傅立叶系数）的估计指定为在误差范围内，这些估计精确到加性1/（n2O（1/2））。这是它的性质，它是一个在n中为一个非负多项式的多项式，并给出了学习线性阈值函数所需样本数的第一个多项式界（以n在“限制性注意力集中”框架内关键词布尔函数，线性阈值函数，Chow参数，计算学习理论。主题分类。 0 6 E 3 0 、52C07、52C35、68Q15、68Q32。1. 介绍线性阈值函数或LTF是布尔函数f：{−1，1}n→{-1，1}，其中存在w =（w1，.，wn）∈R且θ∈R使得f（x）=sgnni=1wixi−θ对于所有的 x∈ {-1，1}。这里sgn函数被定义为sgn（x）= 1对于x0，sgn（x）= 1对于x 0，x0。线性阈值函数（在文献中有时称为第十六届全国妇女大会每个LTF都有一个低权重近似器181{−}自20世纪60年代以来，参见Dertouzos（1965）; Hu（1965）; Muroga（1971），目前在理论计算机科学的许多领域中发挥着重要作用。在复杂性理论中，基本感兴趣的复杂性类，如TC0是根据线性阈值函数定义的，并且已经进行了大量的致力于理解单个线性阈值门和由这些门组成的浅电路的计算能力，例如，Goldmann 等 人 （ 1992 ） ; Goldmann Karpinski （ 1998 ） ; Hajnal 等 人（1993）; Hofmeister（1996）; Orponen（1992）; Razborov（1992）。线性阈值函数在计算学习理论和机器学习中也起着核心作用;许多最广泛使用和最成功的学习技术，如支持向量机（Shawe-Taylor Cristianini 2000），各种boosting算法（Freund 1995; Freund Schapire 1997），以及基本算法，如Perceptron（Block 1962; Noviko Schapire 1962 ）和Winnow（Littlestone1988，1991）都是以基本方式基于线性阈值函数学习线性阈值函数的算法也已经证明有助于设计用于各种表达类的布尔函数的最快已知学习算法Klivanset al. 2004; Klivans Servedio 2001; Maass Turan 1994）。不难看出，任何线性阈值函数f：{-1，1}n→{-1，1}有某种表示它对学习理论和和复杂性理论（参见上面引用的参考文献）来理解这些整数权重必须有多大简单的计算参数表明，大多数超过1，1 n的线性阈值函数需要2 <$（n）的整数权重。Muroga等人的经典结果。（1961）表明，任何线性阈值函数f可以使用整数权重w1，. ，wn每个满足|≤ 2 O（n log n）。|≤ 2 O(nlogn). （这个结果后来被重新发现了很多次，例如，Hong1987;Ragh avan1988.）03TheFamousWomen（1994）展示了一个特定的线性阈值函数，并证明了它的任何整数表示必须具有幅度为2 π（nlogn）的权重。因此，（精确地）计算线性阈值函数所需的权重大小现在已经相当清楚了。在本文中，我们感兴趣的是近似计算线性阈值函数所需的权重的大小。假设一个布尔函数g是f的一个n-逼近子，如果Pr[g（x）±=f（x）]≤n，其中，bility是指从{-1，1}n中均匀选择x。我们认为：问题：设f为任意线性阈值函数。如果g是一个LTF，它近似于f，并且具有整数权重，那么g的权重需要多大？182塞尔韦迪奥第十六届全国妇女大会√√u≤n·2。±我们认为，这是一个自然的问题，需要根据其本身的优点进行研究;第1.2节中描述的应用给出了进一步的动机。当我们从精确计算切换到近似计算时，景观可能会发生巨大变化，考虑比较函数COMP（x，y）在2个n比特上，其输出1 i =x≥y（将x和y视为n -1）。位二进制数）。 不难证明COMP（x，y）是线性的。阈值函数，其需要大小为2π（n）的整数权重，但也容易看出COMP（x，y）由线性阈值函数近似，该线性阈值函数仅具有2 log（1/π）多个相关变量和整数权重，每个权重至多为O（1/π）。1.1. 我们的结果：近似线性阈值函数使用小的权重。我们对上述问题给出了一个比较完整的答案。在第3节中，我们证明了一个下界，展示了一个简单的线性阈值函数f，并表明任何f的n-近似线性阈值函数必须有一些大小为n（n）的权重。也许令人惊讶的是，我们还证明了O（n）是将任何线性阈值函数近似到任何恒定精度ε >0所需的权重的上限。我们的主要结果如下，在第4节中得到证明：T HEOREM1.1. 设f：{-1，1}n→ {-1，1}是任意线性阈值函数。对于任何n>0，存在具有整数权重u1，.，n满足n2O（1/2）我i=1定理1.1直接意味着每个单独的权重ui至多是n·2O（1/2）in星等。这意味着，所有新的时间都是n·2O·s（1/n2）。就对ω的依赖性而言，“正确”的答案在（1 /ω）ω（1）（见第7节）和我们从第1.1节得出的20缩小这一差距是今后工作的一个令人感兴趣的方向1.2. 应用. 我们给出定理1.1的两个主要应用。第一，在第5节，是一个确定性算法，用于近似计算满足任何线性阈值函数的分配的分数（或等效地，计算零-一背包问题的解的数量），以增加精度-是的 该算法的时间 复杂度为O<$（n2/n） +2O<$（1/n2）.第二个应用是重建一个线性阈值函数的问题，从（近似）其低阶傅立叶系数。各种√第十六届全国妇女大会每个LTF都有一个低权重近似器183√对于v ∈ Rn，我们记为v以表示v2+···+v2。 我们写u·v来表示i=1uivi的两个向量u，v ∈ Rn。自 20 世 纪 60 年 代 以 来 ， 人 们 一 直 在 研 究 这 一 问 题 的 各 种 形 式 （ 参 见Birkendorf 等 ，1998; Bruck ， 1990; Chow ， 1961; Goldberg ， 2001;Kaszerman，1963; Winder，1971;我们在第6节中详细描述了先前的工作）。我们证明，对于任何常数ε>0，任何线性阈值函数f在信息理论上被指定为在其0度和1度傅立叶估计的误差范围内精确到加性±1/O（n）的Chow参数第1.2节.设f：{-1，1}n→ {-1，1}是任意线性阈值函数。设g：{-1，1}n → {-1，1}是任意布尔函数，满足|≤1，. | ≤1,.n·2O·（1/2）·对于ea chS= 0，{1}，{2}， . . ，{n}。 nPr[f（x）± = g（x）]≤∞.这是第一个已知的精度界，它是n中的逆多项式; Goldberg（2001）以前的工作给出了1/ quasipoly（n）界。我们还观察到，有一个简单的1/ n（n）下限的精度要求。定理1.2直接给出了在Ben-David Dichterman（1998）的“限制注意力集中”学习框架中学习线性阈值函数所需的样本数量的第一个多项式界（以n为单位）1.3. 相关工作。据我们所知，我们的工作是第一次明确地解决了在n维布尔立方体上近似线性阈值函数所需的权重问题。Servedio（2004）提出了一个相关的问题，其中证明了布尔立方体上的任何单调线性阈值函数都可以通过多项式大小的单调布尔公式近似为任何常数精度。我们对定理1.1的证明是通过考虑Servedio（2004）的主要结果的证明中考虑的相同的三种情况来进行的，但细节是显著不同的;详细讨论见4.1节。2. 预赛n1n我们将对独立随机变量的和使用标准的尾界，特别是以下形式的Hoebounding界，其中偏差是有界的。内积184塞尔韦迪奥第十六届全国妇女大会ΣΣ·≥ǁǁ≤{−1，1}√≡第2.1节.固定任意0 ±=w∈Rn。对于任何γ >0，我们有PRx∈{−1，1}nwxγwe−γ2/2和Prx∈{−1，1}nw·x≤−γ概率论的另一个有用的工具是下面的定理，该定理给出了独立随机变量的某些和在任何小区域上的概率质量的上限。这个结果可以从Petrov（1995）的The-orem 2.14中导出; Servedio（2004）给出了一个简短的自包含证明。第2.2节.固定任意w ∈ Rn，|wi|对于每个i ≤ 1。 则对于每个λ ≥ 1且θ∈R，我们有xPrn|w·x − θ| ≤ λ ≤ 6 λ/μw。我们利用O_n（·）旋转来隐藏O_n（·）的变元的多元性，例如，如果g（n）=n2log3n，则可以用g（n）=O_n（n2）.3. 下限在这一节中，我们展示了一个线性阈值函数f，并证明了任何具有整数权重的表示，它可以计算出f的一个好的近似器，它必须有一个大小为n（n）的权重。设f：{−1，1}n+1→{−1，1}定义为：f（x1，. ，xn+1）= sgn（x1+···+xn+ nxn+1− n）。注意，f（x1，...，xn，1）= Maj（x1，.，xn）和f（x1，...，xn，−1）= −1对于所有x。为了方便起见，我们假设n2 mod 4，但很明显，可以在不失一般性的情况下去除这个假设。本节的主要结果是：THEOREM3.1. Leth：{−1，1}n+1→{−1，1}banyLTFwhich1/10-approxi-matesf，andndletsgn（n+v1x1+· · ·+vn+1xn+1−θ）是一个简单的整数，表示一个螺杆然后|vi| = 0（n）对于一些i.一个简单的应用Hoe的约束表明，对于任何当k=Θ（1）时，存在一个k-approximaginggLTFsgn（x1+· ··+xn+N xn+1−N），其中，N= 0， n）。第十六届全国妇女大会每个LTF都有一个低权重近似器185{−}ΣΣ···· ··n1n/2+1n/21√n≥（1/2）1/2−o（1）−111nnn+1个T HEOREM3.1 的 P 屋 顶 。 设 h1 表 示 函 数 h （ x1 ， . ， xn ， 1 ） = sgn（ v1x1+···+vnxn+ vn+1− θ ） 。 由 于 h 是 f的 1/10- 逼 近 器 ， 我 们 得 到Prx1，. . ，xn[h1（x）±=Maj（x）]≤1/5.下面的声明将是有用的。（更强的界限可以用更多的e来给出，但是n/2的界限对于我们的目的来说已经足够好了，并且允许一个非常简单的证明。3.2. 函数h1必须至少依赖于n/2个变量。PROOF.Supposeh1具有r1/5。 对于每个l= 1，.，n设gl：{− 1，1}l→ {−1，1}为变量x 1的布尔函数，.，xl，这是最接近的近似器到Maj（x1，.，xn）。它遵循Pr[h1±=Maj] ≥ Pr[gr±=Maj] ≥ Pr[gn/2±=Maj]。很容易看出，每个函数g1简单地是Maj（x1，. ，xl）。（在每个输入上，x=（x1，. ，xl），g l 的值是位b1 ， 1 ， 使 得 2n-l 扩 展（x1，.，xn）具有Maj（x1，.，xn）= b;容易检查该比特b是Maj（x1，.，xl）.）因此，Pr[gn/2±= Maj] =PrMaj（x1，.， xn/2）Maj（x1，. ，xn）≥Pr sgn（xn/2+1+···+xn）±= sgn（x1+·· ·+xn/2）&|xn/2+1+···+xn|>>|x1+···+xn/2|= Pr sgn（x++x）= sgn（x++x）×Pr.|>>|x1 + ··· + x n /2|Σ|Σ其中第二个等式成立，因为和的符号和幅度是独立的（因为n/2是奇数，每个符号以恰好1/ 2的概率实现Q根据权利要求3.2，我们可以在不失一般性的情况下假设，x1，.，xn/2是h1的相关变量。由于每个vi都是整数，因此每个|v1|，...、|vn/2|至少为1。令vJ表示n维向量（v1，..，vn），则有n/2。因为h1是Ma j（x1， . . ，xn）和ndPr[Maj（x） =1]=1/2−o（1），我们知道Prx1，. . ，xn[v1x1+· ··+vnxn+vn+1≥θ]≥0。295. 同样，sinceh（x）d=efsgn（vx+· · ·+vx−v−θ）是对>1/5186塞尔韦迪奥第十六届全国妇女大会≥ǁ ǁ···ǁ ǁ乌鲁河vjvj第在不损失一般性的情况下，我们可以假设f（x）= sgn（我们有1 = |w1| ≥ |w2| ≥···≥|wn|> 0。ni=1 wixi−θ）const nt函数−1，则可以证明Prx1，.. . ，xn[v1x1+· ··+vnxn−vn+1≥θ] ≤ 0。二、这两个不等式意味着vn+1>0，(3.3)PRx 1，.，XnΣ|v1x1+···+vnxn−θ| ≤vn+1≥ 0。095。设vmax表示max i=1，.，n|vi|，设ui= vi/vmax，i = 1，.，n，设λ = vn+1/vmax. 首先假设λ1。在这种情况下，我们可以应用定理2.2来获得0的情况。095≤（3. 3）=Pr|u·x − θ/v|≤ λΣ≤ 6 λ=6λvmax=6vn+1这意味着vn+1= n（n）。 另一方面，如果λ <1，则vn+1是不是最大的权重;不难证明这样的线性阈值函数相对于f必须具有大的误差。或者，我们可以观察到，如果λ1，那么根据定理2.2，我们有0的情况。095≤（3. 3）=Pr[|u·x−θ/v| u· x − θ /v|u·x−θ/v6 6vmax|≤1] ≤=MaxMax吉乌·吉乌夫这意味着vmax =（n）。所以在每种情况下都有一个权是n（n），定理3.1被证明了。Q4. 定理1.1Letn>0begivenandndletf：{−1，1}n→{−1，1}是一个新的线性时变函数。在Servedio（2004）的论证中，我们考虑了不同的情况，取决于w的值。在每种情况下，我们展示了如何构建一个具有整数权重的近似LTF，满足所要求的范围。病例I：平均体重≥ 12/kg。非常粗略地说，这种情况的想法是，许多权重与最大权重w 1相比是“大的”。（为了直观起见，考虑多数函数，其中1 =w1==wn;该函数具有w的最大可能值。）在这种情况下，构造的工作原理是将权重四舍五入到精心选择的粒度，并表明这只会产生很小的误差。在这种情况下，我们实际上证明了定理1.1的一个更强的版本，即，最多为O（nln（1/n）/n2）而不是n·2Oln（1/n2）.Max第十六届全国妇女大会每个LTF都有一个低权重近似器187ǁǁi=12n（4/n）·α√.Σ√n ln(1/є) ǁǁ ≥n我.Σ对于每个i = 1，. ，n设ui是通过将w i四舍五入到最接近的值而获得的值，i=1（ui/α）xi−θ/α）。我们将证明以下引理：2nΣ我让埃夫α=6×2nln（4/n）。α的整数倍。 设g（x）= sgn（nsgn（uixi−θ），或等价地g（x）=i=14.1. blog 线性阈值函数g（x）= sgn（n（ui/α）xi−θ/α）为大小因此，算法的时间复杂度为O（n ln（1/n）/n2）。P屋顶。 对于i = 1，...，n设ei= wi− ui，所以u·x = w·x − e·x。 设λ ≥ 1使得ϵ6λ=.2周我 们 有 一 个 sgn （ u·x−θ ） ±=sgn （ w·x−θ ） 的 唯 一 条 件 ， |e·x| ≥λ 或|w·x−θ| ≤λ。我们将证明，对于一个随机x，这两个事件中的每一个都以最大为<$/2的概率发生，因此Pr[g（x）±=f（x）] ≤<$。首先，我们绑定Pr[|e·x| ≥λ]。我们有这个|ei|对于每个i ≤ 1α，所以2向量e =（e1，. ，en）有n ∈en ≤ 1 αn。 假设λ =1，Hoe-bounding（定理2.1）给出Pr|e·x| ≥λ≤Pr[|e·x| ≥<$2ln（4/n）·<$e<$]≤2e−（<$2ln（4/n））2/2=<$/2。要绑定Pr[|w·x − θ|≤ λ]我们简单地应用定理2.2;这给出了Pr[|w·x − θ|≤ λ] ≤ 6 λ/<$w<$，根据我们在情形I中关 于 w 的原始条件，它等于<$/2。到目前为止，我们已经证明了g是f的一个π-逼近LTF。显然，hatg在mot1/α=O=O（nln（1/n））时具有与integerweightseach的表示，其中第二个等式使用n w12。在∗w ∗є事实上，我们可以限制这些整数权重的平方和的大小让vi=ui/α，所以每个vi都是整数，g（x）= sgn（v·x − θ/α）。很容易看出，对每个权重wi进行四舍五入以获得ui，以将其幅度增加至多两倍。因此，我们有，每个|vi| ≤ 2 |wi|/α，所以我们有（4.2）i=1v2≤4ni=12/α2= 4w2·72n ln（4/）2w2= O.n ln（1/2）/102QW一个整数权值至多O的f-逼近器（nln（1/n））in188塞尔韦迪奥第十六届全国妇女大会≤ǁ ǁn√···−| ≤±≤（2/2）nj=1 w2）>102/144。Kj=kJ在情形IIa中，我们有w2>（n =2/144）nj=l+1 w2，因此wl>（n/12）W=1JLJC aseII：w<12/. 请注意，由于|w1|=1，您可以重新编写此命令让我们建立一些符号。我们让C= 4 ln（4/μ m），C = 72 ln（2 C/μ m），τ = 102/144，l = 3 ln（C/τ）ln（4/μm）。1 2 1τ2注意l=O（1/2）。我们一起来看看证明了 如果不是这种情况，则nn=O（1/n ~2），因此定理1.1从Muroga等人的标准2 O（nlogn）重量上界向下三倍地下降。.与Servedio（2004）一样，我们考虑两个子案例。情形IIa：对 于 所 有 k = 1 ， . ， w2/（nnw2）> n2/144。湖 这个案子可能是被认为是捕获第一个L的权重非常迅速地减小的那些W几何级数。(For直觉上可以考虑ODDMAXBIT函数，即，具有交替输出位的判定列表;可以直接检查，对于该函数的标准线性阈值函数表示，w的值是与n无关的绝对常数，并且类似于情况IIa的连续权重的界限确实成立。在这种情况下，我们将在第一个l变量之后简单地截断线性阈值函数，而不是像在情况I中那样对权重wi进行舍入，并表明所得的LTF是f的一个近似器。由于这个截断的LTF只依赖于l个变量，Muroga等人的标准上限意味着它有一个整数表示，每个权重至多为2O（llogl）。并且，所需的时间总和为2O（11 0gl）=2O（1/12）。设g（x）= sgn（w1x1+···+wlxl− θ）. 让并让2l+1 +···+w2，η=2 W ln（4/μ m）。我们有g（x）±=f（x）的唯一性|wl+1xl+1+· · ·+wnxn| ≥η或|w1x1++w1×1θn。 我们将证明这些事件的概率都是最大为f/2，从而得到Pr[g（x）= f（x）] f。第一概率的界很容易;通过我们选择η，Hoe的界给出（4.3）Pr|wl+1xl+1+· · ·+wnxn| ≥ηε≤2e−2ln（4/ε）/2=ε/2。我们现在怎么样了？|w1x1+ · · ·+wlxl−θ| ≤η]≤η/2。请注意，W=w第十六届全国妇女大会每个LTF都有一个低权重近似器189j=IJ一一一2- − −- -τττ一i−1我我ki−1+1我（n/12）（n/12ln（4/12））。Itthere forsurestoshowat（4.4）Pr [|w1x1+· · ·+wlxl−θ| ≤（12/）2ln（4/）wl]≤/2。对于i = 1，.，n，我们将写Wi来表示nW2;注意Wi=w2+ Wi+1。下面的引理将是有用的（回想一下τ = π2/144）：4.5. 对于a b≤l，我们有W<（1−τ）b−aW<（1−τ）b−aw2.P屋顶。由于我们在情形IIa中，我们有w2> τ Wa=τw2+τ Wa+1，或a a等价地（1τ）w2> τWa+1。两边加上（1 τ）Wa+1，得到（1τ）（w2 + Wa+1）=（1τ）Wa>Wa+1.这意味着Wb<（1τ）b−aWa;第二个不等式由w2> τ Wa得出。Q我们将权重w1，... ，W1分成连续权重的块，如下所示。 其中，blockB1是{w1， . . ，wk1}，其中rek1是索引x，Wk+11ln（12/n）。没有使用Lemma4.5，we有这个w≤100W≤（1−τ）（l−（ki+1））/2W≤1000W。Prxki+1，. . ，x[|wki+1xki+1+· · ·+wlxl|≥<$2ln（2C1/n）·<$Wki+1]by<$/C1。但当w2+· ··2、2-（2ln（2C1/C））2/2=C 1/C。Q我们现在证明，无论第i个时间段之前的值i−1如何，第i个时间段之后的时间段都可以证明，|i−θ|≤2Wki+12ln（2C1/n）holds，其概率约为第i阶段中块BiLEMMA4.10.对于任意的εi−1∈R，我们有PRxki−1+ 1，.，xkiΣ|i−θ| ≤2<$Wki+1<$2ln（2C1/<$）<$<$≤1/2。好吧 Since|i−θ| ≤在区间[IL，IR]：=<$θ−<$i−1−2<$Wki+1<$2ln（2C1/<$）， θ−<$i−1+2<$Wki+1<$2ln（2C1/<$）<$width4Wki+12ln（2C1/n）。Firssupposet0∈/[IL，IR]，即，中间值的w孔具有相同的符号。 如果在对称性 中 Pr[wki−1+ 1xki−1+ 1+· · ·+wkixki∈[IL ， IR]]≤1/2s ， 则 值 wki−1+ 1xki−1+1+· ·+wkixki等于正或负。N=0∈[IL，IR]. 通过定义ki，我们不知道Wki+1≤|/C 2，并且结果是具有如下的值[IL，IR]|/C2,andconsequentlywehavethatthewidthoftheinterval[IL,IR]Lki+12Wki+1第十六届全国妇女大会每个LTF都有一个低权重近似器19133√|· · ·−|≤KnKj=kJ为至多4|焕光i−1+1个|n=2C1/n=2C2，其中n=2|焕光i−1+1个|誓，C2的发射。但我们注意到，一旦xki−1+ 1的值被设为r+1或r，−1，这是一个高效率的“t a r g e t i n t er v a l”，其中n o w k i − 1 + 2 x k i − 1 +2+ · ·· + w k i x k i m us t hit，通过将一个ceme n o f w k i − 1 + 1 to b ec om e [ IL − w k i − 1 + 1 x k i − 1 + 1，I R − w k i − 1 + 1 x k i − 1 + 1 ]来实现。由于最初的输入值[IL，IR]，长度最多2|焕光i−1+1个|，新的间隔不包含0，因此再次通过对称性是指概率y（n）不选择xki−1+ 2， . . . ，xki）使得wki−1+ 1xki−1+1+· · ·+wkixki在[IL，IR]]中至多为1/2。Q为了使w1x1++wlxlθ（12/n）2ln（4/n）wl，必须满足以下条件之一：（1）ea ch|i−θ|<2<$Wki+1<$2ln（2C1/n），其中i=1， . . . . ，ln（4/n）;或（2）对于smei≤ln（4/n），|i−θ|≥<$2<$Wki+1<$2ln（2C1/n），但引理4.10给出了（1）的概率至多为（1/2）ln（4/n）= n/4，引理4.7给出了（ 2 ） 的 概 率 至 多 为 ln （ 4/n ） ·n/C1=n/n/4 。 这 是 最 大 的 可 能 性|w1x1+· · ·+wlxl−θ|≤(12/）2 ln（4/n）wl至多为n/2，证明了（4.4）式情形Ⅱ b：对于某个k∈ {1，...，l}。粗略地说，在这种情况下，第一个k-1权重下降得相当快，但随后的速率下降速度减慢，wk与wk +1相比“不太大”，...，wn. 它似乎我们不能简单地截断权重wk，.，wn;相反，我们对权重wk，.，wn，以获得其中这些权重是小整数的1/ 2近似LTF。然后，我们认为，这个LTF本身是1/2-接近所有小整数权重的LTF。我们定义权向量uJ，vJ∈Rn如下：对于i = 1，.，k− 1字母i= wi/|焕光|.对于i=k， . . ， nletuJie是通过对wi/|焕光|的整数倍Jdef（/2）w2+···+w2Kα=6|W|2nln（8/(Note在情形I中处处α都有一个<$，现在αJ有<$/2。）让viJ=uJi/αJ尽管如此|w1x1+···+wlxl−θ|（<12/12）2ln（4/cm）wl.192塞尔韦迪奥第十六届全国妇女大会.Σ2±≤≥∈{− 个文件夹nI=k（viJ）2 = O（n lnj=kj=1J- -对于所有i = 1，.，n. 终于让θJ= θ/|焕光|、设g：{-1，1}n→ {-1，1}为LTFg（x）= sgn（uJ·x −θJ）或等价地g（x）= sgn（vJ·x− θJ/αJ）。我们首先证明g是f的一个n/2-逼近器，它具有第4.11章. 线性阈值函数g（x）= sgn（vJ·x−θJ/αJ）是一个f/2π-一个用于f. 当i≥k时，EacheighviJ是一个幂次不等式PROOF.修复一个新的设置x1，.. . ，xk−1的前一个tk−1bits。我不想看到你n−k+ 1个变量的线性阈值函数，通过固定FIrs t k−1input s offtox1， .. . ，xk−1;没有两个w可以写f（xk， . . ，xn）assgn（n（wj/|焕光|）xj−θJ+k−1（wj/|焕光|）xxx）。同样地，让我们来看看LTFonnk+1v通过确定tk可获得的可靠性1个输入sofgtotox=1， . . ，xk−1，也就是说，g（xk，...，xn）=sgnnj=kvjJxj−θJ/αJ+k−1j=1 vjJxj.我们有一个vethat1=|wk/|焕光||≥|wk+1/|焕光||≥· · ·≥|wn/|焕光||>0。摩尔-因此，对于i ≥ k，eachweig htvij由wi/|焕光|四舍五入至最接近αJ的整数倍（然后按αJ缩放以获得整数权重）。由于故障和故障排除的阈值很高（考虑到按yαJ缩放），我们可以应用L emma4.1，并且c考虑到Prxk，. . ，xn[g]f[m]≤m/2。 由于对 每个约束x∈{−1，1}k−1都成立，因此可以得出Pr x1 ，1n[g（x）=f（x）] n. 对于i k，所要求的权重viJ的界限由引理4.1得出Q接下来我们证明，任何线性阈值函数，它的要做到这一点，我们将需要下面的主张，其证明被推迟到以后：ΣO（nln（1/ln）），我们有第十六届全国妇女大会每个LTF都有一个低权重近似器193Si=1我√阈值函数，其中sk，sk +1，.，sn都是整数，nj=k2J ≤N。xk，.. .，xnKKnn·−4.12. 固定一个整数R > 0。 设表示{− 1，1}k−1× {−R，−R + 1，. ，R − 1，R}.设h是在k上的任何线性阈值函数，即， 对于某些w∈Rk和θ∈R，我们有h（x）= sgn（w·x−θ），对所有x∈ R。然后有一个h的表示为h（x）= sgn（u·x −θ），其中(a) 每个ui是整数，并且（b）第（1）款|ui| ≤R·（k + 1）！ 对于i = 1，...，k-1，|uk| ≤（k + 1）！.这一主张是Muroga et al. ’s classic upper bound on the size of4.13. 设tg：{−1，1}n→{−1，1}：g（x）=sgn（s·x−μ）bealinear然后存在线性阈值函数gJ（x）= sgn（t x v），其是g的n/2-逼近器，其中(i) 每个ti是整数;(ii) |≤ <$N ln（1 /n）· 2 O（k log k），其中i ≤ k − 1 ;以及|≤ √N ln(1/ϵ) · 2 O(klogk)for i≤ k − 1; and(iii) 卢恩t2≤N·ln（1/n）·2O（klogk）.P型屋面4.13的LEMMA我们首先观察到，通过锄头的束缚，我们有PrΣ|sx+· · ·+sx|><$2ln（4/n）<$N<$$>≤2e−（<$2ln（4/n））2/2=<$/2。直觉上，我们可以假设，nskxk最多总是有大小j=k2 ln（4/n）nn，这会导致我们产生最多n/2的误差（我们将使稍后更详细现在证明引理4.13的部分已经准备好了。让R=1021n（4/100）<$N。给定LTFg（x）= sgn（s·x−µ），设h：n→ {−1，1}为LTFk−1h（x）= sgnj=1sixi+ xk− µm。.Σ194塞尔韦迪奥第十六届全国妇女大会j=1.Σ.ΣΣΣ≤→·所有x∈ {-1，1}n有|nsjxj|≤R。ForeachsuchxwehavegJ（x）=.x 1，. ，xk− 1，Hnj=k sjxjj=k= g（x）. 因此gJ是g的一个n/2-逼近子，根据权利要求4.12，我们得到在域上h，h等价于h（x）=sgn（kuixi− µ），其中u1，. ，uk满足条件（a）和（b）。现在再-边gJ：{-1，1}n→ {-1，1}，gJ（x）=sgnk−1i=1 uixi+uknj=k sjxj-是的通过我们在项目开始时的努力，整数权重t1，. ，tn，其中ti= ui，i ≤ k − 1，tj= uksj，j ≥ k。从引理4.13和权利要求4.12的条件插入ui，uk，sj的界，完成引理4.13的证明。Q将Lemma4.11和Lemma4.13合并，回顾l=O<$ （1/<$2），并取引理4.13中的N为O（n ln（1/<$）/<$2），我们得到定理1.1在情形IIb下的所需结论。现在只需要证明第4.12条。PC4.12. 我们只需要稍微修改已知的证明Muroga等人。’s upper bound forLTF weights over 特别是我们密切关注H. S. tad（1994）第3部分中的大纲。设H0：RkR是一个线性函数H0（x）=ax+t，满足以下条件：1. sgn（H0（x））=h（x）.2. |对每个x ∈ φ ≥ 1。|≥ 1 for each x ∈ Ω.3. 在满足上述条件（1）和（2）的所有线性函数中，H0使x ∈ H的个数最大，|H0（x）|= 1。如果有一个以上可能的H达到最大值，选择一个任意的。观察到，由于h（x）是在λ上的线性阈值函数，存在满足（1）和（2）的某个线性函数，因此确实存在满足上述（1）-（3）的某个H0AsinHavanastad（1994），letx（1）， . . ，x（r）是一个连续点集，|=1。|=1. H？a？tad（1994）中的一个定理直接地证明了H？0是由以下方程唯一确定的：H0（x（i））= h（x（i）），其中i = 1，.，R.第十六届全国妇女大会每个LTF都有一个低权重近似器195K×±±|| ≤1·K因此，系数A1，...，ak，t可以通过求解k +1个方程的线性系统来获得：a1x（i）+···+akx（i）+t = h（x（i）），其中i = 1，.，k +1。对于这些方程中的每一个，右侧是±1，第一个k−1也是±1。系数x（i），.，x（i）(and（1），（2），（3），（4），（5），（6），（7），（9），（10），（11），（12），（13），（14），（15），（16），（17），（19），（10），（191k−1x（i）是{−R，.，R}。Cramer法则告诉我们，对于j = 1，...，k我们有aj= det（Mj）/det（M）对于合适的（k + 1）（k + 1）个矩阵M1，.，Mk，M. 更准确地说，矩阵M的第i行是向量x（i），其第（k + 1）项附加了1，矩阵Mj是M，但第j列被第i项是h（x（i））的列向量所取代. 由于M中除了第k列之外的所有元素都是1，并且第k列中的每个元素都是最大为R的整数，因此我们得到det（M）是最大为R的整数（k+1）！R，对于det（M1）也是如此，... ，det（Mk−1）. 矩阵Mk是一个1矩阵，所以它满足det（Mk）（k+ 1）！. 由于每个1，...，ak具有