2020

It's Not What Machines Can Learn, It's What We Cannot Teach

Yehuda, Gal, Gabel, Moshe, Schuster, Assaf

Understand

Can deep neural networks learn to solve any task, and in particular problems of high complexity? This question attracts a lot of interest, with recent works tackling computationally hard tasks such as the traveling salesman problem and satisfiability.

In this work we offer a different perspective on this question.
Given the common assumption that $\textit{NP} \neq \textit{coNP}$ we prove that any polynomial-time sample generator for an $\textit{NP}$-hard problem samples, in fact, from an easier sub-problem.
We empirically explore a case study, Conjunctive Query Containment, and show how common data generation techniques generate biased datasets that lead practitioners to over-estimate model accuracy.

Built on

Optimal implementation of conjunctive queries in relational data bases
Chandra, A. K. and Merlin, P. M · 1977
Earlier work this paper cites.
Query optimization in database systems
Jarke, M. and Koch, J · 1984
Earlier work this paper cites.
Arboricity and subgraph listing algorithms
Chiba, N. and Nishizeki, T · 1985
Earlier work this paper cites.
Incomplete information in relational databases
Imieliński, T. and Lipski, W · 1988
Earlier work this paper cites.
Neural networks and NP-complete optimization problems; a performance study on the graph bisection problem
Peterson, C. and Anderson, J · 1988
Earlier work this paper cites.
On the complexity of test case generation for NP-hard problems
Sanchis, L. A · 1990
Earlier work this paper cites.
Turing computability with neural nets
Siegelmann, H. T. and Sontag, E. D · 1991
Earlier work this paper cites.
The SAT phase transition
Gent, I. P. and Walsh, T · 1994
Earlier work this paper cites.
Generating hard satisfiability problems
Selman, B., Mitchell, D. G., and Levesque, H. J · 1996
Earlier work this paper cites.
Neural networks for NP-complete problems
Budinich, M · 1997
Earlier work this paper cites.
Finding hard instances of the satisfiability problem: A survey
Cook, S. A. and Mitchell, D. G · 1997
Earlier work this paper cites.
Hard instance generation for SAT
Horie, S. and Watanabe, O · 1997
Earlier work this paper cites.
Verifying integrity constraints on web sites
Florescu, D., Levy, A., and Suciu, D · 1999
Earlier work this paper cites.
Neural networks for combinatorial optimization: a review of more than a decade of research
Smith, K. A · 1999
Earlier work this paper cites.
The nimble XML data integration system
Draper, D., Halevy, A. Y., and Weld, D. S · 2001
Earlier work this paper cites.
Elastic image matching is NP-complete
Keysers, D. and Unger, W · 2003
Earlier work this paper cites.
Phase transitions and backbones of the asymmetric traveling salesman problem
Zhang, W · 2004
Earlier work this paper cites.
A simple model to generate hard satisfiable instances
Xu, K., Boussemart, F., Hemery, F., and Lecoutre, C · 2005
Earlier work this paper cites.

Similar

Hard satisfiable clause sets for benchmarking equivalence reasoning techniques
Haanpää, H., Järvisalo, M., Kaski, P., and Niemelä, I · 2006
Cited alongside, same era.
ADASYN: Adaptive synthetic sampling approach for imbalanced learning
He, H., Bai, Y., Garcia, E. A., and Li, S · 2008
Cited alongside, same era.
On over-fitting in model selection and subsequent selection bias in performance evaluation
Cawley, G. C. and Talbot, N. L · 2010
Cited alongside, same era.
First-order theorem proving and Vampire
Kovács, L. and Voronkov, A · 2013
Cited alongside, same era.
Neural Turing machines
Original
Graves, A., Wayne, G., and Danihelka, I · 2014
Cited alongside, same era.
Adam: A method for stochastic optimization
Original
Kingma, D. P. and Ba, J · 2014
Cited alongside, same era.
Neural GPUs learn algorithms
Original
Kaiser, Ł. and Sutskever, I · 2015
Cited alongside, same era.
Hybrid computing using a neural network with dynamic external memory
Graves, A., Wayne, G., Reynolds, M., Harley, T., Danihelka, I., Grabska-Barwińska, A., Colmenarejo, S. G., Grefenstette, E., Ramalho, T., Agapiou, J., et al · 2016
Cited alongside, same era.
Complexity of distributions and average-case hardness
Itsykson, D., Knop, A., and Sokolov, D · 2016
Cited alongside, same era.
Deep Learning with Python
Chollet, F · 2017
Cited alongside, same era.
Learning combinatorial optimization algorithms over graphs
Khalil, E., Dai, H., Zhang, Y., Dilkina, B., and Song, L · 2017
Cited alongside, same era.
The expressive power of neural networks: A view from the width
Lu, Z., Pu, H., Wang, F., Hu, Z., and Wang, L · 2017
Cited alongside, same era.

Then

On the practical computational power of finite precision RNNs for language recognition
Weiss, G., Goldberg, Y., and Yahav, E · 2018
Later among the works it cites.
Ethical implications of bias in machine learning
Yapo, A. and Weiss, J · 2018
Later among the works it cites.
MixMatch: A holistic approach to semi-supervised learning
Berthelot, D., Carlini, N., Goodfellow, I., Papernot, N., Oliver, A., and Raffel, C. A · 2019
Later among the works it cites.
The use of deep learning for symbolic integration: A review of (Lample and Charton, 2019)
Original
Davis, E · 2019
Later among the works it cites.
Generating difficult SAT instances by preventing triangles
Original
Escamocher, G., O’Sullivan, B., and Prestwich, S. D · 2019
Later among the works it cites.
MIPaaL: Mixed integer program as a layer
Original
Ferber, A., Wilder, B., Dilina, B., and Tambe, M · 2019
Later among the works it cites.
On learning paradigms for the travelling salesman problem
Original
Joshi, C. K., Laurent, T., and Bresson, X · 2019
Later among the works it cites.
A survey on bias and fairness in machine learning
Original
Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., and Galstyan, A · 2019
Later among the works it cites.
Hidden stratification causes clinically meaningful failures in machine learning for medical imaging
Original
Oakden-Rayner, L., Dunnmon, J., Carneiro, G., and Ré, C · 2019
Later among the works it cites.
On the Turing completeness of modern neural network architectures, 2019
Pérez, J., Marinković, J., and Barceló, P · 2019
Later among the works it cites.
Learning to solve NP-complete problems: A graph neural network for decision TSP
Prates, M., Avelar, P. H., Lemos, H., Lamb, L. C., and Vardi, M. Y · 2019
Later among the works it cites.
Guiding high-performance SAT solvers with unsat-core predictions
Selsam, D. and Bjørner, N · 2019
Later among the works it cites.
SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver
Wang, P.-W., Donti, P., Wilder, B., and Kolter, Z · 2019
Later among the works it cites.
Predicting propositional satisfiability via end-to-end learning
Cameron, C., Chen, R., Hartford, J. S., and Leyton-Brown, K · 2020
Closest in time.
Learning TSP requires rethinking generalization
Original
Joshi, C. K., Cappart, Q., Rousseau, L.-M., Laurent, T., and Bresson, X · 2020
Closest in time.
Deep learning for symbolic mathematics
Lample, G. and Charton, F · 2020
Closest in time.
What can neural networks reason about?
Xu, K., Li, J., Zhang, M., Du, S. S., ichi Kawarabayashi, K., and Jegelka, S · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…