ML Anthology

Learning Switch Configurations

Vijay Raghavan, Stephen R. Schach
COLT 1990 pp. 38-51
doi:10.1016/B978-1-55860-146-8.50006-0 /colt/1990/raghavan1990colt-learning/

Abstract

ABSTRACT Consider a black box with n electrical switches. A switch operation consists of setting an individual switch to the marked ON or OFF position. The output of the black box is a lamp (in series with a battery). The invisible part of the black box is an arbitrary interconnection of the switches. The lamp lights up when an electrical circuit is formed with the lamp and a subset of the ON switches. The problem is to find a representation of switches equivalent to the configuration in the black box by using only switch operations and observing the state of the lamp. The representation must satisfy the property that a set of ON switches causes the lamp to light up in the black box if and only if the corresponding set of switches does so in the representation. As stated, the problem is identical to that of exactly learning a large proper subclass of monotone Boolean functions. Observing the input-output relationship corresponds to using an N-oracle in Valiant's model and a membership query in Angluin's model. We show that O(n 2) switch operations and a total computational time of O(n 2) suffice to find an equivalent representation. This improves on earlier results of Valiant and Angluin, Hellerstein, and Karpinski on monotone μ-expressions by simultaneously enlarging the class of monotone Boolean functions learnable with queries and reducing the time complexity for so doing by a factor of n. The transformation of Angluin et al for unate functions can be used with our algorithm to reduce the time complexity of learning nonmonotone μ-expressions with membership and equivalence queries from O(n 4) to O(n 3).

COLT Semantic Scholar

Cite

Text

Raghavan and Schach. "Learning Switch Configurations." Annual Conference on Computational Learning Theory, 1990. doi:10.1016/B978-1-55860-146-8.50006-0

Markdown

[Raghavan and Schach. "Learning Switch Configurations." Annual Conference on Computational Learning Theory, 1990.](https://mlanthology.org/colt/1990/raghavan1990colt-learning/) doi:10.1016/B978-1-55860-146-8.50006-0

BibTeX

@inproceedings{raghavan1990colt-learning,
  title     = {{Learning Switch Configurations}},
  author    = {Raghavan, Vijay and Schach, Stephen R.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1990},
  pages     = {38-51},
  doi       = {10.1016/B978-1-55860-146-8.50006-0},
  url       = {https://mlanthology.org/colt/1990/raghavan1990colt-learning/}
}