全部版块 我的主页
› 论坛 › 经济学人 二区 › 外文文献专区
面板数据回归的Coresets
可人4
1357 14
2022-04-16
摘要翻译：
本文介绍了面板数据设置中回归问题的重置问题。我们首先定义了面板数据回归问题的几种变体的重置集，然后给出了构造大小多项式依赖于1/$\\varepsilon$（其中$\\varepsilon$是误差参数）和回归参数个数的重置集的有效算法--与面板数据中个体的个数或每个个体被观察的时间单位无关。我们的方法是基于Feldman-Langberg框架，其中一个关键步骤是上界“总灵敏度”，即在所有可能的回归参数选择中，所有个体时间对的最大影响之和。在经验上，我们用合成的和现实世界的数据集来评估我们的方法；用我们的方法构造的coreset的大小比完整的数据集要小得多，并且coreset确实加快了计算回归目标的运行时间。
---
英文标题：
《Coresets for Regressions with Panel Data》
---
作者：
Lingxiao Huang, K. Sudhir, Nisheeth K. Vishnoi
---
最新提交年份：
2020
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Machine Learning        机器学习
分类描述：Papers on all aspects of machine learning research (supervised, unsupervised, reinforcement learning, bandit problems, and so on) including also robustness, explanation, fairness, and methodology. cs.LG is also an appropriate primary category for applications of machine learning methods.
关于机器学习研究的所有方面的论文（有监督的，无监督的，强化学习，强盗问题，等等），包括健壮性，解释性，公平性和方法论。对于机器学习方法的应用，CS.LG也是一个合适的主要类别。
--
一级分类：Computer Science        计算机科学
二级分类：Computational Geometry        计算几何
分类描述：Roughly includes material in ACM Subject Classes I.3.5 and F.2.2.
大致包括ACM课程I.3.5和F.2.2中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Data Structures and Algorithms        数据结构与算法
分类描述：Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
一级分类：Economics        经济学
二级分类：Econometrics        计量经济学
分类描述：Econometric Theory, Micro-Econometrics, Macro-Econometrics, Empirical Content of Economic Relations discovered via New Methods, Methodological Aspects of the Application of Statistical Inference to Economic Data.
计量经济学理论，微观计量经济学，宏观计量经济学，通过新方法发现的经济关系的实证内容，统计推论应用于经济数据的方法论方面。
--
一级分类：Statistics        统计学
二级分类：Machine Learning        机器学习
分类描述：Covers machine learning papers (supervised, unsupervised, semi-supervised learning, graphical models, reinforcement learning, bandits, high dimensional inference, etc.) with a statistical or theoretical grounding
覆盖机器学习论文（监督，无监督，半监督学习，图形模型，强化学习，强盗，高维推理等）与统计或理论基础
--

---
英文摘要：
  This paper introduces the problem of coresets for regression problems to panel data settings. We first define coresets for several variants of regression problems with panel data and then present efficient algorithms to construct coresets of size that depend polynomially on 1/$\\varepsilon$ (where $\\varepsilon$ is the error parameter) and the number of regression parameters - independent of the number of individuals in the panel data or the time units each individual is observed for. Our approach is based on the Feldman-Langberg framework in which a key step is to upper bound the \"total sensitivity\" that is roughly the sum of maximum influences of all individual-time pairs taken over all possible choices of regression parameters. Empirically, we assess our approach with synthetic and real-world datasets; the coreset sizes constructed using our approach are much smaller than the full dataset and coresets indeed accelerate the running time of computing the regression objective.
---
PDF下载：
-->
English_Paper.pdf
大小:(753.74 KB)

 马上下载

二维码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

