📅 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>;
Stefan Richter [ARCHIVE] /
npub19f…f4wf0
2023-06-09 15:04:25
in reply to nevent1q…vt7y
Author Public Key
npub19fnl48y9j4fk9w0a284mqvszq6fuppelqp2tcxf0s37l95avdtussf4wf0Published at
2023-06-09 15:04:25Event JSON
{
"id": "a38e2e7f466fadb5553e6d77f08f67782f1015b40bf320f30ae3b796b81bf624",
"pubkey": "2a67fa9c85955362b9fd51ebb032020693c0873f0054bc192f847df2d3ac6af9",
"created_at": 1686315865,
"kind": 1,
"tags": [
[
"e",
"ff2b02f52b6bf2ba44fad040ebd04a11cbcc61fa7b8b2822e2b9132801128989",
"",
"root"
],
[
"e",
"125731b5f3a97e6a1ea8367378efc33f32742d3f430eb47588265212ee988d29",
"",
"reply"
],
[
"p",
"4505072744a9d3e490af9262bfe38e6ee5338a77177b565b6b37730b63a7b861"
]
],
"content": "📅 Original date posted:2021-11-15\n📝 Original message:\nActually, if you look into our paper, the theory tells us the following:\n\n1) A weighted sum of different cost aspects is attractive because it\nremains convex if all the aspects are convex themselves. This cannot be\nsaid of other methods like the harmonic mean, which kind of forces our hand\nif we aim to really calculate optimal flows.\n\n2) even in the single path case, finding a route that optimizes one goal\n(say, reliability) while ensuring that another cost aspect remains under\nsome boundary, is a (weakly) NP hard problem. My interpretation of this\nfact is that while it is certainly possible to find suitable factors for\nthe linear combination (by, say, gradient descent methods), we cannot\nexpect a method that is simple and works for every conceivable graph every\ntime. In practice, we have observed that the factor needs to be varied over\nmultiple orders of magnitude to make a meaningful impact. Mapping this onto\nan easy user interface (e.g. your suggestion of a linearly feeling value\nbetween 0 and 1) will need some trial and error engineering, IMHO.\n\nCheers,\n Stefan\n\n\nRené Pickhardt via Lightning-dev \u003clightning-dev at lists.linuxfoundation.org\u003e\nschrieb am Mo., 15. Nov. 2021, 12:50:\n\n\u003e Dear Joost,\n\u003e\n\u003e First I am happy that you also agree that reliability can and should be\n\u003e expressed as a probability as discussed in [0].\n\u003e\n\u003e The problem that you address is that of feature engineering[1]. Which\n\u003e consists of two (or even more) steps:\n\u003e\n\u003e 1.) Feature selection: That means in payment delivery we will compute a\n\u003e min cost flow [2] with a chosen cost function (historically people used\n\u003e dijkstra seach for single paths with the cost function representing the\n\u003e weights on the edges of the graph -which is what most folks currently still\n\u003e do). While [2] and I personally agree with you that the cost function\n\u003e should be a combination the two features fees and reliability (as in\n\u003e successprobability) Matt Corallo righfully pointed out [3] that other\n\u003e features might be chosen in the future to deliver more optimal results. For\n\u003e example implementations currently often use CLTV as a feature (which I\n\u003e honestly find horrible) and I am currently investigating if one could add\n\u003e latency of channels or - for known IP addresses - either the geo distance\n\u003e or IP distance.\n\u003e\n\u003e 2.) Combining features: This is the question that you are asking. Often\n\u003e people use a linear weighted sum to combine features. This is what often\n\u003e happens implicitly in neural networks. While this is often good enough and\n\u003e while it is often practical to either learn the weights or give users a\n\u003e choice there are many situation where the weighted linear sum does not work\n\u003e well with the selected features. An example for the weighted sum is the\n\u003e risk-factor in c-lightning that could have been used to decide if one\n\u003e wanted the dijkstra seach to either optimize for CLTV delta or for paid\n\u003e routing fees. Also in our paper [2] in which we discuss the same two\n\u003e features that you mentioned we explain how a linear sum of two features can\n\u003e be optimal due to the lagrangian bounding principle. However in practice\n\u003e (of machine learning) it has been shown that using the harmonic mean [4]\n\u003e between features often works very well without the necessity to learn a\n\u003e weight / parameter. This has for example been done when c-lightnign\n\u003e recently switched to probabilistic path finding [5]. In this thread you\n\u003e find a long discussion and evaluation how the harmonic mean outperformed\n\u003e the linear sum.\n\u003e\n\u003e I think the main issue that you address here is that there is no universal\n\u003e truth for situations like this. In practice only tests and experience will\n\u003e help us to make good decisions.\n\u003e\n\u003e with kind Regards Rene\n\u003e\n\u003e [0]:\n\u003e https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-March/002984.html\n\u003e [1]: https://en.wikipedia.org/wiki/Feature_engineering\n\u003e [2]: https://arxiv.org/abs/2107.05322\n\u003e [3]:\n\u003e https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-September/003219.html\n\u003e [4]: https://en.wikipedia.org/wiki/Harmonic_mean\n\u003e [5]: https://github.com/ElementsProject/lightning/pull/4771\n\u003e\n\u003e\n\u003e\n\u003e\n\u003e On Mon, Nov 15, 2021 at 4:26 PM Joost Jager \u003cjoost.jager at gmail.com\u003e wrote:\n\u003e\n\u003e\u003e In Lightning pathfinding the two main variables to optimize for are\n\u003e\u003e routing fee and reliability. Routing fee is concrete. It is the sat amount\n\u003e\u003e that is paid when a payment succeeds. Reliability is a property of a route\n\u003e\u003e that can be expressed as a probability. The probability that a route will\n\u003e\u003e be successful.\n\u003e\u003e\n\u003e\u003e During pathfinding, route options are compared against each other. So for\n\u003e\u003e example:\n\u003e\u003e\n\u003e\u003e Route A: fee 10 sat, success probability 50%\n\u003e\u003e Route B: fee 20 sat, success probability 80%\n\u003e\u003e\n\u003e\u003e Which one is the better route? That depends on user preference. A patient\n\u003e\u003e user will probably go for route A in the hope of saving on fees whereas for\n\u003e\u003e a time-sensitive payment route B looks better.\n\u003e\u003e\n\u003e\u003e It would be great to offer this trade-off to the user in a simple way.\n\u003e\u003e Preferably a single [0, 1] value that controls the selection process. At 0,\n\u003e\u003e the route is only optimized for fees and probabilities are ignored\n\u003e\u003e completely. At 1, the route is only optimized for reliability and fees are\n\u003e\u003e ignored completely.\n\u003e\u003e\n\u003e\u003e But how to choose between the routes A and B for a value somewhere in\n\u003e\u003e between 0 and 1? For example 0.5 - perfect balance between reliability and\n\u003e\u003e fee. But what does that mean exactly?\n\u003e\u003e\n\u003e\u003e Anyone got an idea on how to approach this best? I am looking for a\n\u003e\u003e simple formula to decide between routes, preferably with a reasonably sound\n\u003e\u003e probability-theoretical basis (whatever that means).\n\u003e\u003e\n\u003e\u003e Joost\n\u003e\u003e _______________________________________________\n\u003e\u003e Lightning-dev mailing list\n\u003e\u003e Lightning-dev at lists.linuxfoundation.org\n\u003e\u003e https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev\n\u003e\u003e\n\u003e\n\u003e\n\u003e --\n\u003e https://www.rene-pickhardt.de\n\u003e _______________________________________________\n\u003e Lightning-dev mailing list\n\u003e Lightning-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev\n\u003e\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20211115/42fe9021/attachment-0001.html\u003e",
"sig": "6e55d1eb1564f1acc56034e926a3a197daf3772deb3d4eaca6e37322310616ab154e377c3f514c87c21785ee0453bec4c1049b4154e7d75d3b0bf2eb0afc0516"
}