2017-07-17-backurs17a.md

title	booktitle	year	volume	series	address	month	publisher	pdf	url	abstract	layout	id	tex_title	bibtex_author	firstpage	lastpage	page	order	cycles	editor	author	date	container-title	genre	issued	extras
Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms	Proceedings of the 34th International Conference on Machine Learning	2017	70	Proceedings of Machine Learning Research		0	PMLR	http://proceedings.mlr.press/v70/backurs17a/backurs17a.pdf	http://proceedings.mlr.press/v70/backurs17a.html	The classic algorithm of Viterbi computes the most likely path in a Hidden Markov Model (HMM) that results in a given sequence of observations. It runs in time $O(Tn^2)$ given a sequence of T observations from a HMM with n states. Despite significant interest in the problem and prolonged effort by different communities, no known algorithm achieves more than a polylogarithmic speedup. In this paper, we explain this difficulty by providing matching conditional lower bounds. Our lower bounds are based on assumptions that the best known algorithms for the All-Pairs Shortest Paths problem (APSP) and for the Max-Weight k-Clique problem in edge-weighted graphs are essentially tight. Finally, using a recent algorithm by Green Larsen and Williams for online Boolean matrix-vector multiplication, we get a $2^{\Omega(\sqrt{\log n})}$ speedup for the Viterbi algorithm when there are few distinct transition probabilities in the HMM.	inproceedings	backurs17a	Improving {V}iterbi is Hard: Better Runtimes Imply Faster Clique Algorithms	Arturs Backurs and Christos Tzamos	311	321	311-321	311	false	given family Doina Precup given family Yee Whye Teh	given family Arturs Backurs given family Christos Tzamos	2017-07-17	Proceedings of the 34th International Conference on Machine Learning	inproceedings	date-parts 2017 7 17	label link Supplementary PDF http://proceedings.mlr.press/v70/backurs17a/backurs17a-supp.pdf