Ajuste proporcional iterativo

El procedimiento de ajuste proporcional iterativo ( IPF o IPFP , también conocido como ajuste biproporcional o biproporción en estadística o economía (análisis de entrada-salida, etc.), algoritmo RAS ^{[ 1 ]} en economía, raking en estadística de encuestas y escalamiento de matrices en informática) es la operación de encontrar la matriz ajustada.${\displaystyle X}$que es la más cercana a una matriz inicial${\displaystyle Z}$pero con los totales de filas y columnas de una matriz objetivo${\displaystyle Y}$(que proporciona las restricciones del problema; el interior de${\displaystyle Y}$es desconocido). La matriz ajustada tiene la forma${\displaystyle X=PZQ}$, dónde${\displaystyle P}$y${\displaystyle Q}$son matrices diagonales tales que${\displaystyle X}$tiene los márgenes (sumas de filas y columnas) de${\displaystyle Y}$Algunos algoritmos pueden elegirse para realizar la biproporción. También tenemos la maximización de la entropía, ^{[ 2 ] [ 3 ]} la minimización de la pérdida de información (o entropía cruzada) ^{[ 4 ]} o RAS que consiste en factorizar las filas de la matriz para que coincidan con los totales de fila especificados, luego factorizar sus columnas para que coincidan con los totales de columna especificados; cada paso generalmente perturba la coincidencia del paso anterior, por lo que estos pasos se repiten en ciclos, reajustando las filas y columnas a su vez, hasta que todos los totales marginales especificados se aproximan satisfactoriamente. Sin embargo, todos los algoritmos dan la misma solución. ^{[ 5 ]} En casos de tres o más dimensiones, los pasos de ajuste se aplican a los marginales de cada dimensión a su vez, los pasos también se repiten en ciclos.

IPF ha sido "reinventado" muchas veces, la primera por Kruithof en 1937 ^{[ 6 ]} en relación con el tráfico telefónico ("método del doble factor de Kruithof"), Deming y Stephan en 1940 ^{[ 7 ]} para ajustar tabulaciones cruzadas del censo, y GV Sheleikhovskii para el tráfico según lo informado por Bregman. ^{[ 8 ]} (Deming y Stephan propusieron IPFP como un algoritmo que conduce a un minimizador de la estadística X-cuadrada de Pearson , lo que Stephan informó más tarde que no hace ). ^{[ 9 ]} Las primeras pruebas de unicidad y convergencia vinieron de Sinkhorn (1964), ^{[ 10 ]} Bacharach (1965), ^{[ 11 ]} Bishop (1967), ^{[ 12 ]} y Fienberg (1970). ^{[ 13 ]} La demostración de Bishop de que IPFP encuentra el estimador de máxima verosimilitud para cualquier número de dimensiones extendió una demostración de 1959 de Brown para casos de 2x2x2... La demostración de Fienberg por geometría diferencial explota las razones de producto cruzado constantes del método, para tablas estrictamente positivas. Csiszár (1975). ^{[ 14 ]} encontró condiciones necesarias y suficientes para tablas generales con entradas cero. Pukelsheim y Simeone (2009) ^{[ 15 ]} dan resultados adicionales sobre convergencia y comportamiento del error.

Un tratamiento exhaustivo del algoritmo y sus fundamentos matemáticos se puede encontrar en el libro de Bishop et al. (1975). ^{[ 16 ]} Idel (2016) ^{[ 17 ]} ofrece una revisión más reciente.

Otros algoritmos generales pueden modificarse para obtener el mismo límite que el IPFP, por ejemplo, el método de Newton-Raphson y el algoritmo EM . En la mayoría de los casos, se prefiere el IPFP debido a su velocidad de cálculo, bajos requisitos de almacenamiento, estabilidad numérica y simplicidad algebraica.

Las aplicaciones de IPFP se han ampliado para incluir modelos de distribución de viajes , Fratar o Furness y otras aplicaciones en planificación del transporte (Lamond y Stewart), ponderación de encuestas, síntesis de datos demográficos clasificados de forma cruzada, ajuste de modelos de entrada-salida en economía, estimación de tablas de contingencia cuasi-independientes esperadas , sistemas de reparto biproporcional de representación política y como precondicionador en álgebra lineal. ^{[ 18 ]}

