Итеративная пропорциональная подгонка

Итерационная процедура пропорционального подбора ( IPF или IPFP , также известная как бипропорциональный подбор или бипропорция в статистике или экономике (анализ «затраты-выпуск» и т. д.), алгоритм RAS в экономике, сбор статистики опросов и матричное масштабирование в информатике) — это операция поиска подходящей матрицы $X$ которая наиболее близка к исходной матрице $Z$ но с итоговыми суммами строк и столбцов целевой матрицы $Y$ (который обеспечивает ограничения задачи; внутреннюю часть $Y$ неизвестно). Подобранная матрица имеет вид $X=PZQ$, где $P$ и $Q$ являются диагональными матрицами такими, что $X$ имеет поля (суммы строк и столбцов) $Y$. Некоторые алгоритмы могут быть выбраны для выполнения бипропорции. У нас также есть максимизация энтропии, минимизация потерь информации (или перекрестная энтропия) или RAS, который состоит из факторизации строк матрицы для соответствия указанным итоговым суммам строк, а затем факторизации ее столбцов для соответствия указанным итоговым суммам столбцов; каждый шаг обычно нарушает соответствие предыдущего шага, поэтому эти шаги повторяются циклически, по очереди корректируя строки и столбцы, пока все указанные предельные итоги не будут удовлетворительно аппроксимированы. Однако все алгоритмы дают одно и то же решение. В трехмерных и более объемных случаях этапы корректировки применяются поочередно к границам каждого измерения, причем этапы также повторяются циклически.

История

IPF «изобретался заново» много раз, самый первый из них Круитхоф в 1937 году. в отношении телефонного трафика («двухфакторный метод Круитгофа»), Деминг и Стефан в 1940 г. за корректировку перекрестных таблиц переписи и Г.В. Шелейховский за движение транспорта по сообщению Брегмана. (Деминг и Стефан предложили IPFP в качестве алгоритма, ведущего к минимизации статистики Пирсона X-квадрат , но, как позже сообщил Стефан, это не так ). Ранние доказательства уникальности и конвергенции были получены Синкхорном (1964): Бахарах (1965), Бишоп (1967), и Финберг (1970). Доказательство Бишопа о том, что IPFP находит оценку максимального правдоподобия для любого числа измерений, расширило доказательство Брауна 1959 года для случаев 2x2x2.... Доказательство Файнберга с помощью дифференциальной геометрии использует постоянные коэффициенты перекрестного произведения метода для строго положительных таблиц. Чисар (1975). нашел необходимые и достаточные условия для общих таблиц, имеющих нулевые записи. Пукельсхайм и Симеоне (2009) дать дальнейшие результаты по сходимости и поведению ошибок.

Исчерпывающее описание алгоритма и его математических основ можно найти в книге Бишопа и др. (1975). Идеал (2016) дает более поздний опрос.

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

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

Бипропорциональный

Бипропорция, какой бы алгоритм ни использовался для ее решения, представляет собой следующую концепцию: $Z$, матрица $Y$ и матрица $X$ известны вещественные неотрицательные матрицы размерности $n,m$; интерьер $Y$ неизвестно и $X$ ищется так, что $X$ имеет те же пределы, что и $Y$, то есть $Xs=Ys$ и $s'X=s'Y$ ( $s$ вектор суммы) и такой, что $X$ близко к $Z$ следуя заданному критерию, подобранная матрица имеет вид $X=K(Z,Y)=PZQ$, где $P$ и $Q$ являются диагональными матрицами.

$min\sum _{i}\sum _{j}x_{ij}\log(x_{ij}/z_{ij})$ ул. $\sum _{j}x_{ij}=y_{i.}$, ∀ $i$ и $\sum _{i}x_{ij}=y_{.j}$, ∀ $j$.Лагранжиан $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})$.

Таким образом $x_{ij}=z_{ij}\exp -(1+p_{i}+q_{j})$, для ∀ $i,j$,

который после позирования $P_{i}=\exp -(1+p_{i})$ и $Q_{j}=\exp -q_{j}$, дает

$x_{ij}=P_{i}z_{ij}Q_{j}$, ∀ $i,j$, то есть, $X=PZQ$,

с $P_{i}=z_{i}.(\sum _{j}z_{ij}Q_{j})^{-1}$, ∀ $i$ и $Q_{j}=z_{.j}(\sum _{i}z_{ij}P_{i})^{-1}$, ∀ $j$. $P_{i}$ и $Q_{j}$ сформировать систему, которую можно решать итеративно:

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

