Итерационная пропорциональная подгонка - Iterative proportional fitting

В итеративная процедура пропорциональной подгонки (IPF или же IPFP, также известный как бипропорциональный фитинг в статистике, Алгоритм RAS^[1] в экономике, сгребание в статистике опросов, и масштабирование матрицы в информатике) является итерационный алгоритм для пропорциональной корректировки матрицы или таблицы непредвиденных обстоятельств неотрицательных элементов для создания новой «аналогичной» таблицы с заданными положительными предельными суммами как минимум в двух измерениях. В двух измерениях корректировка заключается в разложении строк матрицы на множители для соответствия указанным суммам строк, а затем факторизации ее столбцов для соответствия указанным итоговым значениям столбцов. Каждый шаг обычно нарушает совпадение предыдущего шага, поэтому эти шаги повторяются циклами, изменяя по очереди строки и столбцы, пока все указанные предельные итоги не будут удовлетворительно аппроксимированы. В трехмерных и более-мерных случаях этапы настройки применяются по очереди для маргинальных значений каждого измерения, причем этапы также повторяются циклами.

История

IPF был изобретен повторно много раз, самый ранний - Круитхофом в 1937 году. ^[2]в отношении телефонного трафика ("метод двойного фактора Круитхофа"), Деминг и Стефан в 1940 году^[3] для корректировки перекрестных таблиц переписи, и Г.В. Шелейховскому за пробки, сообщает Брегман.^[4] (Деминг и Стефан предложили IPFP как алгоритм, ведущий к минимизатору Статистика Пирсона X-квадрат, о чем позже сообщил Стефан не,^[5]. Ранние доказательства уникальности и сходимости пришли из Синкхорна (1964),^[6] Бахарах (1965),^[7] Епископ (1967),^[8] и Fienberg (1970).^[9]. Доказательство Бишопа, что IPFP находит оценку максимального правдоподобия для любого числа измерений, расширило доказательство Брауна 1959 года для случаев 2x2x2 ... Доказательство Финберга дифференциальная геометрия использует постоянные отношения между продуктами метода для строго положительных таблиц. Цисар (1975).^[10] нашли необходимые и достаточные условия для общих таблиц с нулевыми записями. Пукельсхайм и Симеоне (2009)^[11] дать дальнейшие результаты о сходимости и поведении ошибок.

Исчерпывающее описание алгоритма и его математических основ можно найти в книге Bishop et al. (1975).^[12] Идель (2016)^[13] дает более свежий обзор.

Другие общие алгоритмы могут быть изменены для получения того же ограничения, что и IPFP, например Метод Ньютона – Рафсона и EM алгоритм. В большинстве случаев IPFP предпочтительнее из-за его скорости вычислений, низких требований к памяти, числовой стабильности и алгебраической простоты.

Приложения IPFP выросли и включают распределение поездок модели, Fratar или Furness и другие приложения в транспортном планировании (Ламонд и Стюарт), взвешивание обследований, синтез перекрестно классифицированных демографических данных, корректировка модели ввода-вывода в экономике, оценивая ожидаемые квазинезависимые таблицы непредвиденных обстоятельств, бипропорциональное распределение системы политического представительства, и для предварительный кондиционер в линейной алгебре.^[14]

Алгоритм 1 (классический IPF)

Учитывая двусторонний (я × J)-стол ${displaystyle x_ {ij}}$, мы хотим оценить новую таблицу ${displaystyle {hat {m}} _ {ij} = a_ {i} b_ {j} x_ {ij}}$ для всех я и j такие, что маргиналы удовлетворяют ${displaystyle sum _ {j} {hat {m}} _ {ij} = u_ {i},}$ и ${displaystyle sum _ {i} {hat {m}} _ {ij} = v_ {j}}$.

Выберите начальные значения ${displaystyle {hat {m}} _ {ij} ^ {(0)}: = x_ {ij}}$, и для ${displaystyle eta geq 1}$ набор

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

Повторяйте эти шаги до тех пор, пока итоговые значения строк и столбцов не станут достаточно близкими к u и v.

Примечания:

• Для алгоритма в форме RAS определите оператор диагонализации ${displaystyle diag: mathbb {R} ^ {k} longrightarrow mathbb {R} ^ {k imes k}}$, который создает (диагональную) матрицу с входным вектором на главной диагонали и нулем в другом месте. Затем для каждой корректировки строки пусть ${displaystyle R ^ {eta} = diag ({frac {u_ {i}} {sum _ {j} m_ {ij} ^ {(2eta -2)}}})}$, откуда ${displaystyle M ^ {2eta -1} = R ^ {eta} M ^ {2eta -2}}$. Аналогичным образом настройка каждого столбца ${displaystyle S ^ {eta} = diag ({frac {v_ {i}} {sum _ {i} m_ {ij} ^ {(2eta -1)}}})}$, откуда ${displaystyle M ^ {2eta} = M ^ {2eta -1} S ^ {eta}}$. Сводя операции к необходимым, легко видеть, что RAS делает то же самое, что и классический IPF. На практике невозможно реализовать фактическое матричное умножение на все матрицы R и S; Форма RAS - это удобство больше для обозначения, чем для вычислений.

Алгоритм 2 (факторная оценка)

Предположим те же настройки, что и в классическом IPFP. В качестве альтернативы мы можем оценить факторы строки и столбца отдельно: Выберите начальные значения ${displaystyle {hat {b}} _ {j} ^ {(0)}: = 1}$, и для ${displaystyle eta geq 1}$ набор

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

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

Повторяйте эти шаги до тех пор, пока последовательные изменения a и b не станут достаточно незначительными (показывая, что итоговые суммы строк и столбцов близки к u и v).

Наконец, матрица результатов${displaystyle {hat {m}} _ {ij} = {hat {a}} _ {i} ^ {(eta)} {hat {b}} _ {j} ^ {(eta)} x_ {ij}}$

Примечания:

• Два варианта алгоритма математически эквивалентны, что можно увидеть с помощью формальной индукции. При факторной оценке нет необходимости фактически вычислять каждый цикл ${displaystyle {hat {m}} _ {ij} ^ {(eta)}}$.

• Факторизация не уникальна, так как она ${displaystyle m_ {ij} = a_ {i} b_ {j} x_ {ij} = (gamma a_ {i}) ({frac {1} {gamma}} b_ {j}) x_ {ij}}$ для всех ${displaystyle gamma> 0}$.

Обсуждение

Смутно требуемое «сходство» между M и X можно объяснить следующим образом: IPFP (и, следовательно, RAS) поддерживает соотношения между продуктами, т.е.

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

поскольку ${displaystyle m_ {ij} ^ {(eta)} = a_ {i} ^ {(eta)} b_ {j} ^ {(eta)} x_ {ij}.}$

Это свойство иногда называют сохранение структуры и непосредственно приводит к геометрической интерпретации таблиц сопряженности и доказательству сходимости в основополагающей статье Финберга (1970).

Прямая оценка фактора (алгоритм 2), как правило, является более эффективным способом решения IPF: в то время как форма классического IPFP требует

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

элементарные операции на каждом шаге итерации (включая шаг подгонки строки и столбца), требуется только оценка фактора

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

операции как минимум на порядок быстрее, чем у классического IPFP.

IPFP можно использовать для оценки ожидаемых квазинезависимых (неполных) таблиц непредвиденных обстоятельств, с ${displaystyle u_ {i} = x_ {i +}, v_ {j} = x _ {+ j}}$, и ${displaystyle m_ {ij} ^ {0} = 1}$ для включенных ячеек и ${displaystyle m_ {ij} ^ {0} = 0}$ для исключенных ячеек. Для полностью независимых (полных) таблиц непредвиденных обстоятельств оценка с помощью IPFP завершается ровно за один цикл.

Существование и уникальность ОМО

Необходимые и достаточные условия существования и единственности МЛЭ в общем случае усложняются (см.^[15]), но достаточные условия для двумерных таблиц просты:

• маргиналы наблюдаемой таблицы не исчезают (т. е. ${displaystyle x_ {i +}> 0, x _ {+ j}> 0}$) и
• наблюдаемая таблица неразделима (то есть таблица не переставляется в блочно-диагональную форму).

Если существуют уникальные MLE, IPFP демонстрирует линейную сходимость в худшем случае (Fienberg 1970), но также наблюдается экспоненциальная сходимость (Pukelsheim and Simeone 2009). Если прямая оценка (т. Е. Замкнутая форма ${displaystyle ({шляпа {m}} _ {ij})}$) существует, IPFP сходится после 2 итераций. Если уникальных MLE не существует, IPFP сходится к так называемому расширенные MLE по замыслу (Haberman 1974), но сходимость может быть сколь угодно медленной и зачастую вычислительно невыполнимой.

Если все наблюдаемые значения строго положительны, гарантируется существование и уникальность MLE и, следовательно, сходимость.

Пример

Рассмотрим следующую таблицу с суммами по строкам и столбцам и целевыми значениями.

	1	2	3	4	ОБЩИЙ	ЦЕЛЬ
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
ОБЩИЙ	125	190	230	255	800
ЦЕЛЬ	200	300	400	100		1000

Для выполнения классического IPFP сначала настраиваем строки:

	1	2	3	4	ОБЩИЙ	ЦЕЛЬ
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
ОБЩИЙ	161.81	241.50	281.58	315.11	1000.00
ЦЕЛЬ	200	300	400	100		1000

Первый шаг точно соответствовал суммам строк, но не суммам столбцов. Затем мы настраиваем столбцы:

	1	2	3	4	ОБЩИЙ	ЦЕЛЬ
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
ОБЩИЙ	200.00	300.00	400.00	100.00	1000.00
ЦЕЛЬ	200	300	400	100		1000

Теперь суммы столбцов точно соответствуют их целям, но суммы строк больше не соответствуют их. После выполнения трех циклов, каждый с корректировкой строки и корректировкой столбца, мы получаем более точное приближение:

	1	2	3	4	ОБЩИЙ	ЦЕЛЬ
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
ОБЩИЙ	200.00	300.00	400.00	100.00	1000.00
ЦЕЛЬ	200	300	400	100		1000

Выполнение

Пакет R mipfp (в настоящее время в версии 3.1) обеспечивает многомерную реализацию традиционной итерационной процедуры пропорциональной подгонки.^[16] Пакет позволяет обновлять N-мерный массив относительно заданных целевых маржинальных распределений (которые, в свою очередь, могут быть многомерными).

У Python есть эквивалентный пакет, ipfn^[17][18] который можно установить через pip. Пакет поддерживает входные объекты numpy и pandas.

Рекомендации