La biproporción, cualquiera que sea el algoritmo utilizado para resolverla, es el siguiente concepto:${\displaystyle Z}$, matriz${\displaystyle Y}$y matriz${\displaystyle X}$son matrices reales no negativas conocidas de dimensión${\displaystyle n,m}$; el interior de${\displaystyle Y}$es desconocido y${\displaystyle X}$se busca de tal manera que${\displaystyle X}$tiene los mismos márgenes que${\displaystyle Y}$, es decir${\displaystyle Xs=Ys}$y${\displaystyle s'X=s'Y}$(${\displaystyle s}$siendo el vector suma), y tal que${\displaystyle X}$está cerca de${\displaystyle Z}$siguiendo un criterio dado, la matriz ajustada tiene la forma${\displaystyle X=K(Z,Y)=PZQ}$, dónde${\displaystyle P}$y${\displaystyle Q}$son matrices diagonales.

${\displaystyle min\sum _{i}\sum _{j}x_{ij}\log(x_{ij}/z_{ij})}$calle${\displaystyle \sum _{j}x_{ij}=y_{i.}}$, ∀${\displaystyle i}$y${\displaystyle \sum _{i}x_{ij}=y_{.j}}$, ∀${\displaystyle j}$. El lagrangiano es${\displaystyle L=\sum _{i}\sum _{j}x_{ij}\log(x_{ij}/z_{ij})-\sum _{i}p_{i}(y_{i.}-\sum _{j}x_{ij})-\sum _{j}q_{j}(y_{.j}-\sum _{i}x_{ij})}$.

De este modo${\displaystyle x_{ij}=z_{ij}\exp -(1+p_{i}+q_{j})}$, para todo${\displaystyle i,j}$,

que, después de posar${\displaystyle P_{i}=\exp -(1+p_{i})}$y${\displaystyle Q_{j}=\exp -q_{j}}$, produce

${\displaystyle x_{ij}=P_{i}z_{ij}Q_{j}}$, ∀${\displaystyle i,j}$, es decir,${\displaystyle X=PZQ}$,

con${\displaystyle P_{i}=y_{i.}(\sum _{j}z_{ij}Q_{j})^{-1}}$, ∀${\displaystyle i}$y${\displaystyle Q_{j}=y_{.j}(\sum _{i}z_{ij}P_{i})^{-1}}$, ∀${\displaystyle j}$.${\displaystyle P_{i}}$y${\displaystyle Q_{j}}$formar un sistema que pueda resolverse iterativamente:

${\displaystyle P_{i}^{(t+1)}=y_{i.}(\sum _{j}z_{ij}Q_{j}^{(t)})^{-1}}$, ∀${\displaystyle i}$y${\displaystyle Q_{j}^{(t+1)}=y_{.j}(\sum _{i}z_{ij}P_{i}^{(t+1)})^{-1}}$, ∀${\displaystyle j}$.

