cgreerrun

I think it is notable because he's an expert in that area and would know how to assess it. I'm not a fan of the tone either though...

But the authors claim "Hopular surpasses Gradient Boosting (e.g. XGBoost), Random Forests, and SVMs on tabular data." So if a simple sklearn model works better, it's worth knowing it might not be all it's cracked up to be before deciding to spend hours understanding another paper.

Also more context about criticism from the paper's authors here: https://twitter.com/bschaefl/status/1532281938593173504

Notable criticism here: https://medium.com/@tunguz/trouble-with-hopular-6649f22fa2d3

With a little formatting to make it feel like a fiction book, the writing style works much better for me: https://imgur.com/a/5R3x2BL

Love the article and the writing style!

  /* CSS changes for fiction book style: */

  .postbody p::first-letter {
    margin-left: 18px;    
  }

  .postbody p {
    text-align: justify;  
    hyphens: auto;  
    line-height: 29px;  
    font-family: Georgia;  
    max-width: 683px;  
    margin-top: 1px; 
    margin-bottom: 0px;
  }

I haven't personally, but I know people that have. The people that I know that sold shares used Equity Zen (https://equityzen.com/). The company I worked for has/had a "first right of refusal" option in the equity contracts, which basically means that when EquityZen offers you a deal, you have to bring the deal to your company and they can decide to buy your shares for the same price instead of letting you sell your shares to an outside party (which they might not want).

