On Learning Mixture of Linear Regressions in the Non-Realizable Setting
On Learning Mixture of Linear Regressions in the Non-Realizable Setting
复制标题
DOI：
10.48550/arxiv.2205.13166
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Avishek Ghosh;A. Mazumdar;S. Pal;Rajat Sen
中科院分区：
文献类型：
--
作者：
Avishek Ghosh;A. Mazumdar;S. Pal;Rajat Sen
虽然线性回归混合（MLR）是一个被充分研究的课题，但先前的研究通常没有针对预测误差分析此类模型。事实上，在混合模型的背景下，“预测”和“损失”并没有明确的定义。在本文中，我们首先表明MLR可用于预测，在此模型不是预测一个标签，而是预测一系列值（也称为“列表解码”）。列表的大小等于混合模型中组件的数量，并且损失函数定义为所有组件模型所产生的损失中的最小值。我们表明，通过这个定义，经验风险最小化（ERM）的一个解能够实现较小的预测误差概率。这就需要一种算法来最小化MLR的经验风险，而这在计算上是困难的。先前关于MLR的算法研究集中在“可实现”的设定上，即当数据由混合线性（有噪声）模型以概率方式生成时对参数的恢复。在本文中，我们表明一种流行的交替最小化（AM）算法的变体在数据集和初始点满足某些正则性条件时，即使不假设可实现模型，也能在数据集中找到最佳拟合线，从而为ERM提供了一个解。我们还提供了一种在数据点数量上以多项式时间运行的算法，并恢复最佳拟合线的一个良好近似。对这两种算法进行了实验比较。
While mixture of linear regressions (MLR) is a well-studied topic, prior works usually do not analyze such models for prediction error. In fact, {\em prediction} and {\em loss} are not well-defined in the context of mixtures. In this paper, first we show that MLR can be used for prediction where instead of predicting a label, the model predicts a list of values (also known as {\em list-decoding}). The list size is equal to the number of components in the mixture, and the loss function is defined to be minimum among the losses resulted by all the component models. We show that with this definition, a solution of the empirical risk minimization (ERM) achieves small probability of prediction error. This begs for an algorithm to minimize the empirical risk for MLR, which is known to be computationally hard. Prior algorithmic works in MLR focus on the {\em realizable} setting, i.e., recovery of parameters when data is probabilistically generated by a mixed linear (noisy) model. In this paper we show that a version of the popular alternating minimization (AM) algorithm finds the best fit lines in a dataset even when a realizable model is not assumed, under some regularity conditions on the dataset and the initial points, and thereby provides a solution for the ERM. We further provide an algorithm that runs in polynomial time in the number of datapoints, and recovers a good approximation of the best fit lines. The two algorithms are experimentally compared.