1,140 測定値

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

に Anton Yarkov22m2023/10/28

長すぎる; 読むには

以前の取り組みに続いて、私は収益性の高い通貨交換の方法を探して、グラフとグラフ走査アルゴリズムをいじり続けています。

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

‘a person entering a bank vault’ Image created by HackerNoon AI Image Generator

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<vector<double>> Matrix; vector<GraphNode> 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<double> _shortestPath; vector<int> _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 < verticesNumber - 1; k++) for (int from = 0; from < verticesNumber; from++) for (int to = 0; to < verticesNumber; to++) if (_shortestPath[to] > _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<double> _shortestPath; vector<int> _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 < verticesNumber - 1; k++) { updated = false; for (int from = 0; from < verticesNumber; from++) { for (int to = 0; to < verticesNumber; to++) { if (_shortestPath[to] > _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 < verticesNumber; from++) for (int to = 0; to < verticesNumber; to++) if (_shortestPath[to] > _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 < verticesNumber - 1; k++) for (int from = 0; from < verticesNumber; from++) for (int to = 0; to < verticesNumber; to++) { if (graph.Matrix[from][to] == INF) // Edge not exists { continue; } if (_shortestPath[to] > _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 < verticesNumber - 1; k++) for (int from = 0; from < verticesNumber; from++) for (int to = 0; to < verticesNumber; to++) { if (graph.Matrix[from][to] == INF) // Edge not exists { continue; } if (_shortestPath[to] > _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)