Comment by tsumnia | Hacker News Reader

Comment by tsumnia | Hacker News Reader

Parent Full thread

Shamelessly Plugging my own videos on Linear Programs and Meta-heuristic Algorithms to solve Linear Assignment Problems.

The Linear Assignment Problem: https://www.youtube.com/watch?v=dMJpCnocmGk

Simulated Annealing: https://www.youtube.com/watch?v=21EDdFVMz8I

Genetic Algorithms: https://www.youtube.com/watch?v=Jm4qGteDlZE

Ant Colony Optimization: https://www.youtube.com/watch?v=Jm4qGteDlZE

Whenever I find some mythical free time I'd like to add a video about Constraint Satisfaction, but in the mean time here's my full lecture on CSP: https://www.youtube.com/watch?v=w5tPsbOvkmU

When we think about Explainable AI, we're looking for a "reason the AI made a decision". LLMs are using text prediction to make their decisions, but more traditional AIs use a different heuristic for their selection process. Many of these methodologies are still in use today and get the job done quite well. The "explanation" for these AIs is a (hopefully) intuitive method inspired by other natural phenomena that occurs in the world (like evolution, blacksmithing, literally how ants move).

If however you're looking for AI to explain the "why" element, I will admit that is where the traditional algorithms struggle, but I would add that LLMs aren't much more informative. Its reflection is going to be by guessing what the next right word to say is, which isn't any better or worse than the other models in terms of explainability.

Watched your Linear Assignment video, and the whole time I'm thinking why would one ever contemplate a meta-heuristic for Linear Assignment when Hungarian/Munkres runs in polynomial time? I think I must be missing some context.

Because you can also have additional restrictions (for example cumulative capacities) in which case the Hungarian method is not valid anymore.

In real life you rarely encounter the vanilla book version of a problem.

Algorithmic approaches tend to break completely if your problem does not follow the exact assumptions.

Model based approaches are more flexible. You just add more variables and constraints, and you use the same solver.

I talk briefly about this in my video on Heuristic Functions (I won't link just to stop shameless plugging), but its a combination of funding, knowledge, and team.

Scheduling problems are a specific type of Optimization problem and many of those problems are NP-hard to exponential in complexity. For example a 25x25 Linear Assignment Problem has 25! potentially configurations, which would take longer than the heat death of the universe to find the global maxima. It doesn't matter what algorithm you use, finding the absolute best solution and proving it is impossible.

I'm not super familiar with Hungarian/Munkres but a quick GPT conversation points out that its O(n^3) isn't really good for those types of large problem sizes. Even if 25! isn't bad, I can always increase my N.

Again, how do you decide if Hungarian is better than Simulated? You find a bunch of problems that both can do and test the algorithms against them. If you get decent enough results, I'm sure there's a science journal out there that would also publish the results.

> which would take longer than the heat death of the universe to find the global maxima

Sure, if you're using brute force, instead of a polynomial time algorithm.

> It doesn't matter what algorithm you use, finding the absolute best solution and proving it is impossible.

Hard disagree: https://en.wikipedia.org/wiki/Hungarian_algorithm

Linear Assignment seems a very strange choice to illustrate the utility of meta-heuristics, when that particular problem has a polynomial-time solution algorithm that has been known for 70 years.

I mostly use Linear Assignment because it was a simple problem that I could present to my students to serve as a foundation for learning about these algorithms and how they operate within a problem space. One aspect I believe helps in the learning process is to see an algorithm in action and to work through it at the base level.

The course is meant to serve as an intro to AI for students just coming out of a data structures course. Hungarian may be better for producing the optimal answer, I don't know I'd have to try it out. But I know that for my section on meta-heuristics Linear Assignment works as a great vehicle for demonstrating those algorithms.

Can you recommend some good books which explain "Mathematical Programming/Optimization" from the very beginning in a simple manner? Most books are notation heavy and seem to lack explanations for the beginning student. Long ago i was recommended N.S.Kambo's Mathematical Programming Techniques which covers a lot of ground but is very hard to understand.

The second question is, how (and where) are these techniques used in the ML/AI domain?

I used Russell and Norvig's "Artificial Intelligence: A Modern Approach" as a starting point for the course's schedule and have modified it over the years to help align with things I think would continue my students have a broad overview of all of AI.

These techniques won't be as widely advertised not because they're inefficient but rather from a marketing perspective it is often easier to just say "AI". However what I would do if I needed to find use case examples would be to search for research articles on Google Scholar [1]. They haven't hooked up a GPT summarizer to Scholar so you'll have to read through everything, but the game is find papers that DID use the approach.

For example, [2] is a research paper looking at utilizing Simulated Annealing to schedule disaster relief teams.

[1] scholar.google.com

[2] https://link.springer.com/article/10.1007/s00500-021-06425-6

Thank You. I have the Russell & Norvig AIMA book though i have not looked at everything there; probably as you point out it would answer my second question. Any pointers to specific chapters/sections would be appreciated.

What i was specifically asking for was for some intuitive and explanatory books on Mathematical Optimization/Programming (https://en.wikipedia.org/wiki/Mathematical_optimization and https://en.wikipedia.org/wiki/Linear_programming) independent of AI/ML. This is of course a much older subject with a lot of breadth. However i have not been able to find a intuitive introduction to the subject. Everything has been symbol heavy but not much explanations on the intuitive and model building aspects which imo is crucial to understanding.

My Constraint Satisfaction lecture (https://www.youtube.com/watch?v=w5tPsbOvkmU) may help, though I will say it only serves as a light 75 minute overview of constraints. Specifically in the second half of the lecture I use girl scout cookies and scooters to try and explain Linear Programming.

A quick Googling pulled up a Linear Programming Using Excel tutorial: https://science.utm.my/procscimath/wp-content/uploads/sites/...

This type of problem was what helped me understand the optimizations. I haven't studied the inner workings of the Simplex method, but it is used in Excel's Solver as well as Apache Commons'.

While it is still computer science oriented, I also like Grokking Algorithms (https://www.manning.com/books/grokking-algorithms). I used it as a source when I was building out some examples when I was teaching Algorithmic analysis and data structures. It does a great job of distilling the problems into a beginner friendly way that will lead you to dig into "what libraries are out there that have implemented this?"

Reply on news.ycombinator.com