# zbMATH — the first resource for mathematics

On learning to coordinate: random bits help, insightful normal forms, and competency isomorphisms. (English) Zbl 1094.68039
Summary: A mere bounded number of random bits judiciously employed by a probabilistically correct algorithmic coordinator is shown to increase the power of learning to coordinate compared to deterministic algorithmic coordinators. Furthermore, these probabilistic algorithmic coordinators are provably not characterized in power by teams of deterministic ones.
An insightful, enumeration technique based, normal form characterization of the classes that are learnable by total computable coordinators is given. These normal forms are for insight only since it is shown that the complexity of the normal form of a total computable coordinator can be infeasible compared to the original coordinator.
Montagna and Osherson showed that the competence class of a total coordinator cannot be strictly improved by another total coordinator. It is shown in the present paper that the competencies of any two total coordinators are the same modulo isomorphism. Furthermore, a completely effective, index set version of this competency isomorphism result is given, where all the coordinators are total computable. We also investigate the competence classes of total coordinators from the points of view of topology and descriptive set theory.

##### MSC:
 68Q32 Computational learning theory
##### Keywords:
coordination; learning; probabilistic machines
Full Text:
##### References:
 [1] Barzdin, J.M., Prognostication of automata and functions, Inform. process., 1, 81-84, (1971) · Zbl 0255.94031 [2] Blum, L.; Blum, M., Toward a mathematical theory of inductive inference, Inform. control, 28, 125-155, (1975) · Zbl 0375.02028 [3] Case, J.; Jain, S.; Kaufmann, S.; Sharma, A.; Stephan, F., Predictive learning models for concept drift, Theoret. comput. sci., 268, 323-349, (2001), (special issue for ALT’98) · Zbl 0983.68157 [4] Case, J.; Jain, S.; Lange, S.; Zeugmann, T., Incremental concept learning for bounded data mining, Inform. comput., 152, 74-110, (1999) · Zbl 1045.68572 [5] Case, J.; Ott, M.; Sharma, A.; Stephan, F., Learning to win process-control games watching game-masters, Inform. comput., 174, 1, 1-19, (2002) · Zbl 1009.68116 [6] Engl. Transl. Consultants Bureau, NY, pp. 25-43. · Zbl 0216.00901 [7] Freivalds, R.; Kinber, E.; Smith, C., On the impact of forgetting on learning machines, J. assoc. comput. Mach., 42, 1146-1168, (1995) · Zbl 0891.68088 [8] Fulk, M.; Jain, S.; Osherson, D., Open problems in systems that learn, J. comput. system sci., 49, 3, 589-604, (1994) [9] Gold, E.M., Language identification in the limit, Inform. control, 10, 447-474, (1967) · Zbl 0259.68032 [10] Jain, S.; Osherson, D.; Royer, J.; Sharma, A., Systems that learnan introduction to learning theory, (1999), MIT Press Cambridge, MA [11] Kummer, M.; Ott, M., Learning branches and closed recursive games, () [12] Kurtz, S.; Smith, C.; Wiehagen, R., On the role of search for learning from examples, J. exp. theoret. artif. intell., 13, 24-43, (2001) · Zbl 1050.68123 [13] Minsky, M., The society of mind, (1986), Simon and Schuster New York, NY [14] Montagna, F.; Osherson, D., Learning to coordinatea recursion theoretic perspective, Synthese, 118, 363-382, (1999) · Zbl 0943.03034 [15] Moschovakis, Y.N., Descriptive set theory, (1980), North-Holland Publishing Co. Amsterdam, New York, Oxford · Zbl 0433.03025 [16] Osherson, D.; Stob, M.; Weinstein, S., Systems that learnan introduction to learning theory for cognitive and computer scientists, (1986), MIT Press Cambridge, MA [17] L. Pitt, A Characterization of Probabilistic Inference, Ph.D. Thesis, Yale University, 1984. [18] Pitt, L., Probabilistic inductive inference, J. assoc. comput. Mach., 36, 383-433, (1989) · Zbl 0676.68046 [19] Pitt, L.; Smith, C., Probability and plurality for aggregations of learning machines, Inform. comput., 77, 77-92, (1988) · Zbl 0646.68096 [20] Rogers, H., Theory of recursive functions and effective computability, (1967), McGraw-Hill New York · Zbl 0183.01401 [21] R.I. Soare, Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Omega Series, Springer, Heidelberg, 1987.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.