4

自分が今何をしているのかわからないので、私の言葉遣いはおかしく聞こえるかもしれません。しかし、真剣に、私は学ぶ必要があります。

私が直面している問題は、ソフトウェア プログラムの動作方法 (つまり、実行時間と最大メモリ使用量) を推定する方法 (モデル) を考え出すことです。私がすでに持っているのは大量のデータです。このデータセットは、プログラムがさまざまな条件下でどのように機能するかの概要を示します。

<code>
RUN     Criterion_A  Criterion_B  Criterion_C  Criterion_D  Criterion_E <br>
------------------------------------------------------------------------
R0001           12         2           3556            27           9 <br>      
R0002            2         5           2154            22           8 <br>
R0003           19        12           5556            37           9 <br>
R0004           10         3           1556             7           9 <br>
R0005           5          1            556            17           8 <br>
</code>

私はそのようなデータを何千行も持っています。ここで、すべての基準が事前にわかっている場合に、実行時間と最大メモリ使用量を推定 (予測) する方法を知る必要があります。私が必要としているのは、ヒント (上限または範囲) を与える概算です。

私はそれが典型的だと感じていますか？わからない問題。ヒントやアイデア（理論、説明、ウェブページ）、または役立つ可能性のあるものを教えてください。ありがとう！

4

2 に答える 2

5

1 つ以上の条件を入力として取り、実行時間またはメモリ使用量の見積もりを出力する新しいプログラムが必要です。これは機械学習の問題です。

入力は、次のように数値のベクトルとしてリストできます。

input = [ A, B, C, D, E ]

このための最も単純なアルゴリズムの 1 つは、K 最近傍アルゴリズムです。この背後にある考え方は、数値の入力ベクトルを取得し、入力ベクトルに最も類似した数値のベクトルをデータベースで見つけることです。たとえば、次の入力ベクトルがあるとします。

input = [ 11, 1.8, 3557, 29, 10 ]

実行時間とメモリは、この実行の値と非常に似ていると想定できます (元は上記の表にあります)。

R0001           12         2           3556            27           9

これら 2 つのベクトル間の類似度を計算するアルゴリズムはいくつかあります。単純で直感的なアルゴリズムの 1 つがユークリッド距離です。例として、入力ベクトルとテーブルからのベクトルの間のユークリッド距離は次のとおりです。

dist = sqrt( (11-12)^2 + (1.8-2)^2 + (3557-3556)^2 + (27-29)^2 + (9-10)^2 )
dist = 2.6533

距離は 2 つの基準セット間の類似性を表すため、距離が短いポイントの方が実行時間とメモリ使用量をより適切に推定できることは直感的に明らかです。基準が有益で適切に選択されていると仮定すると、同様の基準を持つポイントは実行時間とメモリ使用量が同様になるはずです。

R でこれを行う方法のコード例を次に示します。

r1 = c(11,1.8,3557,29,10)
r2 = c(12,2.0,3556,27, 9)

print(r1)
print(r2)

dist_r1_r2 = sqrt( (11-12)^2 + (1.8-2)^2 + (3557-3556)^2 + (27-29)^2 + (9-10)^2 ) 
print(dist_r1_r2)
smarter_dist_r1_r2 = sqrt( sum( (r1 - r2)^2 ) ) 
print(smarter_dist_r1_r2)

最も近い行の実行時間とメモリ使用量を取得するのは、K=1 の KNN アルゴリズムです。このアプローチを拡張して、データベースから複数の行の重み付けされた組み合わせを取得することにより、複数の行からのデータを含めることができます。入力ベクトルまでの距離が短い行ほど、推定に貢献します。詳細については、KNN のウィキペディアのページを参照してください。特に、複数のポイントからの寄与や距離の計算を含むデータの正規化に関する情報を参照してください。

これらの入力ベクトルのリスト間の差を計算するときは、データの正規化を検討する必要があります。これを行う理由は、基準 C の 3557 と 3556 の間の 1 単位の差は、基準 A の 11 と 12 の間の 1 の差に相当しない可能性があるためです。データが正規分布している場合は、それらをすべて標準に変換できます。次の式を使用してスコア (または Z スコア)を計算します。

N_trans = (N - mean(N)) / sdev(N)

データを正規化する「正しい」方法は、データの種類と範囲によって異なるため、一般的な解決策はありませんが、Z スコアは計算が簡単で、最初に試すのに適した方法です。

線形回帰、サポート ベクター回帰、非線形モデリングなど、このような推定値を作成するためのより高度な手法が多数あります。いくつかのより洗練された方法の背後にある考え方は、変数と実行時間またはメモリとの関係を記述する方程式を作成しようとすることです。たとえば、単純なアプリケーションには基準が 1 つしかなく、次のようなモデルを試して区別することができます。

running_time = s1 * A + s0
running_time = s2 * A^2 + s1 * A + s0
running_time = s3 * log(A) + s2 * A^2 + s1 * A + s0

A は固定基準であり、sN は、適切に機能するモデルが得られるまで微調整できる自由パラメーターのリストです。

このアプローチの問題点の 1 つは、さまざまな数のパラメーターを持つさまざまなモデルが多数存在することです。パラメーターの数が異なるモデルを区別することは、統計では難しい問題であり、機械学習への最初の進出時に取り組むことはお勧めしません。

自問すべき質問は次のとおりです。

  1. すべての条件は、実行時間とメモリ使用量の両方に影響しますか? どちらか一方のみに影響するものもあれば、予測の観点から役に立たないものもありますか? この質問に答えることが特徴選択と呼ばれ、機械学習の未解決の問題です。
  2. 変数が実行時間やメモリ使用量にどのように影響するかについて、アプリオリな見積もりはありますか? たとえば、アプリケーションが時間的に N * log(N) である並べ替えアルゴリズムを使用していることを知っている場合があります。これは、1 つの基準と実行時間との関係を明示的に知っていることを意味します。
  3. 実行時間とメモリ使用量と組み合わせた測定された入力基準の行は、アプリケーションの考えられるすべてのユース ケースをカバーしていますか? もしそうなら、機械学習はなじみのないデータを扱うのに苦労する可能性があるため、見積もりははるかに良くなります。
  4. プログラムの実行時間とメモリは、見積もり戦略に入力していない基準に依存していますか? たとえば、Web スパイダーなどの外部リソースに依存している場合、ネットワークの問題が実行時間やメモリ使用量に予測しにくい影響を与える可能性があります。この場合、見積もりにはさらに多くの分散が生じます。
于 2010-07-05T00:59:37.470 に答える
2

予測する基準が現在知られている基準の範囲内にある場合は、補間プロセスについてさらに調査する必要があります。

数値解析の数学的サブフィールドでは、内挿は、既知のデータ ポイントの離散セットの範囲内で新しいデータ ポイントを構築する方法です。

現在知られているデータ範囲外にある場合は、精度の低い 外挿を調査します。

数学では、外挿は既知のデータ ポイントの離散セットの外部に新しいデータ ポイントを構築するプロセスです。

メソッド

于 2010-07-05T00:13:43.393 に答える