Data-driven algorithm design
Autor: | Tim Roughgarden, Rishi Gupta |
---|---|
Rok vydání: | 2020 |
Předmět: |
General Computer Science
Computer science business.industry 0102 computer and information sciences 02 engineering and technology Machine learning computer.software_genre 01 natural sciences Data-driven 010201 computation theory & mathematics Application domain 0202 electrical engineering electronic engineering information engineering Feature (machine learning) 020201 artificial intelligence & image processing Algorithm design Artificial intelligence Computational problem business Heuristics computer |
Zdroj: | Communications of the ACM. 63:87-94 |
ISSN: | 1557-7317 0001-0782 |
DOI: | 10.1145/3394625 |
Popis: | The best algorithm for a computational problem generally depends on the "relevant inputs," a concept that depends on the application domain and often defies formal articulation. Although there is a large literature on empirical approaches to selecting the best algorithm for a given application domain, there has been surprisingly little theoretical analysis of the problem. We model the problem of identifying a good algorithm from data as a statistical learning problem. Our framework captures several state-of-the-art empirical and theoretical approaches to the problem, and our results identify conditions under which these approaches are guaranteed to perform well. We interpret our results in the contexts of learning greedy heuristics, instance feature-based algorithm selection, and parameter tuning in machine learning. |
Databáze: | OpenAIRE |
Externí odkaz: |