Trading with BDDs | Hacker News Reader

Trading with BDDs

taeric.github.io

83 pointstaeric24 comments

I enjoyed this post, thank you! For the benefit of anyone else reading, some context that I felt would have helped: The toy problem being considered is the following. You are given a sequence of historical prices (of a single stock or index or whatever), one for each day:

    day   1  2  3  ... n
    price p1 p2 p3 ... pn

The task is to annotate each day i with a (retroactive) decision z_i ∈ {buy, sell, do nothing}, and do this optimally, subject to the constraint that you cannot sell before you buy, cannot "buy" twice without an intervening "sell" and vice-versa, etc. And there are indeed dynamic-programming algorithms to solve this quickly, which you can find on Leetcode writeups and whatnot.

(Whether or not this has any resemblance to real-world trading is not the point of the toy problem, which is about computational techniques. See e.g. Knuth's article “Are toy problems useful?” from Chapter 10 of https://cs.stanford.edu/~knuth/cs.html, or “Puzzles versus the real world” on pages 7–9 of TAOCP Vol 4A.)

Another way to model it is with two-valued y_i ∈ {do nothing, "change state"}, where "change state" means buy if you haven't bought and sell if you have, with the last day's decision forced (you have to end in the sold state), which shows why there are 2^{n-1} possibilities to optimize over.

But there's yet another way of modeling the problem, presented in this post, where we have 2n-2 boolean variables x1, x2, x3, x4, … denoting respectively the choices of whether or not to "buy on day 1", "sell on day 2", "buy on day 2", "sell on day 3", and so on, and now the problem becomes one of the form:

    maximize w1x1 + w2x2 + w3x3 + …
    such that f(x1, x2, x3, ...) = 1

where f is a boolean function denoting whether the 0-1 values assigned to the x_i variables is "valid" (does not have both buy and sell on the same date, has a buy before a sell, etc).

Now, this may seem hard to optimize over, but BDDs (binary decision diagrams) are a data structure that can represent such functions compactly, and in this case (because of the problem structure) the entire truth table (over all possible 2^{2n-2} assignments to xi, with 2^{n-1} "true" values among them) can be represented as a BDD with 2.5n nodes, and with a standard algorithm can be optimized over.

This gives an algorithm that is just as fast as the dynamic programming algorithm (almost? asymptotically?), and is a fun exercise to play with BDDs, which this post describes very well.

Thanks! Better description of the toy than I put on the page. :)

I haven't used a bdd before, so I was surprised this worked as well as it did. I haven't tried this with DP, but the solutions I saw that did weren't able to handle this much data. I'm assuming I just saw sub optimal solutions?

I might be misunderstanding the problem statement, but my take:

My impression is that for N max trades and M days of data, the "obvious" DP solution should be 2*N entries and O(NM) time, by tracking best profit for n trades whether you have the stock, where your update looks something like profit[trade_count=n, day=m, has_stock] = max(profit[trade_count=n, day=m-1, has_stock], profit[trade_count=n-1, day=n-1, has_stock] + transaction_cost[day=n, has_stock]) -- namely, as you've described in the article, either do nothing, or make a trade. Of course, you wouldn't store the full history -- you'd only need yesterday's data and today's update.

Adding accounting to track the trade history is doable without bloating runtime too much, but it does increase space usage substantially.

That said, if you don't have to keep to a strict number of trades, the DP solution should be able to fit in constant space (well, linear in number of days if you want to keep track of history for the best sequence of trades).

I really like the idea in the article of adding a transaction cost and varying that to constrict the number of trades -- it reminds me of a cooling schedule for simulated annealing, and it's definitely not an approach I see interview candidates reaching for regularly.

That all sounds reasonable. I'm not sure what the solutions I saw were trying. They definitely went slower, though. Hours for one of the solutions I saw.

I didn't post this as a "show hn," as I wasn't sure it counted for that. I'd be delighted to know if anything I did wrong in this. Was fun, regardless.

> Binary Decision Diagrams (BDDs)

where does intraday/momentum/swing trading fit into this? like little “algorithms” looking at indicators or "open/high/low/close" candles + volume to pick direction, entry, stop loss/limit?

i’ve seen something that looks at things like VWAP/EMA fast/slow crossover and then pours into 0 days to expiration. “guessing/following” the market along for a 0.5% move in the index can turn into 100-500% ROI in options. obviously has its drawbacks/isn't perfect.

