LLLアルゴリズム(LLL algorithm)とは、格子の基底を、Gram–Schmidt の係数の絶対値が $\frac12$ 以下で隣り合う射影の長さが急に減らない基底(LLL 簡約基底)に取り替えるアルゴリズムで、1982 年に Lenstra・Lenstra・Lovász が多項式の因数分解のために導入した。階数 $n$ の格子の簡約基底の最初のベクトル $b_1$ は、最短の $0$ でない格子の点の長さ $\lambda_1$ について $\|b_1\|\le2^{(n-1)/2}\lambda_1$ をみたす。整数の基底で長さの 2 乗が $B$ 以下なら、基底の入れ替えは $\frac{n(n-1)}{2}\log_{4/3}B$ 回以下で、全体は多項式時間で終わる。最小多項式の推定、連立の Diophantus 近似、格子暗号の解析に使われる。
13秒前に投稿
高速多重極法(fast multipole method)とは、平面の $N$ 個の点電荷のつくる対数ポテンシャルの和のような、すべての点の組の相互作用の和を、決めた精度で、点がほぼ一様に分布していれば点の数に比例する手間で計算する方法である。遠くの点の集まりの寄与を、1 つの中心のまわりの $p$ 項の多重極展開にまとめ、4 分木の箱の間で係数を移し替え、隣接する箱の寄与だけを直接計算する。誤差の上界は $p$ を 1 増やすごとに一定の比で小さくなる。粒子の計算や、境界要素法の密な行列とベクトルの積に使う。
45秒前に投稿
コア(ゲーム理論)(core)とは、提携形ゲーム $(N,v)$ で、全体の価値 $v(N)$ を分ける配分 $x$ のうち、すべての提携 $S$ が $x(S)\ge v(S)$ を満たすものの全体である。どの提携も抜け出す理由を持たない配分の集合で、有限個の 1 次不等式の定める多面体である。コアが空でないことは、すべての均衡な重みで $\sum_S\lambda_Sv(S)\le v(N)$ となることと同値である(Bondareva–Shapley の定理)。優モジュラな凸ゲームではコアは限界ベクトルの凸包で、Shapley 値を含むが、多数決のように空になるゲームもある。
3分前に投稿
普遍近似定理(universal approximation theorem)とは、隠れ層 1 つのニューラルネットワークが、ユニットの数を十分に増やせば、コンパクト集合の上の任意の連続関数をいくらでもよく一様に近似できるという定理の総称である。代表的な形では、活性化関数が連続で、正の無限大で 1、負の無限大で 0 に近づくとき、その 1 次式との合成の 1 次結合の全体が連続関数の空間で稠密になる。証明は Hahn–Banach の定理と測度による汎関数の表示を使う方法と、Stone–Weierstrass の定理と 1 変数の構成による方法があり、ReLU や双曲線正接にも広がるが、活性化関数が多項式なら成り立たない。
4分前に投稿
Shapley値(Shapley value)とは、提携形ゲーム $(N,v)$ の全体の価値 $v(N)$ を、プレイヤーが無作為な順に到着するときの限界貢献の期待値に従って分ける配分である。効率性・対称性・ダミー・加法性の 4 つの公理を満たす規則はこれただ 1 つである。部分集合の和の式や配当の和の式で計算でき、投票の力の指数、費用の分担、機械学習の予測の寄与の分解に使われる。凸ゲームではコアに属するが、一般のゲームではコアに入るとは限らない。
4分前に投稿
Metropolis–Hastings法(Metropolis–Hastings algorithm)とは、正規化の定数が分からない密度 $p\propto\tilde p$ の分布 $\pi$ について、現在の状態 $x$ から提案の密度 $q(x,\cdot)$ で候補 $y$ を引き、確率 $\min\bigl(1,\frac{p(y)q(y,x)}{p(x)q(x,y)}\bigr)$ で受理し、そうでなければ $x$ にとどまる Markov 連鎖を作る方法で、事後分布の計算に使う。$\pi$ は提案によらず定常分布になり、連鎖が既約で非周期的なら、$\pi$ についてほとんどすべての出発点から分布は $\pi$ に収束する。提案が状態によらない独立型ですべての点で $p\le Mg$ なら、全変動距離は出発点によらず $(1-1/M)^n$ 以下である。
5分前に投稿
Euler–Lagrange方程式(Euler–Lagrange equation)とは、汎関数 $J(u)=\int_a^b F(x,u,u')\,dx$ の停留点が満たす微分方程式 $\frac{d}{dx}F_p(x,u,u')=F_y(x,u,u')$ である。端点を固定した $C^1$ 級の関数について、停留点であることとこの方程式の解であることは同値で、最小点であるための必要条件だが十分条件ではない。方程式は座標変換で形を変えず、$F$ が $x$ を含まなければ第一積分をもつ。最速降下線のサイクロイドはその代表的な解で、多変数では偏微分方程式になる。
5分前に投稿
遅延微分方程式(delay differential equation)とは、$\dot x(t)=f(x(t),x(t-\tau))$ のように変化の速さが過去の状態にも依存する微分方程式である。初期条件は長さ $\tau$ の区間の履歴で、$f$ が第 1 引数について局所 Lipschitz 連続なら階段法で解がただ 1 つ定まる。線形の $\dot x=ax(t)+bx(t-\tau)$ では特性方程式 $\lambda=a+be^{-\lambda\tau}$ の根の最大実部が解の増え方を決め、安定領域が完全に決まる。遅れのあるロジスティック方程式では $r\tau=\pi/2$ で平衡点の線形化が不安定に変わる。
6分前に投稿
誤差逆伝播法(backpropagation)とは、ニューラルネットワークの損失のすべてのパラメータについての偏微分を、連鎖律を出力の側から入力の側へ順に当てて計算する方法である。順伝播で途中の値を保存したあと、各層の値についての損失の偏微分(誤差)を、重みの転置を掛けて活性化関数の微分を掛ける漸化式で出力から入力へ 1 層ずつ求め、各重みの偏微分を誤差とその層の入力の積として得る。演算は順伝播の 2 倍以下で、パラメータごとに差分をとる方法よりはるかに速く、一般の計算グラフの逆向きの自動微分の特別な場合にあたる。
7分前に投稿
生存解析(survival analysis)とは、寿命や故障までの時間のように、観測が途中で打ち切られて一部しか分からない「出来事までの時間」の分布を推定し比べる統計の手法である。分布を生存関数とハザード(その時刻まで生き残った者がその時刻に死ぬ割合)で表すと、離散の場合は生存関数がハザードを使った積、密度をもつ場合は累積ハザードの指数で書ける。Kaplan–Meier 推定量は、各死亡時刻の死亡数をその時刻のリスク集合の大きさで割った割合を使う積で、打ち切りのあるデータの尤度を最大にし、打ち切りが寿命と独立で寿命が有限個の値をとるときは真の生存関数に近づく。累積ハザードは Nelson–Aalen 推定量で推定し、打ち切りが寿命に依存すると推定は偏る。
7分前に投稿