Problems of Control and Information Theory 4. (Budapest, 1975)
1975 / 1. szám - Csibi, S.: Learning under computational constraints from weakly dependent samples
4 CSIBI: LEARNING UNDER COMPUTATIONAL CONSTRAINTS Suppose X and Y = {Yn\ n = 1, 2,.. .} to be related in a memoryless manner, in the following sense P(F„ = j I Xn, Zn l) = P(T„ = j I Xn) = ITj(Xn) for j = 0, 1. (Zn = {Zj, i <Z n}. We call, according to the usual terminology, II j= {rij(x), x £6X } a posteriori probability function with respect to //,. In this paper we show how this problem, concerning weakly dependent observations, may be reduced to disciplines of learning from totally independent sample sequences. In so doing we first extend two well-known theorems, due to Braverman and Rozonoer [5], in a way appropriate for our further purposes. Next we illustrate how to use these results for learning from weakly dependent samples under a set of usual computational constraints. 2. Extending stability theorems We adopt, concerning a pair of sequences S = {Sn; n = 1,2,...} and Z of random variables, the following well-known [8] notions: Definition A [8]. We say S to be adopted to Z if, for any n, S„ is measurable with respect to §{Zn). (Here and in what follows we refer by A, B, .. . and 1,2,... to cited and new notions, results, etc. respectively.) Definition В [8]. A sequence S of random variables, adapted to Z, is centered (with respect to Z) if E(Sn+1 | Zn) = 0 for any n. (Here and in what follows E stands for the expectation and E(.|.), specifically, for the conditional expectation.) Let us now turn, concerning Braverman’s and Rozonoer’s stability studies [5], to a fundamental result which underlies a number of theorems on learning either functions or classification rules from labelled samples. Theorem A [5]. Given a sequence G = {Gn, n = 1, 2, . . .} of nonnegative valued random variables adapted to Z. Let (i) \L(!y < °o and (ii) E(Gn+1|Zn)<G„ + Ä(n0). (1) (S(0) = {Sn; n = 1,2,...} stands for a sequence of nonnegative valued random variables adapted to Z, such that ^ E.S'}^ < °o.) Then there exists a /1 = 1 real valued random variable q for which P(limG„ = p) = 1. /1—00 Let us extend Theorem A according to our further purposes.