Stefan Richter [ARCHIVE] on Nostr: 📅 Original date posted:2021-11-15 📝 Original message: Actually, if you look ...
📅 Original date posted:2021-11-15
📝 Original message:
Actually, if you look into our paper, the theory tells us the following:
1) A weighted sum of different cost aspects is attractive because it
remains convex if all the aspects are convex themselves. This cannot be
said of other methods like the harmonic mean, which kind of forces our hand
if we aim to really calculate optimal flows.
2) even in the single path case, finding a route that optimizes one goal
(say, reliability) while ensuring that another cost aspect remains under
some boundary, is a (weakly) NP hard problem. My interpretation of this
fact is that while it is certainly possible to find suitable factors for
the linear combination (by, say, gradient descent methods), we cannot
expect a method that is simple and works for every conceivable graph every
time. In practice, we have observed that the factor needs to be varied over
multiple orders of magnitude to make a meaningful impact. Mapping this onto
an easy user interface (e.g. your suggestion of a linearly feeling value
between 0 and 1) will need some trial and error engineering, IMHO.
Cheers,
Stefan
René Pickhardt via Lightning-dev <lightning-dev at lists.linuxfoundation.org>
schrieb am Mo., 15. Nov. 2021, 12:50:
> 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
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20211115/42fe9021/attachment-0001.html>;
📝 Original message:
Actually, if you look into our paper, the theory tells us the following:
1) A weighted sum of different cost aspects is attractive because it
remains convex if all the aspects are convex themselves. This cannot be
said of other methods like the harmonic mean, which kind of forces our hand
if we aim to really calculate optimal flows.
2) even in the single path case, finding a route that optimizes one goal
(say, reliability) while ensuring that another cost aspect remains under
some boundary, is a (weakly) NP hard problem. My interpretation of this
fact is that while it is certainly possible to find suitable factors for
the linear combination (by, say, gradient descent methods), we cannot
expect a method that is simple and works for every conceivable graph every
time. In practice, we have observed that the factor needs to be varied over
multiple orders of magnitude to make a meaningful impact. Mapping this onto
an easy user interface (e.g. your suggestion of a linearly feeling value
between 0 and 1) will need some trial and error engineering, IMHO.
Cheers,
Stefan
René Pickhardt via Lightning-dev <lightning-dev at lists.linuxfoundation.org>
schrieb am Mo., 15. Nov. 2021, 12:50:
> 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
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20211115/42fe9021/attachment-0001.html>;