全部回复
mingdashike22
2022-4-16 11:12:22
用面板数据回归的Coresets，小黄华为TCS Labk。SudhirYale UniversityNisheeth K.VishnoiYale University2020年11月4日，用面板数据对几种回归问题的变体进行了coresets摘要，然后提出了构造大小的coresets的算法，这些coresets多项式依赖于1/ε（其中ε是误差参数）和回归参数的数量-与面板数据中的个体数量无关，在所有可能的回归参数选择的所有个体时间对中，我们用合成和现实世界的数据集来评估我们的方法；计算回归对象的coreset大小构造时间。arxiv:2011.00981 v2[CS.LG]2020.11月3日Contents1简介11.1相关工作。.............................................22`-与面板数据的回归33我们的面板数据的coreset代码44 GLSE 54.1算法的coreset定理4.1。....................................定理4.1的有用符号和有用事实。........................54.3定理4.1的证明。.......................................64.4引理4.3的证明：伪维数的上界。..................74.5引理4.4的证明：总灵敏度有界。........................85个用于GLSEK5.1验证概述的CORESET。..........................................115.2定理5.2的证明：GLSEK的上界。.........................125.3定理5.4的证明：GLSEK的下界。........................结论、限制和未来工作18A生成模型的讨论(1)23B OLSE的现有结果和方法23B。1定理B.1的证明。.......................................23B.2定理B.2的证明。.......................................241引言Panel数据，表示为asX∈Rn×T×Dandy∈Rn×T，其中实体/个体的数量，Tisthe时间段的数量和dis特征的数量在统计学中被广泛使用，并且只在机器上应用一次）[28,6]。使用观测数据推断变量之间关系的最常用方法是在时间段内包含实体。因此，面板数据的回归问题是以下关于回归变量β∈RD的优化问题，其中协方差矩阵Ω由上述参数minβ∈RD，Ω∈RT×TPI∈[N]yi-xiβ>-1yi-xiβ所导出。第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1这个回归模型的动机是Randome的ects模型（等式（1）和附录A)，在面板数据文献[，，]中常见。由于时间和空间的限制，参数空间为P=rd+q，一般采用ARQρ∈Rqq≥GLSE最小二乘估计。此外，拥有数据的组织可能只希望共享性能保证的一个问题子集，这些问题与在较小的Coreset上处理CompleteDataSet问题时获得的性能保证足够接近。由于Coresets的广泛应用和优点，它已经被开发用于各种无监督和有监督的重要限制，对于每一个可能的回归参数选择，它都接近回归目标。一个想法，因此，数据。但是，这个联合至少包含一个不受欢迎的tobservations，因为它可能很大。此外，目标。
二维码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

nandehutu2022
2022-4-16 11:12:29
在面板数据中，我们需要考虑如何对实体进行采样，以及在每个实体中如何使用这样一个由实体-时间对组成的coreset。我们的贡献。我们发起了对coreset的研究，用于`-与面板数据的回归，包括definition2.3)版本，以及GLSE的聚类扩展（GLSEK；定义2.4)，其中所有实体被划分为k个簇，每个簇共享相同的回归参数。ε与N和T无关。我们的主要贡献是:1.KNT，它使我们能够对coreset进行分析，类似于横截面数据的情况。对于GLSEk，回归在这个问题上，我们通过包含最小操作来定义一个coreset S上的回归目标。2.OMIN{ε-2d,d}coreset用于`-有截面数据的回归。3.～Oε-2max{qd,qd}。4.Kpolym,k,q,d,/εM介于OLSE的最大个体回归目标和最小个体回归目标之间（定义5.1）。我们提供了一个匹配的下界Ω(N)（定理5.4）fork,q,d≤2,表明coreset sizesh包含了比k,q,d,1/ε更多的因素，从而证明了M-有界假设。kρS变量使GLSE的目标函数非凸，而不是交叉-分段数据集ρβ∈RDK模型ork-means。因此，我们还不清楚GLSEK如何被简化为目标函数中高斯运算中使用的投影聚类，第二阶段将我们的GLSE的coreset构造应用于每个单独回归目标的EACHK“上下文可选性”（引理5.7）上，反过来，证明是由M-有界假设（第5.1）控制的。εε进一步，对于经验误差的可比水平，我们的coresets在样本量和coresets构造速度方面比均匀抽样INTERM性能好得多。1.1与面板数据相关的工作，依赖于生成模型，有几种方法来定义`-regression[，(1)参数与N和T无关（更多讨论见A节）。``承认大小为O(d/ε)[8]和大小为O(d)[33]的ε-coresets。利用截面数据，已经为机器学习中的一大类问题开发了coresets，以研究这些结果是否可以推广到面板数据。截面设置。2`-回归考虑以下`-回归生成模型：对于（i,t)∈[N]×[t]，yit=x>Itβi+eit，(1)βi∈rdeit∈r，包含一个额外的实体或个人指定的ectαi∈r，结果可用yit=x>Itβi+αi+eit表示。注2.1 xityitxit，yit，β∈rdyit-x>itβ缺少个体-时间对。假定`-回归函数可以表示为：对于任何回归参数ζP(Pζζpi∈[N]ψiζ,φi是否存在个体间的相关性以及βii是否唯一，φi有几个变体。βIβIβ设置导致普通最小二乘估计(OLSE)；定义2.2（普通最小二乘估计器(OLSE))(OLSE)，参数空间为RD，对于任意β∈RD，单个目标函数为φ(O)i(β):=pt∈[T]ρ(O)it(β)=pt∈[T](yit-x>itβ)。考虑当βii相同但单个时间周期之间可能存在相关性时，定义相关性的一种常见方法称为自相关关系纳(q)[，]，其中存在ρ∈Bq，其中q≥1是一个整数，Bq={x∈Rq:kxk<1}，如it=pmin{t-1,q}a=1ρaei,t-1 a+N(0,1）。
二维码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

kedemingshi
2022-4-16 11:12:35
（2）这种自相关得到了广义最小二乘估计(GLSE)。对于具有(q)(integerq≥1)的广义最小二乘估计(GLSE),参数空间为ISrd×Bq，对于任一ζ=(β,ρ)∈Rd×Bq，单个目标函数为ψ（G,q)i(ζ）:=pt∈[T]ψ（G,q)it(ζ）等于(1-kρk)(yi1-x>i1β)+ptt=2(yit-x>itβ)-pmin{t-1,q}j=1ρj(yi,t-j-x>i,t-jβ).,q）itxit,yitψ（G,q）itq(xi,max{1,t-q},yi,max{1,t-q}）,。KKK≥K，关于某些GLSE的回归参数相同。定义2.4（GLSEK：GLSE的扩展）Letk，q≥1是整数。对于一个GLSEk，参数Rd×Bq-kζβ(1)。.，β(k)，ρ(1)，...,ρ(k)∈Rd×Bq^k函数是ψ（G,q,k)i(ζ）:=minl∈[k]ψ（G,q)i(β(l),ρ(l))。kβ(l),ρ(l)l∈k，即GLSE，完全是GLSE。还要注意GLSEK可以被看作是clusteredlinear regression[4]的一个广义版本，其中个体之间没有相关性。3面板数据的coreset定义在这一节中，我们展示了如何在面板数据上定义回归的coreset，包括OLSE和GLSE。Duecross-分段设置。一种方法是将个体的所有观察视为一个不可分割的群体，并选择一个个体集合作为一个coreset。然而，这种构造导致了一个与大小相关的核重置。对于较大的核重置大小，我们引入了一个广义的定义：查询空间的核重置，它捕获了OLSE和GLSE的核重置。定义3.1（查询空间[21,9])将一个索引集与一个权函数u:x→r≥0。P∑xp→r≥0x∈xxζP∑ζpx∈xx·ψxζ。x,u,P,ψ具体地，如果u(x)=1对于所有x∈x,为了简单起见，我们使用(x，P,ψ）。由于ζ的可分性，我们得到了如下的核重置：核重置3.2（查询空间[21,9]的核重置）X,u,P,ρε∈，εX,u,P,ρsxw:S→r≥0,使得对于任一ζ∈P,ρS(ζ）:=px∈Sw(X)·ρX(ζ）∈(1±ε)·ρ(ζ）。因此，我们可以应用上面的识别来识别OLSE和GLSE的CORESET。注意OLSEis是Q=0的GLSE的特例。因此，我们只需要为GLSE提供coreset dognition。我们letu=1和P=Rd×Bq。GLSE的索引集有以下形式:Z(G，q)=Zit=Xi,max{1,t-q},yi,max{1,t-q},。..退欧，YIT：（我，t)∈[N]×[t],zitqzit∈Z(G,q)ζβ,ρ∈Pψittψ（G,q)itζ-kρk·yi1-x>i1βt6ψ（G,q)itζ(yit-x>itβ)-pmin{t-1,q}j=1ρj(yi,t-j-x>i,t-jβ)。因此，(Z(G，q)，P,φ（G,q））是GLSE的一个查询空间，我们对GLSE有如下的核重集定义：定义3.3(GLSE的核重集）X∈Rn×T×Dy∈Rn×Tε，q≥pεsN×T，并有权函数w：S→R≥0，使得对于任一ζ=(β,ρ)∈P,ψ（G,q)S(ζ）:=X(i,t)∈SW(i,t)·ψ（G,q)it(ζ）∈(1±ε)·ψ（G,q)(ζ）。SεZ(G，q),P,ψ（G,q)点在此共重集中至多(q+1)·s规定，对于OLSE,参数空间为rdsinceq=0,相应的索引集为Z(O)={zit=(xit,yit):(i，t)∈[N]×[t]}。因此，OLSE的查询空间为(Z(O),Rd,ψ(O))。对于GLSEK，由于在定义2.4中的操作，目标函数ψ（G,q,k）只能分解为子函数ψ（G,q,k））而不是单独的时间对。则letu=1,Pk=rd×bq^k,和Z(G，q，k)={zi=(xi1，yi1，..,xiT，yiT):i∈[N]}。我们可以把(Z(G，q，k),Pk,ψ（G,q,k))看作一个查询空间kεZ(G，q，k),Pk,ψ（G,q,k）是N个权函数w:is→r≥0,使得对于任一ζPk，xi∈ISW(i)·ψ（G,q,k)i(ζ）∈(1±ε)·ψ（G,q,k)(ζ）。
二维码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

nandehutu2022
2022-4-16 11:12:42
（3）在这里，我们稍微滥用了这个记号，用ζ（G,q)it(ζ）代替了ζ（G,q)zit(ζ）。但是，Eachzi∈Z(G，q，k)由tobservations组成，因此，这个coresetSisT·stkt中的点数进一步选择一个时间段子集来估计ψ（G,q,k）i.S.N×tis{i∈[N]:ut∈[T]，S.T.，(i，T)∈S}Si∈ISJS，i{T∈[T]:(i，T)∈S}中单个i的观测值3.4（GLSEk的Coresets)X∈rn×T×dy∈rn×Tεε(0,1）,整数k,q≥1,参数spacePk,glseks的ε-coreset是一个加权集[N]×[T]和一个权函数w:S→r≥0,对于任意ζ=(β(1)，)。.，β(k)，ρ(1)，...,ρ(k))∈Pk,ψ（G,q,k)S(ζ）：=xi∈isminl∈[k]xt∈JS,iw(i,t)·ψ（G,q)it(β(l),ρ(l))∈(1±ε)·ψ（G,q,k)(ζ）。与GLSE相似，这样的一个核重集S中的点数最多为(q+1)·S.4个GLSE4核重集。在本节中，我们将介绍如何构造GLSE的核重集。我们设参数空间BEPλ=RD×BQ1-λ，对于某个常数λ∈(0,1）,其中BQ1-λ=ρ∈RQ:KρK≤1-λ。定理4.1(GLSE的Coresets）存在一个随机化算法，对于给定的面板数据etx∈rn×t×dy∈rn×tε，δ，λ，q≥-δ构造一个ε-GLSE的coreset，其大小为ε-2λ-1qd最大qd,qd·logdλ+logδ,并在时间O（NT q+NT d)中运行，q·Oε-2λ-1qd最大qd,qd·logdλ+logδ,yitntλδλδ。进一步简化:Oε-2最大qd,qd·log d=poly(q,d,1/ε)。4.1定理4.1x的算法，y，输出单个时间对的一个重置。主要思想是利用Feldman-Langberg(FL)框架使用重要性抽样（第6-7行）[，]。关键的新步骤出现在第5行，它计算GLSE的灵敏度函数，该函数定义采样分布。还要注意，基于另一个函数(O)(4行）的SIS的构造，它实际上是文献[8]中研究过的OLSE的灵敏度函数。4.2定理4.1Feldman和Langberg[]的有用符号和有用事实表明了如何通过重要性抽样来构造核重集，核重集的大小被[9]改进。定理4.2(FL框架[21,9])ε,δ,dimsn×t→r≥0i,t∈N×ts(i，t)≥supζ,pλψ（G,q)it(ζ）ψ（G,q)(ζ）和G:=p(i，t)∈[N]×[t]s(i，t))。设S X由takingoε-2G(dim·log G+log(1/δ))构造算法1：CGLSE：GLSerequire的Coreset构造；X∈Rn×T×D，Y∈Rn×T，常数ε，δ，λ∈(0,1)、整数q≥1和参数空间pλ。确保：子集S[N]×[T]连同权函数w；S→R≥0.1:Mèoε-2λ-1qd最大qd,QD·logdλ+logδ的具体情况。2：设Z∈RNT×(d+1)是其(it-t+T)第1行是zit=(xit，yit)∈RD+1for（i,t)∈[N]×[t].3:计算RNT×dwhes列构成z.4的列空间的单位基：对于每一个（我，t)∈[N]×[t]，s(O)(i)，t)èkait-t+tk.5:对于每一对（i,t)∈[N]×[t]，s（i,t)minn1,2λ-1S(O)(i，t)+Pmin{t-1,q}j=1S(O)(i，t-j)O.6：选择M对的随机样本S[N]×[t]，其中每个（i,t)∈S以概率（i,t)P(i，t)∈[N]×[t]S(i，t).7：对于每个（i,t)∈S，w(i，t)èP(i，t)∈[N]×[t]S(i，t)M·S(i，t).8：输出（S,w）.x∈Xs(x)Gwxgs·S(x).概率至少为1-δ,S是GLSE的ε-coreset。这里，灵敏度函数S测量每一个xit的最大值。与灵敏度成正比。样本复杂度由总灵敏度G和伪二次函数控制。4.3定理4.1（引理4.3）和“灵敏度”（引理4.4）的证明；引理4.3(GLSE的伪维数）(Z(G，q),u，pλ，ρ(G，q))上的权函数u:[N]×[T]→r≥0至多为O((q+d)qd)，qd，以及单个回归目标的运算次数（对于GLSE为O(qd))。
二维码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

大多数88
2022-4-16 11:12:48
因此，我们得到引理4.3中的界O((q+d)qd)。Salgorithm1确实是GLSE的一个灵敏度函数，它度量了Eachxit∈X的最大灵敏度；由以下引理概括。引理4.4（GLSE的总灵敏度）函数:[N]×[T]→r≥0算法1的结论是，对于i,T∈N×tsi,T≥supζ∈pψ（G,q）it(ζ）ψ（G,q)(ζ）GP(i,T)∈[N]×[T]si,到λ-1qd，函数s的构造时间为O(NT q+NT d）。直观地说，如果灵敏度（i,T）很大，例如，接近1，ψ（G,q）时，它一定对某个参量ζpλ有重要的贡献。该抽样保证了我们很可能将这对（i,t）包含在从OLSE得到的φζ中，使每个单独的时间对对GLSE的灵敏度有界地变为：φ（G,q)ζ(O)ζβ,ρ∈Pλφ（G,q)iζ≥λ·ψ(O)iβ和φ（G,q)itζ≤·ψ(O)it(β)+pmin{t-1,q}j=1ψ(O)i,t-j(β)。...,xit,yitss（O）基于以下观察：对于任一ζ=(β,ρ)∈Pλ,ψ（G,q)it(ζ）ζ（G,q)(ζ）≤2·ψ（O）it(β)+pmin{t-1,q}j=1ψ（O）i,t)≤2λ-1·s(O)(i,t)+pmin{t-1,q}j=1s(O)(i,t-j)=s(i，t-j).然后它su-ces构造(O)(2-4d行（引理4.7）。因此，我们根据S.的规定得出GLSE的总灵敏度为isO(λ-1 qd)。现在我们准备证明定理4.1。证明:GOλ-1 qddimo((q+d)qd)gdimsize。对于运行时间，根据引理4.4计算灵敏度函数需要花费（NT q+NT d）的时间，而构造ε-核重置需要花费O（NT d）的时间。这就完成了证明。4.4引理4.3的证明：伪维数的上界我们的证明思想与[]类似。为了准备，我们需要以下引理来限定前馈神经网络的伪维数。引理4.5（对[2]定理8.14的重述）X,u,P,FFXζ={0,1}x∈xζPP Rmfx,ζ∈X×PFXζL运算:o算术运算+，-,×，和/在实数上。o跳转条件为>，≥，<，≤，=，6=实数的比较，和o输出0,1。然后是（X,u,P,f）至多为O(ml).Fx，这有助于将这个范围扩展到R.Lema 4.6（对[52]引理4.1的重述）X,u,P,fgxP×R→{0,1}是满足对任意x∈x，ζ∈P和r∈r,gx(ζ,r)=I[u(x)·f(x,ζ）≥r],那么(x，u，P，f)的伪维数正好是查询空间(x，u，P×r，gf)的伪维数。现在我们准备证明引理4.3。证明:un×t→r≥0I,t∈n×tgit:Pλ×r≥0→{0,1}是满足对任一ζ∈Pλ和r∈r≥0,git(ζ,r):=Ihu(I,t)·ψ（G,q）it(ζ）≥ri的指示函数。我们考虑查询空间(Z(G，q),u,Pλ×r≥0,G）。通过对pλ的认识，得到了pλ×r≥0ism=q+1+d的维数。通过对φ(G，q)it的认识，可以用L=O(qd)运算计算GIT，其中O(qd)ml(Z(G，q),u,pλ×r≥0,G）为O((q+d)qd)。然后通过引理4.6完成了证明。4.5引理4.4的证明：总敏感度的界我们通过将GLSE和OLSE之间的敏感度联系起来证明引理4.4。为了准备，我们给出了OLSE总灵敏度的上界引理。给定两个整数b≥1，表示(a，b)为矩阵inra×b的列基的运算时间。例如，通过计算矩阵INRA×B的SVD分解，可以得到它的列基，用[14]计算它的SVD分解时间为O（最小ab,ab）。算法1的引理4.7（OLSE的全灵敏度）函数(O):[N]×[T]→r≥0,证明了对于任意（i,T)∈[N]×[T],s(O)(i，T)≥supβ∈Rd'A(O)it(β)ρ(O)(β)(β)，(4)和G(O):=P(i，T)∈[N]×[T]s(O)(i，T)≤d+1。此外，函数(O)的构造时间为T(N，T，d+1)+O(N，d)。证明：证明思想来源于[]。根据算法1的第3行，RNT×DIS是一个矩阵，其列构成列空间OFZ的单位基。我们有≤d+1和Hencekak=d≤d+1。
二维码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

点击查看更多内容…
相关推荐
栏目导航
热门文章
推荐文章

说点什么

分享

微信QQ空间QQ微博
扫码加好友，拉您进群
各岗位、行业、专业交流群