2

Mathematica には、標準の数学的定義に基づいて、無限領域にわたる関数用の組み込み関数ArgMaxがあります。

有限領域の類似物は便利な効用関数です。関数とリスト (関数のドメインと呼びます) を指定すると、関数を最大化するリストの要素を返します。実行中の有限 argmax の例を次に示します。 NFL チーム名の正規化

そして、これが私の実装です（適切な測定のために argmin とともに）：

(* argmax[f, domain] returns the element of domain for which f of 
   that element is maximal -- breaks ties in favor of first occurrence. *)
SetAttributes[{argmax, argmin}, HoldFirst];
argmax[f_, dom_List] := Fold[If[f[#1]>=f[#2], #1, #2]&, First[dom], Rest[dom]]
argmin[f_, dom_List] := argmax[-f[#]&, dom]

まず、それは argmax を実装する最も効率的な方法ですか? 最初の要素だけでなく、すべての最大要素のリストが必要な場合はどうしますか?

次に、最大要素を返す代わりに、最大要素の位置を返す関連関数 posmax はどうですか?

4

2 に答える 2

3

@dreeves、それがOrdering有限ドメインでの ArgMax の最速の実装の鍵であるという点で正しいです。

ArgMax[f_, dom_List] := dom[[Ordering[f /@ dom, -1]]]

を使用した元の実装の問題の一部は、必要に応じて 2 倍のFold評価を行うことになることです。これは、特に計算が遅い場合に非効率的です。ここでは、ドメインのメンバーごとに 1 回だけ評価します。ドメインに多くの重複要素がある場合、次の値をメモ化することでさらに最適化できます。ffff

ArgMax[f_, dom_List] :=
  Module[{g},
    g[e___] := g[e] = f[e]; (* memoize *)
    dom[[Ordering[g /@ dom, -1]]]
  ]

これは、0 から 100 までの 100,000 個のランダムな整数のリストに対するいくつかの基本的なテストで約 30% 高速でした。

関数のposmax場合、このやや洗練されていないアプローチは、私が思いつく最速のものです。

PosMax[f_, dom_List] :=
  Module[{y = f/@dom},
    Flatten@Position[y, Max[y]]
  ]

もちろん、メモ化を再度適用することもできます。

PosMax[f_, dom_List] := 
  Module[{g, y},
    g[e___] := g[e] = f[e];
    y = g /@ dom;
    Flatten@Position[y, Max[y]]
  ]

すべての最大要素を取得するには、次のように実装ArgMaxするだけですPosMax。

ArgMax[f_, dom_List] := dom[[PosMax[f, dom]]]
于 2010-04-17T08:39:14.853 に答える
0

posmax の場合、最初に関数をリストにマップしてから、最大要素の位置を求めることができます。すなわち:

posmax[f_, dom_List] := posmax[f /@ dom]

whereposmax[list]は、最大要素の位置を返すようにポリモーフィックに定義されています。本質的にこれを行う組み込み関数Orderingがあることがわかりました。したがって、単一引数バージョンの posmax を次のように定義できます。

posmax[dom_List] := Ordering[dom, -1][[1]]

ループベースのバージョンと再帰バージョンに対してテストしたところ、順序付けは何倍も高速です。再帰バージョンはきれいなのでここで紹介しますが、大きな入力に対して実行しようとしないでください。

(* posmax0 is a helper function for posmax that returns a pair with the position 
   and value of the max element. n is an accumulator variable, in lisp-speak. *)
posmax0[{h_}, n_:0] := {n+1, h}
posmax0[{h_, t___}, n_:0] := With[{best = posmax0[{t}, n+1]},
  If[h >= best[[2]], {n+1, h}, best]]

posmax[dom_List] := First@posmax0[dom, 0]
posmax[f_, dom_List] := First@posmax0[f /@ dom, 0]
posmax[_, {}] := 0

これはどれも、すべての最大要素 (またはそれらの位置)を見つける方法の問題に対処していません。これは通常、実際には思いつきませんが、あるとよいと思います。

于 2010-04-17T00:53:54.093 に答える