Dear Joost, First I am happy that you also agree that reliability can and should be expressed as a probability as discussed in [0].
The problem that you address is that of feature engineering[1]. Which consists of two (or even more) steps: 1.) Feature selection: That means in payment delivery we will compute a min cost flow [2] with a chosen cost function (historically people used dijkstra seach for single paths with the cost function representing the weights on the edges of the graph -which is what most folks currently still do). While [2] and I personally agree with you that the cost function should be a combination the two features fees and reliability (as in successprobability) Matt Corallo righfully pointed out [3] that other features might be chosen in the future to deliver more optimal results. For example implementations currently often use CLTV as a feature (which I honestly find horrible) and I am currently investigating if one could add latency of channels or - for known IP addresses - either the geo distance or IP distance. 2.) Combining features: This is the question that you are asking. Often people use a linear weighted sum to combine features. This is what often happens implicitly in neural networks. While this is often good enough and while it is often practical to either learn the weights or give users a choice there are many situation where the weighted linear sum does not work well with the selected features. An example for the weighted sum is the risk-factor in c-lightning that could have been used to decide if one wanted the dijkstra seach to either optimize for CLTV delta or for paid routing fees. Also in our paper [2] in which we discuss the same two features that you mentioned we explain how a linear sum of two features can be optimal due to the lagrangian bounding principle. However in practice (of machine learning) it has been shown that using the harmonic mean [4] between features often works very well without the necessity to learn a weight / parameter. This has for example been done when c-lightnign recently switched to probabilistic path finding [5]. In this thread you find a long discussion and evaluation how the harmonic mean outperformed the linear sum. I think the main issue that you address here is that there is no universal truth for situations like this. In practice only tests and experience will help us to make good decisions. with kind Regards Rene [0]: https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-March/002984.html [1]: https://en.wikipedia.org/wiki/Feature_engineering [2]: https://arxiv.org/abs/2107.05322 [3]: https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-September/003219.html [4]: https://en.wikipedia.org/wiki/Harmonic_mean [5]: https://github.com/ElementsProject/lightning/pull/4771 On Mon, Nov 15, 2021 at 4:26 PM Joost Jager <joost.ja...@gmail.com> wrote: > In Lightning pathfinding the two main variables to optimize for are > routing fee and reliability. Routing fee is concrete. It is the sat amount > that is paid when a payment succeeds. Reliability is a property of a route > that can be expressed as a probability. The probability that a route will > be successful. > > During pathfinding, route options are compared against each other. So for > example: > > Route A: fee 10 sat, success probability 50% > Route B: fee 20 sat, success probability 80% > > Which one is the better route? That depends on user preference. A patient > user will probably go for route A in the hope of saving on fees whereas for > a time-sensitive payment route B looks better. > > It would be great to offer this trade-off to the user in a simple way. > Preferably a single [0, 1] value that controls the selection process. At 0, > the route is only optimized for fees and probabilities are ignored > completely. At 1, the route is only optimized for reliability and fees are > ignored completely. > > But how to choose between the routes A and B for a value somewhere in > between 0 and 1? For example 0.5 - perfect balance between reliability and > fee. But what does that mean exactly? > > Anyone got an idea on how to approach this best? I am looking for a simple > formula to decide between routes, preferably with a reasonably sound > probability-theoretical basis (whatever that means). > > Joost > _______________________________________________ > Lightning-dev mailing list > Lightning-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > -- https://www.rene-pickhardt.de
_______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
