Wednesday, December 19, 2018

Divide and Conquer Networks

Alex Nowak, David Folqué, Joan Bruna
https://arxiv.org/abs/1611.02401


Problem:

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

Approach:

  • 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)
Results:
Demonstrated on convex hull, clustering, knapsack, others, Accuracies in the range of 0.8-0.9 for convex hull.

No comments:

Post a Comment