Wednesday, December 19, 2018

Divide and Conquer Networks

Alex Nowak, David Folqué, Joan Bruna


  • Learn an algorithm from its inputs and outputs
  • Approximation algorithm based on neural nets


  • Limited to Divide and Conquer algorithms. DiCoNets
  • Invariance in size of input, e.g. Problems that can be solved via Recursion, Dynamic Programming
  • Learn two scale invariant operations:
    • Split
    • Merge
  • Split: 
    • Neural network work, trained via policy gradient
    • Rewards:External black box function, calculates cost based on problem constraints
    • Set2Set model, R layers
    • Model applied recursively until split size is less than predetermined value
    • Regularize split operation to control computation complexity 
  • Merge: 
    • Neural Network trained via back prop
    • Uses Pointer Networks (autoregressive model, where outputs are permutation of subsequence of inputs) or Graph Neural Networks (for graph problems)
Demonstrated on convex hull, clustering, knapsack, others, Accuracies in the range of 0.8-0.9 for convex hull.

No comments:

Post a Comment