Coresets and Decision Trees for Machine Learning Optimization

Explore a 59-minute lecture on Coresets and Decision Trees presented by Ibrahim Jubran from the University of Haifa at the HUJI Machine Learning Club. Delve into the mathematical foundations of k-decision trees and their application in matrix partitioning, focusing on how coresets can efficiently summarize large datasets while maintaining accuracy. Learn about the groundbreaking algorithm that creates (k,ε)-coresets for any matrix, with construction time of O(Nk) and coreset size polynomial in k log(N)/ε. Discover how this approach bridges decision trees in machine learning with partition trees in computational geometry, leading to significant performance improvements in random forests and parameter tuning. The lecture showcases experimental results using sklearn and lightGBM, demonstrating up to 10x faster computation times while maintaining accuracy on real-world datasets. Gain insights from Jubran's extensive experience in pose-estimation, 3D reconstruction, and machine learning, where he has developed innovative solutions and approximation algorithms.