论文标题
从响应的混合物中恢复稀疏线性分类器
Recovery of sparse linear classifiers from mixture of responses
论文作者
论文摘要
在学习线性分类器的混合物的问题中，目的是从一系列二元响应中学习一系列超平面。每个响应都是用向量查询的结果，并指示了查询向量所属的集合中随机选择的超平面的侧面。该模型提供了具有分类标签的异质数据的丰富表示形式，并且仅在某些特殊设置中进行了研究。我们查看迄今未研究的查询复杂性上限的问题，即恢复所有超平面，尤其是对于稀疏平面稀疏的情况。这种设置是对极端量化问题的自然概括，称为1位压缩传感。假设我们有一组$ \ ell $ unknown $ k $ -sparse向量。我们可以使用另一个vector $ \ boldsymbol {a} $查询集合，以获取$ \ boldsymbol {a} $的内部产品的符号，并从$ \ ell $ -SET中获取一个随机选择的向量。多少查询足以识别所有$ \ ell $未知的向量？这个问题比基本的1位压缩感测问题（即$ \ ell = 1 $ case）和类似的回归问题（其中提供的值而不是符号）都更具挑战性。我们为此问题提供了严格的查询复杂性结果（具有有效的算法）。
In the problem of learning a mixture of linear classifiers, the aim is to learn a collection of hyperplanes from a sequence of binary responses. Each response is a result of querying with a vector and indicates the side of a randomly chosen hyperplane from the collection the query vector belongs to. This model provides a rich representation of heterogeneous data with categorical labels and has only been studied in some special settings. We look at a hitherto unstudied problem of query complexity upper bound of recovering all the hyperplanes, especially for the case when the hyperplanes are sparse. This setting is a natural generalization of the extreme quantization problem known as 1-bit compressed sensing. Suppose we have a set of $\ell$ unknown $k$-sparse vectors. We can query the set with another vector $\boldsymbol{a}$, to obtain the sign of the inner product of $\boldsymbol{a}$ and a randomly chosen vector from the $\ell$-set. How many queries are sufficient to identify all the $\ell$ unknown vectors? This question is significantly more challenging than both the basic 1-bit compressed sensing problem (i.e., $\ell=1$ case) and the analogous regression problem (where the value instead of the sign is provided). We provide rigorous query complexity results (with efficient algorithms) for this problem.
