René Pickhardt [ARCHIVE] on Nostr: 📅 Original date posted:2021-11-15 📝 Original message: Dear Joost, First I am ...
📅 Original date posted:2021-11-15
📝 Original message:
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.jager at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
--
https://www.rene-pickhardt.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20211115/392fcbf0/attachment-0001.html>;
📝 Original message:
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.jager at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
--
https://www.rene-pickhardt.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20211115/392fcbf0/attachment-0001.html>;