La solución${\displaystyle X}$es independiente de la inicialización elegida (es decir, podemos comenzar por${\displaystyle q_{j}^{(0)}=1}$, ∀${\displaystyle j}$o por${\displaystyle p_{i}^{(0)}=1}$, ∀${\displaystyle i}$. Si la matriz${\displaystyle Z}$Si es “indescomponible”, entonces este proceso tiene un único punto fijo porque se deduce de un programa donde la función es convexa y continuamente derivable, definida en un conjunto compacto. En algunos casos, la solución puede no existir: véase el ejemplo de de Mesnard citado por Miller y Blair (Miller RE & Blair PD (2009) Input-output analysis: Foundations and Extensions, Second edition, Cambridge (UK): Cambridge University Press, pp.  335-336 (freely available)).

Algunas propiedades (ver de Mesnard (1994)):

Falta de información: si${\displaystyle Z}$no aporta información, es decir,${\displaystyle z_{ij}=z}$, ∀${\displaystyle i,j}$entonces${\displaystyle X=PQ}$.

Idempotencia:${\displaystyle X=K(Z,Y)=Z}$si${\displaystyle Y}$tiene los mismos márgenes que${\displaystyle Z}$.

Composición de biproporciones:${\displaystyle K(K(Z,Y_{1}),Y_{2}=K(Z,Y_{2})}$;${\displaystyle K(...K(Z,Y_{1}),Y_{2})...Z_{N})=K(Z,Y_{N})}$.

Ceros: un cero en${\displaystyle Z}$se proyecta como un cero en${\displaystyle X}$Por lo tanto, una matriz diagonal por bloques se proyecta como una matriz diagonal por bloques y una matriz triangular se proyecta como una matriz triangular.

Teorema de las modificaciones separables: si${\displaystyle Z}$Si se premultiplica por una matriz diagonal y/o se postmultiplica por una matriz diagonal, la solución no cambia.

Teorema de la "unicidad": Si${\displaystyle K^{q}}$es cualquier algoritmo no especificado, con${\displaystyle {\hat {X}}=K^{q}(Z,Y)=UZV}$,${\displaystyle U}$y${\displaystyle V}$siendo desconocido, entonces${\displaystyle U}$y${\displaystyle V}$siempre se puede cambiar a la forma estándar de${\displaystyle P}$y${\displaystyle Q}$Las demostraciones hacen referencia a algunas de las propiedades mencionadas anteriormente, en particular al Teorema de las modificaciones separables y a la composición de biproporciones.

Dada una tabla bidireccional ( I × J )${\displaystyle x_{ij}}$, deseamos estimar una nueva tabla${\displaystyle {\hat {m}}_{ij}=a_{i}b_{j}x_{ij}}$para todo i y j tales que las marginales satisfacen${\displaystyle \sum _{j}{\hat {m}}_{ij}\ =u_{i},}$y${\displaystyle \sum _{i}{\hat {m}}_{ij}\ =v_{j}}$.

Elija valores iniciales${\displaystyle {\hat {m}}_{ij}^{(0)}:=x_{ij}}$y para${\displaystyle \eta \geq 1}$colocar

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

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

Repita estos pasos hasta que los totales de filas y columnas estén suficientemente cerca de u y v.

Notas:

• Para la forma RAS del algoritmo, defina el operador de diagonalización.${\displaystyle diag:\mathbb {R} ^{k}\longrightarrow \mathbb {R} ^{k\times k}}$, que produce una matriz (diagonal) con su vector de entrada en la diagonal principal y cero en el resto. Luego, para cada ajuste de fila, sea${\displaystyle R^{\eta }=diag({\frac {u_{i}}{\sum _{j}m_{ij}^{(2\eta -2)}}})}$, de la cual${\displaystyle M^{2\eta -1}=R^{\eta }M^{2\eta -2}}$. De manera similar, cada ajuste de columna${\displaystyle S^{\eta }=diag({\frac {v_{i}}{\sum _{i}m_{ij}^{(2\eta -1)}}})}$, de la cual${\displaystyle M^{2\eta }=M^{2\eta -1}S^{\eta }}$Reduciendo las operaciones a las necesarias, se puede observar fácilmente que RAS realiza la misma función que el IPF clásico. En la práctica, no se implementaría la multiplicación de matrices completa con las matrices R y S; la notación RAS es más una conveniencia notacional que computacional.

Supongamos la misma configuración que en el IPFP clásico. Alternativamente, podemos estimar los factores de fila y columna por separado: Elegir valores iniciales${\displaystyle {\hat {b}}_{j}^{(0)}:=1}$y para${\displaystyle \eta \geq 1}$colocar

${\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 )}}}}$

Repita estos pasos hasta que los cambios sucesivos de a y b sean suficientemente insignificantes (lo que indica que las sumas resultantes de filas y columnas están cerca de u y v).

Finalmente, la matriz de resultados es ${\displaystyle {\hat {m}}_{ij}={\hat {a}}_{i}^{(\eta )}{\hat {b}}_{j}^{(\eta )}x_{ij}}$

Notas:

