Problems of Control and Information Theory 4. (Budapest, 1975)

1975 / 1. szám - Csibi, S.: Learning under computational constraints from weakly dependent samples

1* Problems of Control and Information Theory, Vol. 4(1), pp. 3—21 (1975) LEARNING UNDER COMPUTATIONAL CONSTRAINTS FROM WEAKLY DEPENDENT SAMPLES* S. CSIBI (Budapest) (Received June 15, 1974) Assume a classification rule has to be learned from samples for which the correct hypotheses are known, however the sample sequence is weakly dependent. Admit, for the sake of simplicity, just »»„-dependence. Suppose the relation between hypotheses and samples to be memory less. (Both notions are specified more precisely in the paper.) We show, by extending well-known stability studies due to Braverman and Rozonoer to perturbations, including also real valued but centered components, how such sort of learning problems may be reduced to the disciplines of learning from independent observations. We show, as an illustration, how may be finite dimensional projections of Bayesian discrimination functions, defined with respect to first-order probability distributions, estimated, under such conditions, by means of the very same algorithm, independently of how the subsequent samples precisely depend on each other. 1. Introduction Let our problem be to learn a classification rule from labelled samples Zn = (Xn, Yn), n — 1,2,... Assume Yn = 1 if, for Xn, some hypothesis Hv and Yn = 0 if its complement H0 holds true. Suppose X — {Xn; n = 1,2,...} to be a random process defined in some probability space (Q, cfß, P), taking values in (%, Assume X to be strict sense stationary and m0-dependent. m0-dependence is used in the usual sense. I.e., we assume there exists some positive integer m0 for which P {A'A") = P(A')P(A") for any A' £<!F(Xn) and A" £ §(n+moX) and n — 1, 2, . . . (Xn = {A,-, i <[ n} and n~maX — {Xj, i >» -f rn0}. SF(Xn) stands for the u-algebra generated by Xn, and oF(n+moA) is defined in a similar way.) We confine ourselves to m0-dependence just for the sake of simplicity. For the probability measure of X only the afore-mentioned loose properties are assumed to be a priori known. * Partly presented at the 3rd International Symposium on Information Theory, URSI —USSR Ac. Sc. (Tallinn, June 15-19, 1973).

Next