Решение $X$ не зависит от выбранной инициализации (т.е. мы можем начать с $q_{j}^{(0)}=1$, ∀ $j$ или через $p_{i}^{(0)}=1$, ∀ $i$. Если матрица $Z$ является «неразложимым», то этот процесс имеет единственную неподвижную точку, поскольку он выводится из программы, где функция является выпуклой и непрерывно выводимой функцией, определенной на компактном множестве. В некоторых случаях решения может не существовать: см. пример де Менара, приведенный Миллером и Блэром (Miller RE & Blair PD (2009) Анализ ввода-вывода: основы и расширения, второе издание, Кембридж (Великобритания): Cambridge University Press, стр. 335-336 (в свободном доступе)).

Некоторые свойства (см. де Меснард (1994)):

Недостаток информации: если $Z$ не несет никакой информации, т.е. $z_{ij}=z$, ∀ $i,j$ затем $X=PQ$.

Идемпотентность: $X=K(Z,Y)=Z$ если $Y$ имеет те же пределы, что и $Z$.

Состав бипропорций: $K(K(Z,Y_{1}),Y_{2}=K(Z,Y_{2})$; $K(...K(Z,Y_{1}),Y_{2})...Z_{N})=K(Z,Y_{N})$.

Нули: ноль в $Z$ прогнозируется как ноль в $X$. Таким образом, блочно-диагональная матрица проецируется как блочно-диагональная матрица, а треугольная матрица проецируется как треугольная матрица.

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

Теорема «единственности»: Если $K^{q}$ любой неопределенный алгоритм, с ${\hat {X}}=K^{q}(Z,Y)=UZV$, $U$ и $V$ будучи неизвестным, то $U$ и $V$ всегда можно преобразовать в стандартную форму $P$ и $Q$. Демонстрация вызывает некоторые из вышеперечисленных свойств, в частности, теорему о сепарабельных модификациях и о составе бипропорций.

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

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

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

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

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

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

Примечания:

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

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

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

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

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

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

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

Примечания:

• Два варианта алгоритма математически эквивалентны, как видно с помощью формальной индукции. При факторной оценке нет необходимости фактически вычислять значения каждого цикла. ${\hat {m}}_{ij}^{(\eta )}$.
• Факторизация не является единственной, поскольку она $m_{ij}=a_{i}b_{j}x_{ij}=(\gamma a_{i})({\frac {1}{\gamma }}b_{j})x_{ij}$ для всех $\gamma >0$.

Обсуждение

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

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

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

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

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

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

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

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

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

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

Сравнение с НМ-методом

Подобно ИПФ, НМ-метод также является операцией нахождения матрицы $X$ что является «ближайшим» к матрице $Z$ ( $Z\in \mathbb {N} ^{n\times m}$), в то время как его итоги по строкам и итоги по столбцам идентичны итоговым значениям целевой матрицы $Y$ $(Y\in \mathbb {N} ^{n\times m})$.

Однако существуют различия между НМ-методом и ИПФ . Например, НМ-метод определяет близость матриц одного размера иначе, чем IPF. Также был разработан НМ-метод для решения матричных задач. $X$ в задачах, где матрица ${\boldsymbol {Z}}$ не является выборкой из генеральной совокупности, характеризуемой итогами строк и итогами столбцов матрицы $Y$, но представляет другую популяцию . Напротив, матрица ${\boldsymbol {Z}}$ представляет собой выборку из этой совокупности в задачах, где IPF применяется в качестве средства оценки максимального правдоподобия .

Макдональд (2023) спокойно воспринимает вывод Насзоди (2023) что IPF подходит для задач коррекции выборки, но не для генерации контрфактических данных. Подобно Насзоди, Макдональд также задается вопросом, сохраняют ли пропорциональные преобразования строк и столбцов IPF структуру ассоциаций в таблице непредвиденных обстоятельств, которая позволяет нам изучать социальную мобильность.

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

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

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

Если существуют уникальные MLE, IPFP в худшем случае демонстрирует линейную сходимость (Fienberg 1970), но также наблюдается экспоненциальная сходимость (Pukelsheim and Simeone 2009). Если прямая оценка (т.е. закрытая форма $({\hat {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.2) обеспечивает многомерную реализацию традиционной итеративной процедуры пропорциональной подгонки. Пакет позволяет обновлять N -мерный массив относительно заданных целевых предельных распределений (которые, в свою очередь, могут быть многомерными).

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

См. также

• Очистка данных
• Редактирование данных
• НМ-метод
• Триангуляция (социальные науки) для количественного и качественного улучшения данных исследования.