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

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)-стол , мы хотим оценить новую таблицу для всех я и j такие, что маргиналы удовлетворяют и .

Выберите начальные значения , и для набор

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

Примечания:

  • Для алгоритма в форме RAS определите оператор диагонализации , который создает (диагональную) матрицу с входным вектором на главной диагонали и нулем в другом месте. Затем для каждой корректировки строки пусть , откуда . Аналогичным образом настройка каждого столбца , откуда . Сводя операции к необходимым, легко видеть, что RAS делает то же самое, что и классический IPF. На практике невозможно реализовать фактическое матричное умножение на все матрицы R и S; Форма RAS - это удобство больше для обозначения, чем для вычислений.

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

Предположим те же настройки, что и в классическом IPFP. В качестве альтернативы мы можем оценить факторы строки и столбца отдельно: Выберите начальные значения , и для набор

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

Наконец, матрица результатов

Примечания:

  • Два варианта алгоритма математически эквивалентны, что можно увидеть с помощью формальной индукции. При факторной оценке нет необходимости фактически вычислять каждый цикл .
  • Факторизация не уникальна, так как она для всех .

Обсуждение

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

поскольку

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

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

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

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

IPFP можно использовать для оценки ожидаемых квазинезависимых (неполных) таблиц непредвиденных обстоятельств, с , и для включенных ячеек и для исключенных ячеек. Для полностью независимых (полных) таблиц непредвиденных обстоятельств оценка с помощью IPFP завершается ровно за один цикл.

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

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

  • маргиналы наблюдаемой таблицы не исчезают (т. е. ) и
  • наблюдаемая таблица неразделима (то есть таблица не переставляется в блочно-диагональную форму).

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

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

Пример

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

1234ОБЩИЙЦЕЛЬ
140302010100150
2355010075260300
3308070120300400
420304050140150
ОБЩИЙ125190230255800
ЦЕЛЬ2003004001001000

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

1234ОБЩИЙЦЕЛЬ
160.0045.0030.0015.00150.00150
240.3857.69115.3886.54300.00300
340.00106.6793.33160.00400.00400
421.4332.1442.8653.57150.00150
ОБЩИЙ161.81241.50281.58315.111000.00
ЦЕЛЬ2003004001001000

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

1234ОБЩИЙЦЕЛЬ
174.1655.9042.624.76177.44150
249.9271.67163.9127.46312.96300
349.44132.50132.5950.78365.31400
426.4939.9360.8817.00144.30150
ОБЩИЙ200.00300.00400.00100.001000.00
ЦЕЛЬ2003004001001000

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

1234ОБЩИЙЦЕЛЬ
164.6146.2835.423.83150.13150
249.9568.15156.4925.37299.96300
356.70144.40145.0653.76399.92400
428.7441.1863.0317.03149.99150
ОБЩИЙ200.00300.00400.00100.001000.00
ЦЕЛЬ2003004001001000

Выполнение

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

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

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

  1. ^ Бахарах, М. (1965). «Оценка неотрицательных матриц по маржинальным данным». Международное экономическое обозрение. Блэквелл Паблишинг. 6 (3): 294–310. Дои:10.2307/2525582. JSTOR 2525582.
  2. ^ Круитхоф, Дж. (1937). Telefoonverkeersrekening (Расчет телефонного трафика), De Ingenieur, 52, 8, E15-E25
  3. ^ Деминг, В. Э.; Стефан, Ф. Ф. (1940). "О корректировке методом наименьших квадратов выборочной таблицы частот, когда известны ожидаемые предельные итоги". Анналы математической статистики. 11 (4): 427–444. Дои:10.1214 / aoms / 1177731829. МИСТЕР 0003527.
  4. ^ Ламонд Б. и Стюарт Н.Ф. (1981) Метод балансировки Брегмана. Транспортные исследования 15B, 239-248.
  5. ^ Стефан, Ф. Ф. (1942). «Итерационный метод корректировки частотных таблиц, когда известны ожидаемые запасы». Анналы математической статистики. 13 (2): 166–178. Дои:10.1214 / aoms / 1177731604. МИСТЕР 0006674. Zbl 0060.31505.
  6. ^ Синкхорн, Ричард (1964). «Связь между произвольными положительными матрицами и двустохастическими матрицами». В кн .: Анналы математической статистики, 35.2, с. 876–879.
  7. ^ Бахарах, Майкл (1965). «Оценка неотрицательных матриц по предельным данным». В: Международное экономическое обозрение 6.3, стр. 294–310.
  8. ^ Епископ, Ю. М. М. (1967). «Многомерные таблицы непредвиденных обстоятельств: оценки ячеек». Кандидатская диссертация в Гарвардском университете.
  9. ^ Файнберг, С.Э. (1970). «Итерационная процедура оценки в таблицах непредвиденных обстоятельств». Анналы математической статистики. 41 (3): 907–917. Дои:10.1214 / aoms / 1177696968. JSTOR 2239244. МИСТЕР 0266394. Zbl 0198.23401.
  10. ^ Цисар, И. (1975). "я-Дивергенция вероятностных распределений и задачи минимизации ». Анналы вероятности. 3 (1): 146–158. Дои:10.1214 / aop / 1176996454. JSTOR 2959270. МИСТЕР 0365798. Zbl 0318.60013.
  11. ^ «Об итерационной процедуре пропорциональной подгонки: структура точек накопления и анализ L1-ошибок». Пукельсхайм Ф. и Симеоне Б.. Получено 2009-06-28.
  12. ^ Епископ, Ю.М.М.; Файнберг, С.Э.; Голландия, П. В. (1975). Дискретный многомерный анализ: теория и практика. MIT Press. ISBN 978-0-262-02113-5. МИСТЕР 0381130.
  13. ^ Мартин Идель (2016) Обзор масштабирования матриц и нормальной формы Синхорна для матриц и положительных карт препринт arXiv https://arxiv.org/pdf/1609.06349.pdf
  14. ^ Брэдли, А. (2010) Алгоритмы уравновешивания матриц и их применение к квазиньютоновским методам с ограниченной памятью. Кандидат наук. диссертация, Институт вычислительной и математической инженерии, Стэнфордский университет, 2010 г.
  15. ^ Хаберман, С. Дж. (1974). Анализ частотных данных. Univ. Чикаго Пресс. ISBN 978-0-226-31184-5.
  16. ^ Бартелеми, Йохан; Сюсс, Томас. "mipfp: многомерная итерационная пропорциональная подгонка". КРАН. Получено 23 февраля 2015.
  17. ^ "ipfn: pip".
  18. ^ "ipfn: github".