LEARNING BINARY RELATIONS USING WEIGHTED MAJORITY VOTING

In this paper we demonstrate how weighted majority voting with multipl icative weight updating can be applied to obtain robust algorithms for learning binary relations. We first present an algorithm that obtains a nearly optimal mistake bound but at the expense of using exponentia l computation to make each prediction. However, the time complexity of our algorithm is significantly reduced from that of previously known algorithms that have comparable mistake bounds. The second algorithm w e present is a polynomial time algorithm with a non-optimal mistake bo und. Again the mistake bound of our second algorithm is significantly better than previous bounds proven for polynomial time algorithms. A k ey contribution of our work is that we define a ''non-pure'' or noisy binary relation and then by exploiting the robustness of weighted majo rity voting with respect to noise, we show that both of our algorithms can learn non-pure relations. These provide the first algorithms that can learn non-pure binary relations.