Reranking Algorithm

A reranking algorithm is an algorithm that reranks the outputs of a ranking algorithm.

• AKA: Re-Ranking Algorithm, Output Reranking Algorithm.
• Context:
  • It can introduce information not available to the original ranking algorithm, such as a global predictor features.
  • It can be:
    • a Discriminative Reranking Algorithm.
    • a Generative Reranking Algorithm.
• Example(s):
  • MaxEnt-Rank (Charniak and Johnson, 2005; Ji and Grishman, 2005),
  • SVMRank (Shen and Joshi, 2003),
  • Voted Perceptron (Collins, 2002; Collins & Duffy, 2002; Shen & Joshi, 2004),
  • Kernel Based Methods (Henderson and Titov, 2005),
  • RankBoost (Collins, 2002; Collins & Koo, 2003; Kudo et al., 2005).
• See: k-Best List Algorithm, Joint Inference Algorithm.

---

---

References

2005

• (Collins & Koo, 2005) ⇒ Michael Collins, and Terry Koo. (2005). “Discriminative Reranking for Natural Language Parsing.” In: Computational Linguistics, 31(1) doi:10.1162/0891201053630273
• (Charniak & Johnson, 2005) ⇒ Eugene Charniak, and Mark Johnson. (2005). “Coarse-to-Fine n-Best Parsing and MaxEnt Discriminative Reranking.” In: Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics (ACL 2005) doi:10.3115/1219840.1219862

2001

• (Collins & Duffy, 2001) ⇒ Michael Collins, and Nigel Duffy. (2001). “Convolution Kernels for Natural Language.” In: Proceedings of NIPS 2001.

---