6 ms·

Trading with BDDs

83 points by taeric 4y ago

taeric 4y ago
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.
scaredginger 4y ago
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
- taeric 4y ago
  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.
  - derriz 4y ago
    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”.
    - taeric 4y ago
      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.
MuffinFlavored 4y ago
> 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".
- taeric 4y ago
  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?)
  - deleted 4y ago
    [deleted]
  - fedeb95 4y ago
    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.
    - taeric 4y ago
      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.
vlovich123 4y ago
There’s a bug in the first diagram for the rightmost node 6. Left edge everywhere else represents true but it ends in false.
- taeric 4y ago
  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?
svat 4y ago
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 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.
- taeric 4y ago
  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?
323 4y ago
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.
- taeric 4y ago
  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.
leethargo 4y ago
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/ https://www.andrew.cmu.edu/user/vanhoeve/mdd/
- taeric 4y ago
  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.
worik 4y ago
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.
- taeric 4y ago
  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.
taeric 4y ago
Finally got to where I could make some updates based on the feedback I got here. Thanks again to all that read it!

83 points by taeric 4y ago

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.

scaredginger 4y ago

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

taeric 4y ago
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.
- derriz 4y ago
  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”.
  - taeric 4y ago
    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.

MuffinFlavored 4y ago

> 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".

taeric 4y ago
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?)
- deleted 4y ago
  [deleted]
- fedeb95 4y ago
  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.
  - taeric 4y ago
    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.

vlovich123 4y ago

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

taeric 4y ago
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?

svat 4y ago

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 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.

taeric 4y ago
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?

323 4y ago

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.

taeric 4y ago
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.

leethargo 4y ago

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/ https://www.andrew.cmu.edu/user/vanhoeve/mdd/

taeric 4y ago
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.

worik 4y ago

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.

taeric 4y ago
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.

taeric 4y ago

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