i always felt the results with "trading" (given how market the random is overall) aren't worth it.

i'd be curious how the results of this compare to basic "technical analysis".

Agreed that this isn't worth much as a legit trading algorithm. That is the framing I was given to the puzzle.

With how fast this answers the question of the boolean linear program, I suspect it could be used for some neat tricks. That said, if you try to make the decision diagram smarter, it tends to explode in size. (At least, I think it does?)

For size I read there are ways to reduce and/or compress BDDs in literature. As for trading, I get this is a neat programming exercise, but maybe it's better to put in the article a disclaimer on it not being a real trading strategy? Set aside skepticism on trading strategies as a whole.

Yes, variable order, in particular, can have a dramatic impact on size. With just 5 nodes per day, I think this may be hard to make smaller. I got lucky with not having to reduce this one after I create it.

Got a lot of feedback yesterday, but house was without power, so couldn't update post before we left. Will try to get some updates in when I'm back home in a few days. Biggest one is to more clearly label this as a toy problem.

is there even such thing as a publicly available/known "trading strategy" that actually wins more than it loses?

Well, some claim to have it. I think it can be true, until it isn't

A great resource for optimization with decision diagrams is the website by Willem-Jan van Hoeve from Carnegie Mellon [1].

They go beyond binary (the M in MDD stands for multi-valued) and they derive primal heuristics and relaxations from cropped/merged diagrams of bounded size.

[1] https://www.andrew.cmu.edu/user/vanhoeve/mdd/

Thanks! I have been curious why random forests and such can't be made a bit more linear on their inputs. When I first read of BDDs, I assumed the same ordering and such was used on all decision trees. Clearly, I was wrong.

It would be nice to understand what you're trying to find here. What are the constraints?

Do I have to start and end with a neutral position? Am I allowed to short; i.e. do I have to buy before I sell? What are the limits on liquidity? Do I have unlimited access to margin? Is there a limit on holding time? Are there any borrowing costs? Are there any transaction costs?

All these should be addressed in the problem definition

Ah, apologies. I will try to get that added today

Basic answer is that you can only have one outstanding buy, and must end with no open trade. My understanding is this is/was a common interview style question.

Your terminology is confusing as I think you’re using technical terms (“trade”, “open”, etc) in a way that does not reflect their usual meaning. A “trade” generally refers to an event not state, while I think you want to refer to “position” which is a component of trading state. E.g. by “ending with no open trade”, you mean ending with no position or “flat”.

That makes sense. I thought I lifted the words from others, such that I didn't think I was making up any terms. Will try to scrub all terms and describe things directly.

Finally got to where I could make some updates based on the feedback I got here. Thanks again to all that read it!

One big conceptual problem is that you can't use the technology of today to trade on 1980 prices.

So showing big profits on decades old prices is meaningless, the market was much "softer" back than since there was little machine learning, large clean datasets, very accessible computation power, and so on.

Agreed. And, in general, I don't like this toy problem. Largely because of how silly it is. I did like getting a fast solution using a technique new to me, though.

There’s a bug in the first diagram for the rightmost node 6. Left edge everywhere else represents true but it ends in false.

The dotted line is false for the variable. If you have an outstanding trade, puzzle is you have to sell on the last day. So, false for that day would not be allowed if you have an open buy, right?

Really? More technical analysis?

It does not work, in the general case.

Simply put the efficient market hypothesis is true, in most cases, for most people, in most markets.

It is possible (I know of two cases: pairs trading in stock markets and momentum trading in bond markets) where it has had success for finite periods of time.

What ever goodness can be found is traded away by very sharp and well resources actors before anybody else can get to them.

It is a zero sum game, and the game has some very well resourced actors in it that want very much for you to put all your money into technical trading, thank you. They are crooks and thieves, and include some of the richest people on the planet.

This is like astrology, homoeopathy, aroma therapy... If it seems it works it s for some other reason.

Stay well clear of this hocus pocus. So many computer people gone down this road. The only way to make money out of technical trading is to get paid a salary to implement some one else's algorithm.

I've been sans power today, so haven't done updates. In general, though, I do plan on updating to say this is more fun with a toy program and data structure. Decidedly not an actual trading strategy.

Reply on news.ycombinator.com