2017/03/15 by Ryan Spring, Anshumali Shrivastava, Spring, Ryan +1 · 2 citations
Computer Science · #Advanced Graph Neural Networks #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1703.05160
openalex publication_date 2017/03/15 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
Log-linear models are arguably the most successful class of graphical models\nfor large-scale applications because of their simplicity and tractability.\nLearning and inference with these models require calculating the partition\nfunction, which is a major bottleneck and intractable for large state spaces.\nImportance Sampling (IS) and MCMC-based approaches are lucrative. However, the\ncondition of having a "good" proposal distribution is often not satisfied in\npractice.\n In this paper, we add a new dimension to efficient estimation via sampling.\nWe propose a new sampling scheme and an unbiased estimator that estimates the\npartition function accurately in sub-linear time. Our samples are generated in\nnear-constant time using locality sensitive hashing (LSH), and so are\ncorrelated and unnormalized. We demonstrate the effectiveness of our proposed\napproach by comparing the accuracy and speed of estimating the partition\nfunction against other state-of-the-art estimation techniques including IS and\nthe efficient variant of Gumbel-Max sampling. With our efficient sampling\nscheme, we accurately train real-world language models using only 1-2% of\ncomputations.\n