math - データセットに適合する効率的な関数の作成

Question

基本的に、私は4バイトの入力とそれに対応する4バイトの出力の大きな（100,000〜150,000の値を取得する可能性がある）データセットを持っています。入力が一意であることが保証されているわけではありませんが（疑似乱数を生成して入力を追加または排他的論理和して一意になることができると考えているため、実際には問題ありません）、出力は次のように保証されていません。どちらかが一意である（したがって、2つの異なる入力セットが同じ出力を持つ可能性があります）。

データセットの値を効果的にモデル化する関数を作成しようとしています。効率的に補間する必要はありませんし、まったく必要ありません（これは、この静的データセットに含まれていない入力をフィードすることは決してないということです）。ただし、可能な限り効率的である必要があります。補間を調べたところ、探しているものに実際には適合しないことがわかりました。たとえば、値の数が多いということは、スプライン補間が区間ごとに多項式を作成するため、スプライン補間が実行されないことを意味します。

また、私の理解では、多項式補間は計算コストがかかりすぎます（n値は、多項式にpow（x、n-1）までの項が含まれる可能性があることを意味します）。x=4バイトの数値およびn= 100,000の場合、それはまったくありません。実行可能）。しばらくオンラインで調べてみましたが、数学はあまり得意ではなく、今のところ似たようなものに出会ったことがないので、検索するのに適切な用語を知らないはずです。

これは完全に（穏やかに言えば）プログラミングの質問ではないことがわかります。事前にお詫び申し上げます。私は正確な解決策や完全な答えを探していません。この問題を自分で解決できるように、読み上げる必要のあるトピックへのポインタが必要です。ありがとう！

TL; DR-最初に与えられたデータポイントに適合させるだけでよいが、計算効率が高い補間の変形が必要です。

編集：いくつかの説明-私は出力が正確であり、近似ではない必要があります。これは、私が現在行っているいくつかの調査作業の一種の最適化であり、出力の実際のバイトがプログラムに存在しないように、このルックアップを実装する必要があります。現時点では、それについて多くを語ることはできませんが、私の仕事の目的では、暗号化（または圧縮またはその他の形式の難読化）はテーブルを非表示にするオプションではありません。入力にアクセスできる限り、出力を再作成できる数学関数が必要です。私はそれが物事を少しクリアすることを願っています。

Answer 1

ここに1つのアイデアがあります。関数を、すべての 4 バイト整数の線形関数、最初のビットの値に部分が依存する区分線形関数、最初のビットの値に部分が依存する別の区分線形関数の合計 (mod 2 ³² ) にします。 2 ビットなど。

実際の出力値はどこにも表示されません。線形項を合計して取得する必要があります。また、どの入力値を持っているかについての直接的な記録もありません。(誰かがこれらの入力値について何らかの結論を下すことはできますが、実際の値はそうではありません。)

必要なさまざまな係数は、ハッシュに格納できます。ハッシュに見つからないルックアップはすべて 0 と見なされます。

かなり効率的にエンコードを開始する前に、データセットに一定量のランダムな「ノイズ」を追加すると、入力値が何であるかを判断するのが難しくなり、入力を知らずに出力が何であるかを概算することさえ非常に困難になります。

Answer 2

未使用のエントリでいっぱいの巨大なルックアップ テーブルを提案します。これは、入力のすべての可能な値 (データセットだけでなく、他のすべての可能な 4 バイト値) によって順序付けられた、順序付けられた出力のテーブルを持つブルートフォースアプローチです。

すべてのデータがそこにありますが、使用されていない入力をランダム、任意、または確率的(潜在的に複雑な制約内のランダム) データで埋めることができます。説得力のあるものにすれば、誰もそこからあなたの本当のデータを選ぶことはできません. 「実際の」関数がすべてのデータを補間した場合、実際のデータのすべての情報も「含まれ」、それにアクセスできる人は誰でもそれを使用して上記のように LUT を生成できます。

LUT は非常に高速ですが、非常にメモリを消費します。あなたのケースは実現可能性の限界にあり、(2^32)*32= 16 ギガバイトの RAM が必要であり、実行するには 64 ビット マシンが必要です。これは、プログラム、オペレーティング システム、またはその他のデータではなく、データのためのものです。念のため、24の方がよいでしょう。あなたがそれを買う余裕があるなら、彼らは行く方法です.

Answer 3

関数 (連続、スムーズなど) に制限を課していないため、単純に区分的な定数補間を行うことができます。

または線形補間：

そのような関数をそれほど問題なく構築する方法を理解できると思います。

編集：そのような関数はデータポイントを「隠す」必要があるという追加の要件に照らして...

区分的定数補間の場合、データ ポイントがどこにあるかを明らかにしないように、定数間隔をランダム化する必要があります。たとえば、図では、間隔は補間しているデータ ポイントを中心にしています。代わりに、次のようなことをしたいかもしれません:

[0 , 0.3) -> 0
[0.3 , 1.9) -> 0.8
[1.9 , 2.1) -> 0.9
[2.1 , 3.5) -> 0.2
etc

もちろん、これは x 座標を非表示にするだけです。y 座標も非表示にするには、線形補間を使用できます。

「とがった」部分がデータポイントの場所にならないようにするだけです。隣接するすべてのデータ ポイントがこれらの x 値の 1 つを間に持つように、ランダムな x 値を選択します。次に、「先のとがった」部分がこれらの x 値になるように補間します。