Mostof the existing literature on supervised machine learning problems focuses on the case when the training data set is drawn from an i.i.d. sample. However, many practical problems are characterized by temporal dependence and strong correlation between the marginals of the data-generating process, suggesting that the i.i.d. assumption is not always justified. This problem has been already considered in the context of Markov chains satisfying the Doeblin condition. This condition, among other things, implies that the chain is not singular in its behavior, i.e. it is irreducible. In this article, we focus on the case when the training data set is drawn from a not necessarily irreducible Markov chain. Under the assumption that the chain is uniformly ergodic with respect to the $\mathrm{L}^1$-Wasserstein distance, and certain regularity assumptions on the hypothesis class and the state space of the chain, we first obtain a uniform convergence result for the corresponding sample error, and then we conclude learnability of the approximate sample error minimization algorithm and find its generalization bounds. At the end, a relative uniform convergence result for the sample error is also discussed.
翻译:关于受监督的机器学习问题的现有文献大多侧重于从一.d.样本中提取培训数据集的情况,然而,许多实际问题的特点是:时间依赖和数据生成过程边缘之间的紧密关联,这表明i.i.d.假设并不总是有正当理由的。这个问题已经在Markov链条满足Doeblin条件的背景下得到考虑。这一条件除其他外,意味着该链条的行为并不单一,即不可复制。在本条中,我们侧重于培训数据集来自不一定不可复制的Markov链条的情况。假设该链条对于$\mathrm{L ⁇ 1美元-Wasserstein的距离是统一的,假设等级和链的状态空间也存在某些规律性假设,我们首先从相应的抽样错误中取得统一的趋同结果,然后我们得出大约的抽样差错最小化算法的可学习性,并找到其一般化的界限。在结尾,对于抽样错误的相对一致的结果也进行了讨论。