Iterativní proporcionální tvarování - Iterative proportional fitting

The iterativní postup proporcionálního přizpůsobení (IPF nebo IPFP, také známý jako biproporcionální kování ve statistikách, Algoritmus RAS^[1] v ekonomii, hrabání ve statistikách průzkumu a měřítko matice v informatice) je iterační algoritmus pro proporcionální úpravu matice nebo kontingenční tabulky nezáporných prvků, aby se vytvořila nová „podobná“ tabulka se zadanými kladnými mezními součty alespoň ve dvou rozměrech. Ve dvou dimenzích se úprava skládá z rozdělování řádků matice tak, aby odpovídaly součtu zadaných řádků, a poté rozdělování jeho sloupců tak, aby odpovídaly zadaným součtem sloupců. Každý krok obvykle narušuje shodu předchozího kroku, takže se tyto kroky opakují v cyklech a postupně se znovu upravují řádky a sloupce, dokud nebudou uspokojivě aproximovány všechny zadané mezní součty. V trojrozměrných nebo vícerozměrných případech se postupně použijí kroky nastavení pro okraje každé dimenze, kroky se rovněž opakují v cyklech.

Dějiny

IPF byl mnohokrát „znovu vynalezen“, nejdříve Kruithofem v roce 1937 ^[2]ve vztahu k telefonnímu provozu („metoda dvojitého faktoru Kruithof“), Deming a Stephan v roce 1940^[3] pro úpravu sčítání sčítání lidu a G.V. Sheleikhovskii pro provoz podle hlášení Bregmana.^[4] (Deming a Stephan navrhli IPFP jako algoritmus vedoucí k minimalizátoru Statistika Pearsonova čtverce, což Stephan později ohlásil ne,^[5]. Rané důkazy jedinečnosti a konvergence pocházely od Sinkhorna (1964),^[6] Bacharach (1965),^[7] Bishop (1967),^[8] a Fienberg (1970).^[9]. Bishopův důkaz, že IPFP najde odhad maximální pravděpodobnosti pro libovolný počet rozměrů, rozšířil důkaz z roku 1959 Brownem pro případy 2x2x2 .... Fienbergův důkaz diferenciální geometrie využívá konstantní poměry meziproduktů metody pro přísně pozitivní tabulky. Csiszár (1975).^[10] našel nezbytné a dostatečné podmínky pro obecné tabulky s nulovými položkami. Pukelsheim a Simeone (2009)^[11] poskytnout další výsledky týkající se konvergence a chybového chování.

Vyčerpávající zpracování algoritmu a jeho matematických základů lze najít v knize Bishop et al. (1975).^[12] Idel (2016)^[13] poskytuje novější průzkum.

Jiné obecné algoritmy lze upravit tak, aby poskytovaly stejný limit jako IPFP, například Newton – Raphsonova metoda a EM algoritmus. Ve většině případů je IPFP preferován kvůli své výpočetní rychlosti, nízkým požadavkům na úložiště, numerické stabilitě a algebraické jednoduchosti.

Aplikace IPFP se rozrostly distribuce výletů modely, Fratar nebo Furness a další aplikace v dopravním plánování (Lamond a Stewart), vážení průzkumu, syntéza křížově klasifikovaných demografických dat, úprava modely vstup-výstup v ekonomii, odhad očekávané kvazi nezávislé kontingenční tabulky, biproporcionální rozdělení systémy politické reprezentace a pro kondicionér v lineární algebře.^[14]

Algoritmus 1 (klasický IPF)

Vzhledem k obousměrnému (Já × J)-stůl ${displaystyle x_ {ij}}$, chceme odhadnout novou tabulku ${displaystyle {hat {m}} _ {ij} = a_ {i} b_ {j} x_ {ij}}$ pro všechny i a j tak, aby okrajové strany uspokojily ${displaystyle sum _ {j} {hat {m}} _ {ij} = u_ {i},}$ a ${displaystyle sum _ {i} {hat {m}} _ {ij} = v_ {j}}$.

Zvolte počáteční hodnoty ${displaystyle {hat {m}} _ {ij} ^ {(0)}: = x_ {ij}}$, a pro ${displaystyle eta geq 1}$ soubor

${displaystyle {hat {m}} _ {ij} ^ {(2eta -1)} = {frac {{hat {m}} _ {ij} ^ {(2eta -2)} u_ {i}} {sum _ {k = 1} ^ {J} {hat {m}} _ {ik} ^ {(2eta -2)}}}}$

${displaystyle {hat {m}} _ {ij} ^ {(2eta)} = {frac {{hat {m}} _ {ij} ^ {(2eta -1)} v_ {j}} {sum _ {k = 1} ^ {I} {hat {m}} _ {kj} ^ {(2eta -1)}}}.}$

Tyto kroky opakujte, dokud nejsou součty řádků a sloupců dostatečně blízko u a v.

Poznámky:

• Pro formu RAS algoritmu definujte operátor diagonalizace ${displaystyle diag: mathbb {R} ^ {k} longrightarrow mathbb {R} ^ {k imes k}}$, který vytváří (diagonální) matici se svým vstupním vektorem na hlavní diagonále a nulou jinde. Pak pro každou úpravu řádku nechte ${displaystyle R ^ {eta} = diag ({frac {u_ {i}} {sum _ {j} m_ {ij} ^ {(2eta -2)}}})}$, z nichž ${displaystyle M ^ {2eta -1} = R ^ {eta} M ^ {2eta -2}}$. Podobně každá úprava sloupce ${displaystyle S ^ {eta} = diag ({frac {v_ {i}} {sum _ {i} m_ {ij} ^ {(2eta -1)}}})}$, z nichž ${displaystyle M ^ {2eta} = M ^ {2eta -1} S ^ {eta}}$. Při redukci operací na nezbytné je snadno vidět, že RAS dělá totéž jako klasický IPF. V praxi by se neimplementovalo skutečné násobení matic s celou maticí R a S; forma RAS je spíše notační než výpočetní pohodlí.

Algoritmus 2 (odhad faktoru)

Předpokládejme stejné nastavení jako v klasickém IPFP. Alternativně můžeme odhadnout faktory řádku a sloupce samostatně: Zvolte počáteční hodnoty ${displaystyle {hat {b}} _ {j} ^ {(0)}: = 1}$, a pro ${displaystyle eta geq 1}$ soubor

${displaystyle {hat {a}} _ {i} ^ {(eta)} = {frac {u_ {i}} {sum _ {j} x_ {ij} {hat {b}} _ {j} ^ {( eta -1)}}},}$

${displaystyle {hat {b}} _ {j} ^ {(eta)} = {frac {v_ {j}} {sum _ {i} x_ {ij} {hat {a}} _ {i} ^ {( eta)}}}}$

Tyto kroky opakujte, dokud nejsou následné změny a a b dostatečně zanedbatelné (označující, že výsledné součty řádků a sloupců jsou blízké u a v).

Nakonec je výsledná matice${displaystyle {hat {m}} _ {ij} = {hat {a}} _ {i} ^ {(eta)} {hat {b}} _ {j} ^ {(eta)} x_ {ij}}$

Poznámky:

• Obě varianty algoritmu jsou matematicky ekvivalentní, jak je patrné z formální indukce. Při odhadování faktorů není nutné skutečně počítat cykly každého cyklu ${displaystyle {hat {m}} _ {ij} ^ {(eta)}}$.

• Faktorizace není ojedinělá, protože je ${displaystyle m_ {ij} = a_ {i} b_ {j} x_ {ij} = (gamma a_ {i}) ({frac {1} {gamma}} b_ {j}) x_ {ij}}$ pro všechny ${displaystyle gamma> 0}$.

Diskuse

Nejasně požadovanou „podobnost“ mezi M a X lze vysvětlit takto: IPFP (a tedy RAS) udržuje poměry křížových produktů, tj.

${displaystyle {frac {m_ {ij} ^ {(eta)} m_ {hk} ^ {(eta)}} {m_ {ik} ^ {(eta)} m_ {hj} ^ {(eta)}}} = {frac {x_ {ij} x_ {hk}} {x_ {ik} x_ {hj}}} forall eta geq 0 {ext {and}} ieq h, quad jeq k}$

od té doby ${displaystyle m_ {ij} ^ {(eta)} = a_ {i} ^ {(eta)} b_ {j} ^ {(eta)} x_ {ij}.}$

Tato vlastnost se někdy nazývá zachování struktury a přímo vede ke geometrické interpretaci kontingenčních tabulek a důkazu konvergence v seminární práci Fienberga (1970).

Přímý odhad faktoru (algoritmus 2) je obecně účinnějším způsobem řešení IPF: Zatímco forma klasického IPFP potřebuje

${displaystyle IJ (2 + J) + IJ (2 + I) = I ^ {2} J + IJ ^ {2} + 4IJ,}$

základní operace v každém iteračním kroku (včetně kroku přizpůsobení řádku a sloupce), je potřeba pouze odhad faktoru

${displaystyle I (1 + J) + J (1 + I) = 2IJ + I + J,}$

operace jsou nejméně o jeden řád rychlejší než klasické IPFP.

IPFP lze použít k odhadu očekávaných kvazi-nezávislých (neúplných) pohotovostních tabulek s ${displaystyle u_ {i} = x_ {i +}, v_ {j} = x _ {+ j}}$, a ${displaystyle m_ {ij} ^ {0} = 1}$ pro zahrnuté buňky a ${displaystyle m_ {ij} ^ {0} = 0}$ pro vyloučené buňky. U plně nezávislých (úplných) pohotovostních tabulek končí odhad pomocí IPFP přesně v jednom cyklu.

Existence a jedinečnost MLE

Nezbytné a dostatečné podmínky pro existenci a jedinečnost MLE jsou obecně komplikované (viz^[15]), ale dostatečné podmínky pro dvourozměrné tabulky jsou jednoduché:

• marže sledované tabulky nezmizí (tj. ${displaystyle x_ {i +}> 0, x _ {+ j}> 0}$) a
• pozorovaná tabulka je neoddělitelná (tj. tabulka neprostupuje do tvaru blokové úhlopříčky).

Pokud existují jedinečné MLE, vykazuje IPFP v nejhorším případě lineární konvergenci (Fienberg 1970), ale byla také pozorována exponenciální konvergence (Pukelsheim a Simeone 2009). Pokud je to přímý odhad (tj. Uzavřená forma ${displaystyle ({hat {m}} _ {ij})}$) existuje, IPFP konverguje po 2 iteracích. Pokud jedinečné MLE neexistují, IPFP konverguje k tzv prodloužené MLE záměrně (Haberman 1974), ale konvergence může být libovolně pomalá a často výpočetně neproveditelná.

Pokud jsou všechny sledované hodnoty přísně pozitivní, je zajištěna existence a jedinečnost MLE, a proto je zajištěna konvergence.

Příklad

Zvažte následující tabulku, která obsahuje součty řádků a sloupců a cíle.

Pro provedení klasického IPFP nejprve upravíme řádky:

První krok přesně odpovídal součtu řádků, ale nikoli součtu sloupců. Dále upravíme sloupce:

Nyní se součty sloupců přesně shodují s jejich cíli, ale součty řádků se již neshodují s jejich. Po dokončení tří cyklů, každý s úpravou řádků a úpravami sloupců, získáme bližší aproximaci:

Implementace

Balíček R. mipfp (aktuálně ve verzi 3.1) poskytuje vícerozměrnou implementaci tradičního iteračního postupu proporcionálního přizpůsobení.^[16] Balíček umožňuje aktualizaci a N-dimenzionální pole s ohledem na dané cílové okrajové distribuce (které zase mohou být vícerozměrné).

Python má ekvivalentní balíček, ipfn^[17][18] které lze nainstalovat přes pip. Balíček podporuje vstupní objekty numpy a pandy.

Reference