Identifying similar keywords, known as broad matches, is an im-
portant task in online advertising that has become a standard fea-
ture on all major keyword advertising platforms. Effective broad
matching leads to improvements in both relevance and monetiza-
tion, while increasing advertisers’ reach and making campaign man-
agement easier. In this paper, we present a learning-based approach
to broad matching that is based on exploiting implicit feedback in
the form of advertisement clickthrough logs. Our method can uti-
lize arbitrary similarity functions by incorporating them as features.
We present an online learning algorithm, Amnesiac Averaged Per-
ceptron, that is highly efficient yet able to quickly adjust to the
rapidly-changing distributions of bidded keywords, advertisements
and user behavior. Experimental results obtained from (1) histor-
ical logs and (2) live trials on a large-scale advertising platform
demonstrate the effectiveness of the proposed algorithm and the
overall success of our approach in identifying high-quality broad
match mappings.