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, rastrillado en estadísticas de encuestas y escalado matricial en informática. ) es la operación de encontrar la matriz ajustada cuál es el más cercano a una matriz inicial pero con los totales de fila y columna de una matriz de destino (que proporciona las limitaciones del problema; el interior de es desconocido). La matriz ajustada tiene la forma, dónde y son matrices diagonales tales que tiene los márgenes (sumas de filas y columnas) de . Se pueden elegir algunos algoritmos para realizar la biproporción. También tenemos la maximización de entropía, [2] [3] minimización de 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 la columna especificada totales; cada paso suele perturbar 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 tridimensionales o más, los pasos de ajuste se aplican a los marginales de cada dimensión a su vez, los pasos también se repiten en ciclos.
Historia
La FPI se ha "reinventado" muchas veces, la primera de ellas 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 las 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-cuadrado de Pearson , que Stephan luego informó que no lo hace . [9] Las primeras pruebas de unicidad y convergencia provienen de Sinkhorn (1964), [ 10] Bacharach (1965), [11] Bishop (1967), [12] y Fienberg (1970). [13] La prueba de Bishop de que IPFP encuentra el estimador de máxima verosimilitud para cualquier número de dimensiones extendió una prueba de 1959 de Brown para 2x2x2. ... casos. La demostración de Fienberg por geometría diferencial explota las relaciones constantes entre productos del método, para tablas estrictamente positivas. Csiszár (1975). [14] encontró condiciones necesarias y suficientes para tablas generales que tienen entradas cero. Pukelsheim y Simeone (2009) [15] dar más resultados sobre la convergencia y el comportamiento de 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 encuesta más reciente.
Se pueden modificar otros algoritmos generales para producir 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 IPFP debido a su velocidad computacional, bajos requisitos de almacenamiento, estabilidad numérica y simplicidad algebraica.
Las aplicaciones de IPFP han crecido para incluir modelos de distribución de viajes , Fratar o Furness y otras aplicaciones en la planificación del transporte (Lamond y Stewart), ponderación de encuestas, síntesis de datos demográficos de clasificación cruzada, ajuste de modelos de insumo-producto en economía, estimación cuasi-independiente esperada tablas de contingencia , sistemas de distribución biproporcional de representación política y para un precondicionador en álgebra lineal. [18]
Biproporción
La biproporción, sea cual sea el algoritmo utilizado para resolverlo, es el siguiente concepto: , matriz y matriz son matrices de dimensión reales no negativas conocidas ; el interior de es desconocido y se busca de tal manera que tiene los mismos márgenes que , es decir y ( siendo el vector de suma, y tal que está cerrado a siguiendo un criterio dado, la matriz ajustada es de la forma , dónde y son matrices diagonales.
S t, ∀ y , ∀. El lagrangiano es.
Por lo tanto , por ∀,
que, después de posar y , rinde
, ∀, es decir, ,
con , ∀ y , ∀. y forman un sistema que se puede resolver iterativamente:
, ∀ y , ∀.
La solución es independiente de la inicialización elegida (es decir, podemos empezar por , ∀ o por, ∀. Si la matrizes “indecomponible”, entonces este proceso tiene un punto fijo único porque se deduce del programa un programa donde la función es una función 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, Segunda edición, Cambridge (Reino Unido): Cambridge University Press, p. 335-336 (disponible gratuitamente)).
Algunas propiedades (ver de Mesnard (1994)):
Falta de información: si no trae información, es decir, , ∀ luego .
Idempotencia: Si tiene los mismos márgenes que .
Composición de biproporciones: ; .
Ceros: un cero en se proyecta como un cero en . Así, una matriz bloque-diagonal se proyecta como una matriz bloque-diagonal y una matriz triangular se proyecta como una matriz triangular.
Teorema de modificaciones separables: si se premultiplica por una matriz diagonal y / o posmultiplica por una matriz diagonal, entonces la solución no se modifica.
Teorema de la "unicidad": si es cualquier algoritmo no especificado, con , y siendo desconocido, entonces y siempre se puede cambiar a la forma estándar de y . Las demostraciones llaman a algunas de las propiedades anteriores, particularmente el Teorema de modificaciones separables y la composición de biproporciones.
Algoritmo 1 (IPF clásico)
Dada una tabla bidireccional ( I × J ), deseamos estimar una nueva tabla para todo i y j tales que los marginales satisfagan y .
Elija valores iniciales , y para colocar
Repita estos pasos hasta que los totales de filas y columnas estén lo suficientemente cerca de uy v.
Notas:
- Para la forma RAS del algoritmo, defina el operador de diagonalización , que produce una matriz (diagonal) con su vector de entrada en la diagonal principal y cero en otra parte. Luego, para cada ajuste de fila, deje, a partir del cual . De manera similar, cada ajuste de columna, a partir del cual . Reduciendo las operaciones a las necesarias, se puede ver fácilmente que RAS hace lo mismo que la IPF clásica. En la práctica, no se implementaría la multiplicación de matrices real con las matrices R y S completas; la forma RAS es más una conveniencia de notación que de computación.
Algoritmo 2 (estimación de factores)
Suponga la misma configuración que en la IPFP clásica. Alternativamente, podemos estimar los factores de fila y columna por separado: Elija valores iniciales, y para colocar
Repita estos pasos hasta que los cambios sucesivos de ayb sean suficientemente insignificantes (lo que indica que las sumas de filas y columnas resultantes están cerca de u y v).
Finalmente, la matriz de resultados es
Notas:
- Las dos variantes del algoritmo son matemáticamente equivalentes, como puede verse por inducción formal. Con la estimación de factores, no es necesario calcular realmente el valor de cada ciclo..
- La factorización no es única, ya que es para todos .
Discusión
La 'similitud' vagamente demandada entre M y X se puede explicar de la siguiente manera: IPFP (y por lo tanto RAS) mantiene las proporciones de productos cruzados, es decir
desde
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 la prueba de convergencia en el artículo fundamental de Fienberg (1970).
La estimación directa del factor (algoritmo 2) es generalmente la forma más eficiente de resolver la IPF: mientras que una forma de la IPFP clásica necesita
operaciones elementales en cada paso de iteración (incluido un paso de ajuste de fila y columna), la estimación de factores solo necesita
las operaciones son al menos un orden en magnitud más rápidas que las IPFP clásicas.
El IPFP se puede utilizar para estimar tablas de contingencia cuasi-independientes (incompletas) esperadas, con , y para celdas incluidas y para celdas excluidas. Para tablas de contingencia completamente independientes (completas), la estimación con IPFP concluye exactamente en un ciclo.
Existencia y singularidad de los MLE
Las condiciones necesarias y suficientes para la existencia y unicidad de los MLE son complicadas en el caso general (ver [19] ), pero las condiciones suficientes para las tablas bidimensionales son simples:
- los márgenes de la tabla observada no desaparecen (es decir, ) y
- la mesa observada es inseparable (es decir, la mesa no permuta a una forma de bloque en diagonal).
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) existe, 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 MLE y, por lo tanto, la convergencia.
Ejemplo
Considere la siguiente tabla, dada con las sumas y objetivos de filas y columnas.
1 | 2 | 3 | 4 | TOTAL | OBJETIVO | |
---|---|---|---|---|---|---|
1 | 40 | 30 | 20 | 10 | 100 | 150 |
2 | 35 | 50 | 100 | 75 | 260 | 300 |
3 | 30 | 80 | 70 | 120 | 300 | 400 |
4 | 20 | 30 | 40 | 50 | 140 | 150 |
TOTAL | 125 | 190 | 230 | 255 | 800 | |
OBJETIVO | 200 | 300 | 400 | 100 | 1000 |
Para ejecutar el IPFP clásico, primero ajustamos las filas:
1 | 2 | 3 | 4 | TOTAL | OBJETIVO | |
---|---|---|---|---|---|---|
1 | 60,00 | 45,00 | 30,00 | 15.00 | 150,00 | 150 |
2 | 40,38 | 57,69 | 115,38 | 86,54 | 300,00 | 300 |
3 | 40,00 | 106,67 | 93,33 | 160,00 | 400,00 | 400 |
4 | 21.43 | 32,14 | 42,86 | 53,57 | 150,00 | 150 |
TOTAL | 161,81 | 241,50 | 281.58 | 315.11 | 1000,00 | |
OBJETIVO | 200 | 300 | 400 | 100 | 1000 |
El primer paso coincidió exactamente con las sumas de las filas, pero no las de las columnas. A continuación ajustamos las columnas:
1 | 2 | 3 | 4 | TOTAL | OBJETIVO | |
---|---|---|---|---|---|---|
1 | 74,16 | 55,90 | 42,62 | 4,76 | 177,44 | 150 |
2 | 49,92 | 71,67 | 163,91 | 27,46 | 312,96 | 300 |
3 | 49,44 | 132,50 | 132,59 | 50,78 | 365,31 | 400 |
4 | 26,49 | 39,93 | 60,88 | 17.00 | 144.30 | 150 |
TOTAL | 200,00 | 300,00 | 400,00 | 100,00 | 1000,00 | |
OBJETIVO | 200 | 300 | 400 | 100 | 1000 |
Ahora las sumas de las columnas coinciden exactamente con sus objetivos, pero las sumas de las filas ya no coinciden con las suyas. Después de completar tres ciclos, cada uno con un ajuste de fila y un ajuste de columna, obtenemos una aproximación más cercana:
1 | 2 | 3 | 4 | TOTAL | OBJETIVO | |
---|---|---|---|---|---|---|
1 | 64,61 | 46,28 | 35,42 | 3,83 | 150,13 | 150 |
2 | 49,95 | 68.15 | 156,49 | 25,37 | 299,96 | 300 |
3 | 56,70 | 144,40 | 145.06 | 53,76 | 399,92 | 400 |
4 | 28,74 | 41.18 | 63.03 | 17.03 | 149,99 | 150 |
TOTAL | 200,00 | 300,00 | 400,00 | 100,00 | 1000,00 | |
OBJETIVO | 200 | 300 | 400 | 100 | 1000 |
Implementación
El paquete R mipfp (actualmente en la versión 3.1) proporciona una implementación multidimensional del procedimiento tradicional de ajuste proporcional iterativo. [20] El paquete permite la actualización de una matriz N- dimensional con respecto a las distribuciones marginales objetivo dadas (que, a su vez, pueden ser multidimensionales).
Python tiene un paquete equivalente, ipfn [21] [22] que se puede instalar a través de pip. El paquete admite objetos de entrada numpy y pandas.
Ver también
- Limpieza de datos
- Edición de datos
- Triangulación (ciencias sociales) para la mejora de datos de estudios cuantitativos y cualitativos.
Referencias
- ^ Bacharach, M. (1965). "Estimación de matrices no negativas a partir de datos marginales". Revista económica internacional . Publicación de Blackwell. 6 (3): 294–310. doi : 10.2307 / 2525582 . JSTOR 2525582 .
- ^ Jaynes ET (1957) Teoría de la información y mecánica estadística, Physical Review, 106: 620-30.
- ^ Wilson AG (1970) Entropía en el modelado urbano y regional. Londres: Pion LTD, Monografía en análisis de sistemas espaciales y ambientales.
- ^ Kullback S. & Leibler RA (1951) sobre información y suficiencia, Annals of Mathematics and Statistics, 22 (1951) 79-86.
- ^ de Mesnard, L. (1994). "Unicidad de biproporción". Revista SIAM sobre Análisis y Aplicaciones Matriciales . 15 (2): 490–495. doi : 10.1137 / S0895479891222507 .https://www.researchgate.net/publication/243095013_Unicity_of_Biproportion
- ^ Kruithof, J. (1937). Telefoonverkeersrekening (Cálculo del tráfico telefónico), De Ingenieur, 52, 8, E15-E25
- ^ Deming, NOSOTROS ; Stephan, F. F. (1940). "En un ajuste por mínimos cuadrados de una tabla de frecuencia muestreada cuando se conocen los totales marginales esperados" . Anales de estadística matemática . 11 (4): 427–444. doi : 10.1214 / aoms / 1177731829 . Señor 0003527 .
- ^ Lamond, B. y Stewart, NF (1981) Método de equilibrio de Bregman. Investigación de transporte 15B, 239-248.
- ^ Stephan, FF (1942). "Método iterativo de ajuste de tablas de frecuencia cuando se conocen los márgenes esperados" . Anales de estadística matemática . 13 (2): 166-178. doi : 10.1214 / aoms / 1177731604 . Señor 0006674 . Zbl 0060.31505 .
- ^ Sinkhorn, Richard (1964). “Relación entre matrices positivas arbitrarias y matrices doblemente estocásticas”. En: Annals of Mathematical Statistics 35.2, págs. 876–879.
- ^ Bacharach, Michael (1965). "Estimación de matrices no negativas a partir de datos marginales". En: International Economic Review 6.3, págs. 294–310.
- ^ Obispo, YMM (1967). “Tablas de contingencia multidimensionales: estimaciones de celda”. Tesis doctoral. Universidad Harvard.
- ^ Fienberg, SE (1970). "Un procedimiento iterativo para la estimación en tablas de contingencia" . Anales de estadística matemática . 41 (3): 907–917. doi : 10.1214 / aoms / 1177696968 . JSTOR 2239244 . Señor 0266394 . Zbl 0198.23401 .
- ^ Csiszár, I. (1975). " I- divergencia de distribuciones de probabilidad y problemas de minimización" . Anales de probabilidad . 3 (1): 146-158. doi : 10.1214 / aop / 1176996454 . JSTOR 2959270 . Señor 0365798 . Zbl 0318.60013 .
- ^ "Sobre el procedimiento de ajuste proporcional iterativo: estructura de puntos de acumulación y análisis de error L1" . Pukelsheim, F. y Simeone, B . Consultado el 28 de junio de 2009 .
- ^ Obispo, YMM ; Fienberg, SE ; Holanda, PW (1975). Análisis multivariado discreto: teoría y práctica . Prensa del MIT. ISBN 978-0-262-02113-5. Señor 0381130 .
- ^ Martin Idel (2016) Una revisión de la escala matricial y la forma normal de Sinkhorn para matrices y mapas positivos preprint arXiv https://arxiv.org/pdf/1609.06349.pdf
- ^ Bradley, AM (2010) Algoritmos para el equilibrio de matrices y su aplicación a métodos cuasi-newton de memoria limitada. Doctor. tesis, Instituto de Ingeniería Computacional y Matemática, Universidad de Stanford, 2010
- ^ Haberman, SJ (1974). El análisis de datos de frecuencia . Univ. Prensa de Chicago. ISBN 978-0-226-31184-5.
- ^ Barthélemy, Johan; Suesse, Thomas. "mipfp: ajuste proporcional iterativo multidimensional" . CRAN . Consultado el 23 de febrero de 2015 .
- ^ "ipfn: pip" .
- ^ "ipfn: github" .