• Las dos variantes del algoritmo son matemáticamente equivalentes, como se puede ver por inducción formal. Con la estimación de factores, no es necesario calcular realmente cada ciclo.${\displaystyle {\hat {m}}_{ij}^{(\eta )}}$.
• La factorización no es única, ya que es${\displaystyle m_{ij}=a_{i}b_{j}x_{ij}=(\gamma a_{i})({\frac {1}{\gamma }}b_{j})x_{ij}}$a pesar de${\displaystyle \gamma >0}$.

La vagamente exigida "similitud" entre M y X puede explicarse de la siguiente manera: IPFP (y por lo tanto RAS) mantiene las proporciones de productos cruzados, es decir

${\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{\text{ and }}i\neq h,\quad j\neq k}$

desde${\displaystyle m_{ij}^{(\eta )}=a_{i}^{(\eta )}b_{j}^{(\eta )}x_{ij}.}$

Esta propiedad a veces se denomina conservación de la estructura y conduce directamente a la interpretación geométrica de las tablas de contingencia y a la prueba de convergencia en el artículo fundamental de Fienberg (1970).

La estimación directa de factores (algoritmo 2) es generalmente la forma más eficiente de resolver el IPF: mientras que una forma del IPFP clásico necesita

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

operaciones elementales en cada paso de iteración (incluido un paso de ajuste de fila y columna), la estimación de factores solo necesita

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

operaciones que son al menos un orden de magnitud más rápidas que el IPFP clásico.

IPFP se puede utilizar para estimar tablas de contingencia cuasi-independientes (incompletas) esperadas, con${\displaystyle u_{i}=x_{i+},v_{j}=x_{+j}}$, y${\displaystyle m_{ij}^{0}=1}$para las celdas incluidas y${\displaystyle m_{ij}^{0}=0}$para celdas excluidas. Para tablas de contingencia totalmente independientes (completas), la estimación con IPFP concluye exactamente en un ciclo.

Las condiciones necesarias y suficientes para la existencia y unicidad de los MLE son complicadas en el caso general (véase ^{[ 22 ]} ), pero las condiciones suficientes para tablas bidimensionales son simples:

• los marginales de la tabla observada no se desvanecen (es decir,${\displaystyle x_{i+}>0,\ x_{+j}>0}$) y
• La tabla observada es inseparable (es decir, la tabla no se transforma en una forma diagonal por bloques).

Si existen MLE únicos, IPFP exhibe convergencia lineal en el peor de los casos (Fienberg 1970), pero también se ha observado convergencia exponencial (Pukelsheim y Simeone 2009). Si un estimador directo (es decir, una forma cerrada de${\displaystyle ({\hat {m}}_{ij})}$Si existe un MLE único, IPFP converge después de 2 iteraciones. Si no existen MLE únicos, IPFP converge hacia los llamados MLE extendidos por diseño (Haberman 1974), pero la convergencia puede ser arbitrariamente lenta y a menudo computacionalmente inviable.

Si todos los valores observados son estrictamente positivos, se garantiza la existencia y unicidad de los estimadores de máxima verosimilitud y, por lo tanto, la convergencia.

Considere la siguiente tabla, que incluye las sumas y los objetivos de las filas y columnas.

Para ejecutar el IPFP clásico, primero ajustamos las filas:

El primer paso coincidió exactamente con las sumas de las filas, pero no con las sumas de las columnas. A continuación, ajustamos las columnas:

Ahora las sumas de las columnas coinciden exactamente con sus valores objetivo, pero las sumas de las filas ya no coinciden con los suyos. Después de completar tres ciclos, cada uno con un ajuste de fila y un ajuste de columna, obtenemos una aproximación más precisa:

El paquete R mipfp (actualmente en la versión 3.2) proporciona una implementación multidimensional del procedimiento iterativo de ajuste proporcional tradicional. ^{[ 23 ]} El paquete permite actualizar una matriz N -dimensional con respecto a distribuciones marginales objetivo dadas (que, a su vez, pueden ser multidimensionales).

Python tiene un paquete equivalente, ipfn ^{[ 24 ] [ 25 ]} que se puede instalar a través de pip. El paquete admite objetos de entrada de numpy y pandas.

• Limpieza de datos
• Edición de datos
• Método NM
• Triangulación (ciencias sociales) para la mejora de datos de estudios cuantitativos y cualitativos.