TY - GEN

T1 - Learning binary matroid ports

AU - Hellerstein, Lisa

AU - Coullard, Collette

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028333235&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028333235&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0028333235

SN - 0898713293

T3 - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

SP - 328

EP - 335

BT - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

PB - Publ by ACM

T2 - Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms

Y2 - 23 January 1994 through 25 January 1994

ER -