アルゴリズムの魔術: 外国為替におけるグラフ理論の活用

FinTech スタートアップ業界に詳しい方なら、イギリスのロンドンに拠点を置く有名な FinTech 大手企業 Revolut について聞いたことがあるかもしれません。 2015 年に設立された Revolut は多額の投資を集め、英国で最も急速に成長している新興企業の 1 つとなり、多くの欧州国民に銀行サービスを提供しています。 銀行業務は収益をどのように生み出しているかという点では謎に包まれていることが多いが、2020年と2021年のRevolutに関するいくつかの重要な数字は、その収入源にいくらかの光を当てている。 図に示すように、このネオバンクの収益のかなりの部分は、外国為替 (FX)、資産管理 (仮想通貨を含む)、およびカード サービスから来ています。注目すべきは、2021年にFXが最も収益性の高いセクターとなったことです。 ソフトウェア エンジニアでもある私の友人は、数年前に Revolut のソフトウェア エンジニアリング部門で技術面接を受けたときの興味深い話をしてくれました。彼は、1 つまたは複数の中間通貨を使用して 2 つの通貨を交換する最も収益性の高い方法を特定するアルゴリズムを開発する任務を負っていました。言い換えれば、彼らは通貨裁定取引の戦略を探していたのです。 は、通貨トレーダーが複数の取引を通じて特定の通貨ペアに対してブローカーによって提供されるさまざまなスプレッドを活用する取引戦略です。 通貨アービトラージ アルゴリズムの基礎はグラフ理論に根ざしている必要があることがタスクで明確に述べられました。 FXの基礎 FX (外国為替) は世界貿易において極めて重要な役割を果たし、相互につながった世界の機能を支えています。銀行を最も裕福な組織にする上で、為替も重要な役割を果たしているのは明らかです。 外国為替から生じる利益は主に、買値 (BID) と売値 (ASK) の差またはスプレッドです。この差は、トランザクションごとにわずかに見えるかもしれませんが、毎日の操作量を考慮すると、累積すると数百万ドルの利益になる可能性があります。これにより、一部の企業は高度に自動化された財務業務だけで成長できるようになります。 FX (外国為替) の分野では、常に EUR/USD などの通貨ペアを扱います。ほとんどの場合、これらの為替は双方向 (つまり、EUR/USD および USD/EUR) であり、為替レートの値は各方向で異なります。 2 つの通貨 (たとえば、ユーロと米ドル) の価値間の比率を数値で表し、通貨間の為替レートを決定します。 アービトラージ ペアは、 可能性としては、 として知られる、収益性の高い取引のために複数の中間通貨を使用できる可能性があります。 確実な賭け 循環的に使用される一連のペアです。 アービトラージ シュア ベットは、 続きを読む 多くのプロバイダーは、自社の利益を確保し、他のプロバイダーがそこから利益を得ることを防ぐために、数学的モデリングと分析を採用しています。したがって、ここでは「潜在的」という用語が強調されています。 潜在的な裁定取引の機会のセットを構成するペアの数を指します。 確実なベットの長さは、 現実の世界では、為替レートは銀行や為替プラットフォームによって異なる場合があります。旅行者が可能な限り最良の料金を見つけるために都市を横断することは珍しくありません。コンピューター ソフトウェアを使用すると、プロバイダーのリストにアクセスできる場合、このプロセスは数ミリ秒以内に実行できます。 実際の収益性の高い取引では、複数のステップで、さまざまな取引所プラットフォームにわたるさまざまな通貨を介した変換が含まれる場合があります。言い換えれば、裁定サークルは非常に広範囲に及ぶ可能性があります。 では、通貨を取得し、それを別のプラットフォームに転送し、他の通貨と交換し、最終的には元の通貨に戻します。 アービトラージサークル 1 つ以上の中間通貨を介した 2 つの通貨間の為替レートは として計算されます。 、これらの中間取引の為替レートの積 例 たとえば、スイスのフランクを米ドルで購入し、次にフランクを日本円に交換し、さらに円を米ドルで売却するとします。 2023 年秋の為替レートは次のとおりです。 1 USD で 0.91 CHF (スイス フランク) を購入できます。 1スイスフランで163.16円で買えます。 1日本円で0.0067米ドルが購入できます。 それを表で示してみましょう。 1 USD | 1 CHF | 1 YEN 0.91 CHF | 163.16 YEN | 0.0067 USD ----------------|-------------------|-------------- 1.098901099 | 0.006128953 | 149.2537313 次に、これらの値の積を見つける必要があります。 。 この積が 1 未満の値を生成する場合、一連のトランザクションは利益をもたらします 1.098901099 * 0.006128953 * 149.2537313 = 1.005240803 ご覧のとおり、結果は 1 より大きいため、資金の 0.05% を失ったようです。しかし、正確には何個でしょうか？次のように整理できます。 0.91 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 0.99478652 US Dollars したがって、最初に 1 米ドルを販売した後、最終的には 0.994 を手に入れました。これは 1 米ドル未満です。 簡単に言うと、裁定サイクルは、同じ通貨の 1 単位未満で 1 単位の通貨を取得できる場合に利益が得られます。 最初のトランザクションで 1 米ドルあたり 0.91 スイスフランではなく、0.92 スイスフランを受け取る機会を見つけたと想像してみましょう。 1 USD | 1 CHF | 1 YEN 0.92 CHF | 163.16 YEN | 0.0067 USD ----------------|-------------------|-------------- 1.086956522 | 0.006128953 | 149.2537313 製品は 1 未満になります。 1.086956522 * 0.006128953 * 149.2537313 = 0.994314272 つまり、実際の通貨では 1 米ドル以上の価値が得られることになります。 0.92 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 1.00571824 US Dollars うわー、 次に、グラフ分析を使用してこれを自動化する方法を見てみましょう。 利益が出ました！ したがって、3 つのアービトラージ ペアのアービトラージ サークルで利益または損失を確認する式は次のようになります。 USD/CHF * CHF/YEN * YEN/USD < 1.0 グラフ表現 これらのプロセスを自動化するには、グラフを使用できます。前述のテーブルは、ノードが通貨を表し、エッジが双方向の交換を表すグラフの行列表現に自然に変換できます。 したがって、次のように 2 つのペアの交換を行列で表すのは簡単です。 EUR USD 1 1 EUR 1 1 USD 関与するペアの数に応じて、行列は次のように拡張できます。 EUR USD YEN CHF 1 1 1 1 EUR 1 1 1 1 USD 1 1 1 1 YEN 1 1 1 1 CHF したがって、より多くの交換プラットフォームとリソースを考慮すると、たとえ 2 つの通貨であっても、テーブルがかなり大きくなる可能性があります。 現実の通貨裁定取引の問題に対処するために、通貨相場のすべての関係を網羅する完全なグラフがよく利用されます。 3 通貨為替テーブルは次のようになります。 USD CHF YEN { 1.0, 1.10, 0.0067 } USD { 0.91, 1.0, 0.0061 } CHF { 148.84, 163.16, 1.0 } YEN 単純な を使用して、メモリ内の通貨ペアを表すことができます。 グラフ データ構造 class GraphNode { public: string Name; }; class Graph { public: vector > Matrix; vector Nodes; }; ここで必要なのは、このグラフをたどって最も収益性の高い円を見つける方法を見つけることだけです。しかし、まだ問題が1つあります... 数学がまた私たちを救う 古典的な アルゴリズムは 積を扱うのにはあまり適していません ( のよく知られた古典的な経路探索アルゴリズムの実装を参照してください) ）。 グラフ 、辺の長さの合計として定義されたパスを見つけるように設計されているため、辺の長さの BFS、DFS、ダイクストラなど Aスター ただし、この制限を回避するには、積から和に変換する数学的な方法、つまり対数があります。積が対数で表される場合は、対数の合計に変換できます。 この方程式の右側では、必要な数値は 1 未満であり、この数値の対数はゼロ未満でなければならないことを示しています。 LogE(USD/CHF) * LogE(CHF/YEN) * LogE(YEN/USD) < 0.0 この単純な数学的トリックにより、エッジ長の 1 未満のサイクルの検索 移行することができます。 積が から、エッジ長の合計が 0 未満のサイクルの検索に 行列の値を LogE(x) に変換し、小数点以下 2 桁で四捨五入すると、次のようになります。 USD CHF YEN { 0.0, 0.1, -5.01 } USD { -0.09, 0.0, -5.1 } CHF { 5.0, 5.09, 0.0 } YEN この問題は、古典的なグラフ アルゴリズムを使用することでより解決可能になります。必要なのは、グラフを横断して最も収益性の高い交換経路を探すことです。 グラフアルゴリズム どのアルゴリズムにも限界があります。それらのいくつかについては で説明しました。 、前の記事 グラフには負の重みが含まれている可能性があり、グラフを横断するときに が発生する可能性があるため、ここでは古典的な BFS、DFS、さらにはダイクストラを適用することはできません。アルゴリズムは反復ごとにより良い解決策を継続的に見つけるため、負のサイクルはアルゴリズムに課題をもたらします。 負のサイクル この問題に対処するために、ベルマン-フォード アルゴリズムは単純に反復回数を制限します。これは、グラフの各エッジを 1 サイクルで走査し、すべてのエッジに V-1 回以下の緩和を適用します (V はノードの数です)。 したがって、ベルマン・フォード アルゴリズムは、このアービトラージ システムの中心にあり、2 つの重要な基準を満たすグラフ内の 2 つのノード間のパスの発見を可能にします。つまり、それらのアルゴリズムには負の重みが含まれており、負のサイクルの一部ではありません。 このアルゴリズムは理論的には簡単ですが (それに関するビデオが何億億もあります)、ニーズに合わせて実際に実装するにはある程度の努力が必要です。それを掘り下げてみましょう。 ベルマン・フォードアルゴリズムの実装 この記事の目的はコンピュータサイエンスであるため、実際の為替レートとは関係のない架空の為替レートを使用します。 アルゴリズムをよりスムーズに理解するために、負のサイクルがまったく含まれていないグラフを使用してみましょう。 graph.Nodes.push_back({ "USD" }); graph.Nodes.push_back({ "CHF" }); graph.Nodes.push_back({ "YEN" }); graph.Nodes.push_back({ "GBP" }); graph.Nodes.push_back({ "CNY" }); graph.Nodes.push_back({ "EUR" }); // Define exchange rates for pairs of currencies below // USD CHF YEN GBP CNY EUR graph.Matrix = { { 0.0, 0.41, INF, INF, INF, 0.29 }, // USD { INF, 0.0, 0.51, INF, 0.32, INF }, // CHF { INF, INF, 0.0, 0.50, INF, INF }, // YEN { 0.45, INF, INF, 0.0, INF, -0.38 }, // GBP { INF, INF, 0.32, 0.36, 0.0, INF }, // CNY { INF, -0.29, INF, INF, 0.21, 0.0 } }; // EUR 以下のコード例では、グラフに負のサイクルがない場合に、Bellman-Ford アルゴリズムを使用して 2 つのノード間のパスを見つけます。 vector _shortestPath; vector _previousVertex; void FindPath(Graph& graph, int start) { int verticesNumber = graph.Nodes.size(); _shortestPath.resize(verticesNumber, INF); _previousVertex.resize(verticesNumber, -1); _shortestPath[start] = 0; // For each vertex, apply relaxation for all the edges V - 1 times. for (int k = 0; k _shortestPath[from] + graph.Matrix[from][to]) { _shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to]; _previousVertex[to] = from; } } 中国人民元に対してこのコードを実行すると、 配列が埋められ、次のような結果が得られます。 _previousVertex Path from 4 to 0 is : 4(CNY) 3(GBP) 0(USD) Path from 4 to 1 is : 4(CNY) 3(GBP) 5(EUR) 1(CHF) Path from 4 to 2 is : 4(CNY) 3(GBP) 5(EUR) 1(CHF) 2(YEN) Path from 4 to 3 is : 4(CNY) 3(GBP) Path from 4 to 4 is : 4(CNY) Path from 4 to 5 is : 4(CNY) 3(GBP) 5(EUR) ご覧のとおり、CNY と他のさまざまな通貨の間の最適なパスが特定されます。 繰り返しますが、最適なものを 1 つだけ見つけることには焦点を当てません。これは比較的単純なタスクであり、この記事の目的ではないためです。 上記の実装は、理想的な場合にはうまく機能しますが、負のサイクルを含むグラフを扱う場合には不十分です。 負のサイクルの検出 本当に必要なのは、グラフに負のサイクルが含まれているかどうかを特定し、含まれている場合は問題のあるセグメントを特定する機能です。この知識により、これらの問題を軽減し、最終的に収益性の高いチェーンを発見することができます。 反復回数は、常に正確に V - 1 に達する必要はありません。(N+1) 番目のサイクルで、N 番目のサイクルでのパスよりも優れたパスが発見されない場合、解は見つかったとみなされます。したがって、わずかに最適化の余地があります。 前述のコードは、パスを見つけるだけでなく、グラフに負のサイクルが含まれているかどうかを検出するように拡張できます。これには、前述した最適化も含まれます。 vector _shortestPath; vector _previousVertex; bool ContainsNegativeCycles(Graph& graph, int start) { int verticesNumber = graph.Nodes.size(); _shortestPath.resize(verticesNumber, INF); _previousVertex.resize(verticesNumber, -1); _shortestPath[start] = 0; // For each vertex, apply relaxation for all the edges V - 1 times. for (int k = 0; k _shortestPath[from] + graph.Matrix[from][to]) { _shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to]; _previousVertex[to] = from; updated = true; } } } if (!updated) // No changes in paths, means we can finish earlier. break; } // Run one more relaxation step to detect which nodes are part of a negative cycle. if (updated) for (int from = 0; from _shortestPath[from] + graph.Matrix[from][to]) // A negative cycle has occurred if we can find a better path beyond the optimal solution. return true; return false; } そして今度は、負のサイクルを含むより複雑なグラフを使ってみましょう。 graph.Nodes.push_back({ "USD" }); // 1 (Index = 0) graph.Nodes.push_back({ "CHF" }); graph.Nodes.push_back({ "YEN" }); graph.Nodes.push_back({ "GBP" }); graph.Nodes.push_back({ "CNY" }); graph.Nodes.push_back({ "EUR" }); graph.Nodes.push_back({ "XXX" }); graph.Nodes.push_back({ "YYY" }); // 8 (Index = 7) // USD CHF YEN GBP CNY EUR XXX YYY graph.Matrix = { { 0.0, 1.0, INF, INF, INF, INF, INF, INF }, // USD { INF, 0.0, 1.0, INF, INF, 4.0, 4.0, INF }, // CHF { INF, INF, 0.0, INF, 1.0, INF, INF, INF }, // YEN { INF, INF, 1.0, 0.0, INF, INF, INF, INF }, // GBP { INF, INF, INF, -3.0, 0.0, INF, INF, INF }, // CNY { INF, INF, INF, INF, INF, 0.0, 5.0, 3.0 }, // EUR { INF, INF, INF, INF, INF, INF, 0.0, 4.0 }, // XXX { INF, INF, INF, INF, INF, INF, INF, 0.0 } }; // YYY 私たちのプログラムは単純に停止し、メッセージを表示します。 Graph contains negative cycle. 問題を示すことはできましたが、グラフの問題のあるセグメントを回避する必要があります。 負のサイクルを避ける これを実現するには、負のサイクルの一部である頂点を定数値 NEG_INF でマークします。 bool FindPathsAndNegativeCycles(Graph& graph, int start) { int verticesNumber = graph.Nodes.size(); _shortestPath.resize(verticesNumber, INF); _previousVertex.resize(verticesNumber, -1); _shortestPath[start] = 0; for (int k = 0; k _shortestPath[from] + graph.Matrix[from][to]) { _shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to]; _previousVertex[to] = from; } } bool negativeCycles = false; for (int k = 0; k _shortestPath[from] + graph.Matrix[from][to]) { _shortestPath[to] = NEG_INF; _previousVertex[to] = -2; negativeCycles = true; } } return negativeCycles; } これで、_shortestPath 配列内で NEG_INF が見つかった場合、メッセージを表示してそのセグメントをスキップしながら、他の通貨に対する最適なソリューションを特定できるようになります。たとえば、ノード 0 (USD を表す) の場合は次のようになります。 Graph contains negative cycle. Path from 0 to 0 is : 0(USD) Path from 0 to 1 is : 0(USD) 1(CHF) Path from 0 to 2 is : Infinite number of shortest paths (negative cycle). Path from 0 to 3 is : Infinite number of shortest paths (negative cycle). Path from 0 to 4 is : Infinite number of shortest paths (negative cycle). Path from 0 to 5 is : 0(USD) 1(CHF) 5(EUR) Path from 0 to 6 is : 0(USD) 1(CHF) 6(XXX) Path from 0 to 7 is : 0(USD) 1(CHF) 5(EUR) 7(YYY) うわー！私たちのコードは、データが「少し汚れていた」という事実にもかかわらず、収益性の高いチェーンを多数特定することができました。テスト データを含む上記のすべてのコード例は、 で共有されています。 私の GitHub 小さな変動でも問題になる ここで、学んだことを定着させてみましょう。 3 つの通貨の為替レートのリストがあれば、負のサイクルを簡単に検出できます。 graph.Nodes.push_back({ "USD" }); // 1 (Index = 0) graph.Nodes.push_back({ "CHF" }); graph.Nodes.push_back({ "YEN" }); // 3 (Index = 2) // LogE(x) table: USD CHF YEN graph.Matrix = { { 0.0, 0.489, -0.402 }, // USD { -0.489, 0.0, -0.891 }, // CHF { 0.402, 0.89, 0.0 } }; // YEN from = 0; FindPathsAndNegativeCycles(graph, from); 結果： Graph contains negative cycle. Path from 0 to 0 is: Infinite number of shortest paths (negative cycle). Path from 0 to 1 is: Infinite number of shortest paths (negative cycle). Path from 0 to 2 is: Infinite number of shortest paths (negative cycle). ただし、為替レートのわずかな変更 (つまり、マトリックスの調整) でさえ、大きな差異が生じる可能性があります。 // LogE(x) table: USD CHF YEN graph.Matrix = { { 0.0, 0.490, -0.402 }, // USD { -0.489, 0.0, -0.891 }, // CHF { 0.403, 0.891, 0.0 } }; // YEN from = 0; FindPathsAndNegativeCycles(graph, from); 見てください、収益性の高いチェーンが 1 つ見つかりました。 Path from 0 to 0 is : 0(USD) Path from 0 to 1 is : 0(USD) 2(YEN) 1(CHF) Path from 0 to 2 is : 0(USD) 2(YEN) これらの概念を、複数の通貨を含むさらに大きなグラフに適用できます。 graph.Nodes.push_back({ "USD" }); // 1 (Index = 0) graph.Nodes.push_back({ "CHF" }); graph.Nodes.push_back({ "YEN" }); graph.Nodes.push_back({ "GBP" }); graph.Nodes.push_back({ "CNY" }); // 5 (Index = 4) // LogE(x) table: USD CHF YEN GBP CNY graph.Matrix = { { 0.0, 0.490, -0.402, 0.7, 0.413 }, // USD { -0.489, 0.0, -0.891, 0.89, 0.360 }, // CHF { 0.403, 0.891, 0.0, 0.91, 0.581 }, // YEN { 0.340, 0.405, 0.607, 0.0, 0.72 }, // GBP { 0.403, 0.350, 0.571, 0.71, 0.0 } }; // CNY from = 0; runDetectNegativeCycles(graph, from); その結果、利益を得る候補が複数見つかる可能性があります。 Path from 0 to 0 is : 0(USD) Path from 0 to 1 is : 0(USD) 2(YEN) 1(CHF) Path from 0 to 2 is : 0(USD) 2(YEN) Path from 0 to 3 is : 0(USD) 2(YEN) 3(GBP) Path from 0 to 4 is : 0(USD) 2(YEN) 4(CNY) ただし、重要な要素が 2 つあります。 主に通貨価格の急速な変動により、裁定取引プロセスを実行する際には時間が重要な要素となります。その結果、確実な賭けの寿命は非常に短くなります。 プラットフォームは取引ごとに手数料を徴収します。 したがって、 、 が最も重要であり、これは確実なベットの長さを制限することによって実現されます。 時間コストを最小限に抑え 手数料を削減すること 経験的には、許容可能な確実なベットの長さは通常 2 ～ 3 ペアの範囲であることが示唆されています。これを超えると、計算要件がエスカレートし、取引プラットフォームにより高額な手数料が課せられます。 したがって、収入を得るには、そのようなテクノロジーを所有するだけでは十分ではなく、低レベルの手数料を利用することも必要です。通常、そのようなリソースを持っているのは大手金融機関だけです。 スマートコントラクトを使用した自動化 FX 操作のロジックとそこから利益を引き出す方法については詳しく説明しましたが、これらの操作を実行するために使用されるテクノロジーについては触れていません。この話題は少し本筋からそれますが、スマート コントラクトについては触れずにはいられませんでした。 スマート コントラクトの使用は、今日の為替操作を行うための最も革新的な方法の 1 つです。スマート コントラクトにより、遅延や人間の介入なしでリアルタイムの FX 操作が可能になります (スマート コントラクトの作成を除く)。 Solidity は、暗号通貨を含む金融業務を自動化するスマート コントラクトを作成するための特殊なプログラミング言語です。スマート コントラクトの世界は動的であり、急速な技術変化や進化する規制の影響を受けます。これは、かなりの誇大広告と、ウォレットや法令順守に関連した重大なリスクを伴う分野です。 この分野から利益を得ている才能ある個人やチームがいることは間違いありませんが、市場ルールが確実に守られるように努めている規制当局もいます。 なぜこれを調査するのでしょうか? 世界経済の複雑さ、曖昧さ、予測不可能性にもかかわらず、外国為替は金融界の隠れた原動力であり続けています。これは、世界中の何千もの企業と何百万もの個人が、国境を越えて平和的に協力し、サービスを提供し、相互に利益をもたらすことを可能にする重要な要素です。 もちろん、政治、規制、中央銀行などのさまざまな要因が為替レートや為替効率に影響を与えます。こうした複雑さにより、金融情勢は複雑化しています。しかし、これらの複雑さは公益のためのより大きな目的に役立つと信じることが不可欠です。 世界経済における為替レートの存在と決定については、数多くの科学論文が詳しく調査されており、その例としては次のようなものがあります。 輸入業者、輸出業者と為替レートの断絶 通貨の選択と為替レートのパススルー 為替レートのパズルと政策 これらの論文は、理解することがまだ難しく、1 つのモデルに当てはめることが難しい外国為替のいくつかの基本的なメカニズムに光を当てています。 ただし、コードをいじって実際の問題の解決策を見つけようとすると、それについてもう少し手がかりを得ることができました。皆さんも私と同じようにこの小さな探検旅行を楽しんでいただければ幸いです。 乞うご期待！ リンク これらすべての例を含むソースコード Sedgewick R. - C のアルゴリズム、パート 5: グラフ アルゴリズム Bellman Ford アルゴリズム コードの実装 William Fiset の GitHub の例 - Bellman Ford On Adjacency Matrix William Fiset の GitHub サンプル - Bellman Ford On Edge List でも公開されています。 ここ