• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

A Probabilistic Search for the Best Solution Among Partially Completed Candidates

Filip Ginter, Aleksandr Mylläri, Tapio Salakoski, A Probabilistic Search for the Best Solution Among Partially Completed Candidates. In: Proceedings of the Workshop on Computationally Hard Problems and Joint Inference in Speech and Language Processing (HLT/NAACL'06), New York City, New York, USA, 33-40, Association for Computational Linguistics (ACL), 2006.

Abstract:

We consider the problem of identifying among many candidates a single best solution which jointly maximizes several domain-specific target functions. Assuming that the candidate solutions can be generated incrementally, we model the error in prediction due to the incompleteness of partial solutions as a normally distributed random variable. Using this model, we derive a probabilistic search algorithm that aims at finding the best solution without the necessity to complete and rank all candidate solutions. We do not assume a Viterbi-type decoding, allowing a wider range of target functions.

We evaluate the proposed algorithm on the problem of best parse identification, combining simple heuristic with more complex machine-learning based target functions. We show that the search algorithm is capable of identifying candidates with a very high score without completing a significant proportion of the candidate solutions.

BibTeX entry:

@INPROCEEDINGS{inpGiMySa06a,
  title = {A Probabilistic Search for the Best Solution Among Partially Completed Candidates},
  booktitle = {Proceedings of the Workshop on Computationally Hard Problems and Joint Inference in Speech and Language Processing (HLT/NAACL'06), New York City, New York, USA},
  author = {Ginter, Filip and Mylläri, Aleksandr and Salakoski, Tapio},
  publisher = {Association for Computational Linguistics (ACL)},
  pages = {33-40},
  year = {2006},
}

Belongs to TUCS Research Unit(s): Turku BioNLP Group

Edit publication