+1 to sibling comment about not choosing the SOTA just cuz SOTA (if you're in the market for an ANN algo). Almost all the ones there are pretty darn fast these days and many (e.g. hnsw) are implemented out of the box by libraries like nmslib.

Also, most search use cases have requirements besides just the "get_k_nearest" functionality too (scoring-level filtering, business logic built into scoring unrelated to similarity, disparate query patterns that don't fit nicely into a single similarity space), so unless you only need to retrieve the K most-similar documents it might not be a good solution.

This site keeps track of them: https://github.com/erikbern/ann-benchmarks#glove-100-angular

ScaNN is currently SOTA: https://ai.googleblog.com/2020/07/announcing-scann-efficient...

> Thanks for sharing!

You're welcome.

> Why did you use GBDTs instead of NNs?

I mostly wanted to build an implementation to see how it worked; I was more familiar with GBDTs than NNs, so I figured I'd start with that. At its heart, AlphaZero is the marriage of two great ideas: using a Monte Carlo Tree Search (MCTS) to efficiently look ahead and find good moves and using a powerful ML model (like a ResNet) as a bot's intuition about which positions are good to be in (value network) and which moves are good when you're in which positions (policy network). So if a GBDT is powerful enough for your use case, the "ML Model" component in the MCTS+ML Model AlphaZero setup should be able to be swapped out with it if you want.

But I was also curious if GBDTs would do almost as well as a NN, because GBDTs can be much more efficient w.r.t. cost/energy. At the time when AlphaZero came out, I think it cost >$10M to train a superhuman Go algo. Nowadays KatoGo [1] can do it for <$50K. The most expensive part of training is the self play. You basically have bots play millions of games against each other and learn from the results of those games. Getting value/policy predictions each move from the ML models is a majority of the computation during self play, so if you make that more efficient, you should be able to train a bot faster/cheaper.

Check out this HN thread if you're interested in more AlphaX shenanigans: https://news.ycombinator.com/item?id=23599278

[1] https://github.com/lightvector/KataGo

What you can do is checkout the algorithm at particular stages of development. AlphaZero&Friends start out not being very good at the game, then over time they learn and eventually become super human. You typically checkpoint the weights for the model at various stages. So early on, the algo would be like a 600 elo player for chess and then eventually get to superhuman elo levels. If you wanted to train using an AlphaX algo, you can gradually play against underdeveloped versions of the algo until you can beat them by loading up the weights at increasing stages of deveopment.

If you're curious how it would work, I implemented AlphaZero (but not Mu yet) using GBDTs instead of NNs here: https://github.com/cgreer/alpha-zero-boosted. Instead of saving the "weights" for a GBDT, you save the split points for the value/policy model trees, but the concept is the same.

I wish the code panel was collapsed by default on the repo home page, so that you could see the README section front and center.

That's usually the first thing I read. Then I dive into one or two files to check things out.

> because convolutional networks provide the right inductive bias for the problem of learning to play Go.

Agreed, seems like there will be a set of environments that GBDT won't work on and a CNN will. I'm only mildly familiar with CNNs, but one thing I wanted to try was to add convolutional features to a GBDT some way. I'm sure it's been tried and worked/failed before, but it would be an interesting exercise (at least for me) to learn why/if it works.

It'd be valuable if there was a way to get 95% of the benefits of CNNs (scale/position invariance, etc.) with less compute, even if the accuracy was lower. Right now the GBDT is probably making a ton of redundant split points for connect 4 to re-detect the same position-shifted pattern. There's gotta be a somewhat generalizable way to at least make that more efficient.

> such as symbolic manipulation tasks (I am in a good position to know this as I'm doing research in the area of automated theorem proving). I would be very curious to see how your approach fares for those tasks.

Definitely! I really want to see a non-game application. I think most people think of AlphaZero as "a cool technique to make SOTA board game agents", but to me it excites me because it seems like a very generalizable technique that'll be applied to other important types of problems.

I know as much as Jon Snow about symbolic manipulation, but if you have an example symbolic manipulation problem that can be shoehorned into an environment (state, actions, transitions, rewards) I'd be down to code it up and see how it does.

I'm trying to answer that right now, actually.

For connect 4, once it's trained a bit it seems to do really well. At 800 MCTS playouts (<.4s), it goes from "I can beat it and sometimes we draw" before training to "I pray for a draw, it almost always beats me" after ~4 hours of training.

Connect 4 is a solved game, so it should be possible to sample the space of the trillions of (position, who should win?, what are the best move(s)?) tuples and compare the answers to your value/policy models to get some kind of objective error. I haven't had time to do that, but having that benchmark is nice to have so you don't have to do a "ladder tournament" against some reference bot(s) like you do for Go where you don't know what ideal play is.

After training it for 10 hours on Quoridor (using my personal laptop), it still can't beat me, but it doesn't seem anywhere close to plateauing. It goes from the agents aimlessly wandering around the board looking for victory row and randomly placing walls, to putting walls that thwart the opponent and navigating to the victory row.

I decided to implement PCR and try out some self-play techniques on Connect Four before I give it another go for Quoridor; a few days of self-play improvements can speedup training 10x. That's where I'm at now...

Once I test a few strategies I was thinking of firing up a c5a24x, 96-core box on AWS and giving it another go. It's ~1-2$/hr at the spot price so I can probably do a lot of damage for 50$ or so.

> Are there any papers/comparisons/tradeoffs on when GBDT predictive-power plateaus compared to a NN?

None specifically that I know of, but I haven't searched.

"Shallow learning" GBDTs can do pretty well on MNIST (https://www.kaggle.com/c/digit-recognizer/discussion/61480), getting 98%+ accuracy compared to the 99%+ of NNs. So I figured if they can handle MNIST, they can probably handle connect 4, and would be useful to explore the self-play training efficiency aspects of AlphaZero (at orders of magnitude less compute time/cost)

> with self play you can trade-off a cpu budget for both the GBDT depth, a NN depth, and the roll-out depth - which is super interesting.

Definitely. It'll be interesting to see if a deeper MCTS search with a less powerful model can do pretty well. I'm still fairly ignorant about the MCTS literature, but I've definitely seen MCTS married to other value/policy models (linear regressions, for e.g.) that used large numbers of playouts years before Alpha Go came out. Those didn't work out, so seems like the DL aspect of Alpha Zero is somewhat essential to be able to learn games as complex as Go.

A fast, powerful bayesian model seems like it would be a game-changer. PUCT (the heart of the AlphaZero MCTS that decides which action to choose) really seems setup to model the action choices as a multinomial bayesian inference problem (it already updates the action priors with Dir noise).

Thanks for the link! I don't really know anything about the world of probabilistic trees. I'll check it out.

The only bayesian approach to decision trees I'm familiar with is BART (https://projecteuclid.org/download/pdfview_1/euclid.aoas/127...). I haven't used them, but I'm guessing because it uses MCMC to update the params it's not super fast. I've seen them used in causality applications for partial dependency plots where it's convenient to convey the certainty of a variable's effect.

I'll be sure to let you know how it goes. I have a few self-play experiments that I'm trying out once I get the testing setup finished.

Do you know if there is a discord channel for all of us AlphaZero nerds that I'm missing? If not, we should make one. It'd be great to bounce ideas off each other.

Here was the guestimation: https://www.yuzeh.com/data/agz-cost.html

I've been working on a Python implementation that uses Gradient Boosted Decision Trees (LightGBM/Treelite) instead of using a neural network for the value/policy models:

https://github.com/cgreer/alpha-zero-boosted

It's mostly to understand how AlphaZero&Friends work. I'm also curious about how well a GBDT could do, and if there are self-play techniques that can accelerate training.

The nice thing about a GBDT is that, unlike when using a NN, you can do thousands of value/policy lookups per second on a single core. So it should be cheaper to scale self-play and run a lot of self-play experiments (assuming the self-play learnings when using the GBDT model transfer to when you use the more-powerful NN in these environments).

If you're curious about accelerating self-play training, check out David Wu's work (https://arxiv.org/pdf/1902.10565.pdf). He's the creator of KataGo. I implemented his "Playout Cap Randomization" technique in my implementation above and, sure enough, it's much more efficient: https://imgur.com/a/epaKtDY. It seems like it's still early days in terms of how efficient self-play training is.