Learning binary matroid ports

Lisa Hellerstein, Collette Coullard

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    In this paper we present an algorithm that extends previous research in two distinct fields - matroid theory and computational learning theory. In matroid theory terms, our algorithm proves a constructive version of an early theorem of Lehman. Lehman proved that the port of a connected matroid uniquely determines the matroid. Following previous research on matroid oracle algorithms, we introduce a new oracle, the port oracle, which determines whether a set of elements contains a member of the port. Our algorithm constructs a binary matrix representation of a connected binary matroid in polynomial time via a polynomial number of calls to the port oracle. The algorithm is non-trivial, and does not follow directly from Lehman's proof. (By generalizing the techniques of our algorithm, we can also prove that for arbitrary connected matroids, an independence oracle can be simulated via a polynomial number of calls to a port oracle.) In computational learning theory terms, our algorithm learns the class of binary matroid port functions in polynomial time using membership queries. There are few non-trivial classes known to be learnable in polynomial time in this model. Our algorithm generalizes results of Angluin, Hellerstein, and Karpinski, and Raghavan and Schach, who showed that certain subclasses of the binary matroid port functions are learnable in polynomial time using membership queries. Our algorithm also represents the first use of matroid theory techniques in solving computational learning theory problems.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
    PublisherPubl by ACM
    Pages328-335
    Number of pages8
    ISBN (Print)0898713293
    StatePublished - Jan 1 1994
    EventProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms - Arlington, VA, USA
    Duration: Jan 23 1994Jan 25 1994

    Publication series

    NameProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

    Other

    OtherProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms
    CityArlington, VA, USA
    Period1/23/941/25/94

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Learning binary matroid ports'. Together they form a unique fingerprint.

  • Cite this

    Hellerstein, L., & Coullard, C. (1994). Learning binary matroid ports. In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms (pp. 328-335). (Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms). Publ by ACM.