Team learning as a game
This paper is concerned with relationships between forms of team \(FIN\) learning and probabilistic \(FIN\) learning, which are generalisations of the standard notion of finite (\(FIN\)) learning of partial recursive functions in computational learning theory. The main result proves the decidability of the subset relation on team \(FIN\) identification classes. The results are proved for asymmetric team learning which is still more general than team learning. A two player game (the \(FIN\) game) is introduced which is played on 0-1 matrices defining the learning requirements of two teams. The game is essentially finite (but for some easily detected cycles) and so whether the first player has a winning strategy is decidable. It is shown that the first player, playing on a matrix representing team learning type \([A]\) has a winning strategy over an opponent playing on a matrix representing team learning type \([B]\) if and only if \([A]FIN \not\subseteq [B]FIN\). Thus \([A]FIN \subseteq [B]FIN\) is decidable in \(A\) and \(B\). A natural extension of the \(FIN\) game is to the capability trees (more correctly collections of trees) of \textit{R. Daley} and \textit{B. Kalyanasundram} [Lect. Notes Comput. Sci. 961, 63-75 (1995)] whose labellings with the rows of the matrices representing \(A\) and \(B\) are shown to represent game histories of the \(FIN\) game between players playing on these matrices. \([A]FIN \subseteq [B]FIN\) then reduces to the decidable question of whether every valid labelling of a capability tree with the rows of \(A\) implies the existence of a valid labelling with the rows of \(B\), thus providing an alternative proof of the main result. A corollary of this decidability result and a known relation between team \(FIN\) learning and probabilistic \(FIN\) learning due to \textit{R. Daley, L. Pitt, M. Velauthapillai} and \textit{T. Will} [``Relations between probabilistic and team one-shot learners, in M. Warmuth and L. Valiant (editors), Proc. 1991 Workshop on Computational Learning Theory, Santa Cruz/CA, 228-239 (1991)] provides a simple proof that the hierarchy \(\mathcal H_{FIN}\) of critical ratios in probabilistic \(FIN\) learning is well-ordered. For the entire collection see [Zbl 0877.00015].
This page was built for publication: Team learning as a game
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4370213)
