{"type":"rich","version":"1.0","author_name":"npub1zlxd3xlzjhq2ue03e5m5p2w6mp8v3dkhq5r39flsftjjsje04wvsdd2k4w","author_url":"https://nostr.ae/npub1zlxd3xlzjhq2ue03e5m5p2w6mp8v3dkhq5r39flsftjjsje04wvsdd2k4w","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2021-11-15\n📝 Original message:\nDear Joost,\n\nFirst I am happy that you also agree that reliability can and should be\nexpressed as a probability as discussed in [0].\n\nThe problem that you address is that of feature engineering[1]. Which\nconsists of two (or even more) steps:\n\n1.) Feature selection: That means in payment delivery we will compute a min\ncost flow [2] with a chosen cost function (historically people used\ndijkstra seach for single paths with the cost function representing the\nweights on the edges of the graph -which is what most folks currently still\ndo). While [2] and I personally agree with you that the cost function\nshould be a combination the two features fees and reliability (as in\nsuccessprobability) Matt Corallo righfully pointed out [3] that other\nfeatures might be chosen in the future to deliver more optimal results. For\nexample implementations currently often use CLTV as a feature (which I\nhonestly find horrible) and I am currently investigating if one could add\nlatency of channels or - for known IP addresses - either the geo distance\nor IP distance.\n\n2.) Combining features: This is the question that you are asking. Often\npeople use a linear weighted sum to combine features. This is what often\nhappens implicitly in neural networks. While this is often good enough and\nwhile it is often practical to either learn the weights or give users a\nchoice there are many situation where the weighted linear sum does not work\nwell with the selected features. An example for the weighted sum is the\nrisk-factor in c-lightning that could have been used to decide if one\nwanted the dijkstra seach to either optimize for CLTV delta or for paid\nrouting fees. Also in our paper [2] in which we discuss the same two\nfeatures that you mentioned we explain how a linear sum of two features can\nbe optimal due to the lagrangian bounding principle. However in practice\n(of machine learning) it has been shown that using the harmonic mean [4]\nbetween features often works very well without the necessity to learn a\nweight / parameter. This has for example been done when c-lightnign\nrecently switched to probabilistic path finding [5]. In this thread you\nfind a long discussion and evaluation how the harmonic mean outperformed\nthe linear sum.\n\nI think the main issue that you address here is that there is no universal\ntruth for situations like this. In practice only tests and experience will\nhelp us to make good decisions.\n\nwith kind Regards Rene\n\n[0]:\nhttps://lists.linuxfoundation.org/pipermail/lightning-dev/2021-March/002984.html\n[1]: https://en.wikipedia.org/wiki/Feature_engineering\n[2]: https://arxiv.org/abs/2107.05322\n[3]:\nhttps://lists.linuxfoundation.org/pipermail/lightning-dev/2021-September/003219.html\n[4]:  https://en.wikipedia.org/wiki/Harmonic_mean\n[5]: https://github.com/ElementsProject/lightning/pull/4771\n\n\n\n\nOn Mon, Nov 15, 2021 at 4:26 PM Joost Jager \u003cjoost.jager at gmail.com\u003e wrote:\n\n\u003e In Lightning pathfinding the two main variables to optimize for are\n\u003e routing fee and reliability. Routing fee is concrete. It is the sat amount\n\u003e that is paid when a payment succeeds. Reliability is a property of a route\n\u003e that can be expressed as a probability. The probability that a route will\n\u003e be successful.\n\u003e\n\u003e During pathfinding, route options are compared against each other. So for\n\u003e example:\n\u003e\n\u003e Route A: fee 10 sat, success probability 50%\n\u003e Route B: fee 20 sat, success probability 80%\n\u003e\n\u003e Which one is the better route? That depends on user preference. A patient\n\u003e user will probably go for route A in the hope of saving on fees whereas for\n\u003e a time-sensitive payment route B looks better.\n\u003e\n\u003e It would be great to offer this trade-off to the user in a simple way.\n\u003e Preferably a single [0, 1] value that controls the selection process. At 0,\n\u003e the route is only optimized for fees and probabilities are ignored\n\u003e completely. At 1, the route is only optimized for reliability and fees are\n\u003e ignored completely.\n\u003e\n\u003e But how to choose between the routes A and B for a value somewhere in\n\u003e between 0 and 1? For example 0.5 - perfect balance between reliability and\n\u003e fee. But what does that mean exactly?\n\u003e\n\u003e Anyone got an idea on how to approach this best? I am looking for a simple\n\u003e formula to decide between routes, preferably with a reasonably sound\n\u003e probability-theoretical basis (whatever that means).\n\u003e\n\u003e Joost\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\n\n-- \nhttps://www.rene-pickhardt.de\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20211115/392fcbf0/attachment-0001.html\u003e"}