Papers by Eric Corlett
Reanalyzing the Most Probable Sentence Problem: A Case Study in Explicating the Role of Entropy in Algorithmic Complexity (2021.eacl-main)
Copied to clipboard
| Challenge: | Existing descriptive complexity measures are ineffective at describing algorithms' behaviour, and can make an apparently tractable problem seem NP-complete. |
| Approach: | They propose to use statistical measures to give an updated analysis of the complexity of the NP-complete most probable sentence problem for pCFGs. |
| Outcome: | The proposed method can be applied to word sense disambiguation and inference tasks. |