Pystruct - Structured Prediction in Python

Transcript

1. PyStruct Structured Prediction in Python Andreas Mueller (NYU Center for Data Science, scikit-learn)
2. Structured Prediction
3. Why structure?
4. Applications: Multi-Label Classification
5. Applications: Multi-Label Classification
6. Applications: Sequence Tagging
7. Applications: Sequence Tagging
8. Applications: Image Segmentation
9. Careful: Math ahead
10. The Essence of Structured Prediction
11. The Essence of Structured Prediction
12. Pairwise Structured Models
13. Pairwise Structured Models y 1 y 2 y 3 y 4
14. PyStruct Architecture Estimator = Learner + Model + Inference
15. PyStruct Architecture Estimator = Learner + Model + Inference model = ChainCRF(inference="max_product") ssvm = OneSlackSSVM(model=model, C=.1, inference_cache=50,, tol=0.1, verbose=3) ssvm.fit(X_train, y_train)
16. Sequence Tagging example model = ChainCRF(inference="max_product") ssvm = OneSlackSSVM(model=model, C=.1, inference_cache=50,, tol=0.1, verbose=3) ssvm.fit(X_train, y_train)
17. Sequence Tagging example model = ChainCRF(inference="max_product") ssvm = OneSlackSSVM(model=model, C=.1, inference_cache=50,, tol=0.1, verbose=3) ssvm.fit(X_train, y_train)
18. The Devil is in the Inference y 1 y 2 y 3 y 4 Easy: Dynamic Programming
19. The Devil is in the Inference Easy: Dynamic Programming
20. The Devil is in the Inference HARD! AD3, QPBO, LP, Loopy BP, ….
21. Grid Graphs: Snakes
22. Grid Graphs: Snakes crf = EdgeFeatureGraphCRF(inference_method='qpbo') ssvm = OneSlackSSVM(crf, inference_cache=50, C=.1, tol=.1, switch_to='ad3', n_jobs=1) ssvm.fit(X_train_edge_features, Y_train_flat)
23. Grid Graphs: Snakes
24. Implemented Methods Estimator = Learner + Model + Inference • Learner: SubgradientSSVM, StructuredPerceptron, OneSlackSSVM, LatentSSVM • Model: BinaryClf, MultiLabelClf, ChainCRF, GraphCRF, EdgeFeatureGraphCRF • Inference: Linear Programming, QPBO (PyQPBO), Dual Decomposition (AD3), Message Passing, everything (OpenGM)
25. Classes of Inference Algorithms Exact Algorithms Max-Product (Chains, Trees) 'max-product' Exhaustive (usually too expensive) Relaxed algorithms + branch & bound ('ad3', {'branch_and_bound': True}) Relaxed Linear Programming (slooow) 'lp' Dual Decomposition 'ad3' Approximate / heuristics Loopy message passing 'max-product' QPBO 'qpbo'
26. Classes of Inference Algorithms Exact Algorithms Max-Product (Chains, Trees) 'max-product' Exhaustive (usually too expensive) Relaxed algorithms + branch & bound ('ad3', {'branch_and_bound': True}) Relaxed Linear Programming (slooow) 'lp' Dual Decomposition 'ad3' Approximate / heuristics Loopy message passing 'max-product' QPBO 'qpbo' Install OpenGM for many more!
28. Thank you for your attention. @t3kcit @amueller t3kcit@gmail.com http://amueller.github.io