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

редактировать

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

СОДЕРЖАНИЕ

  • 1 История
  • 2 Бипропорциональность
  • 3 Алгоритм 1 (классический IPF)
  • 4 Алгоритм 2 (факторная оценка)
  • 5 Обсуждение
  • 6 Существование и уникальность MLE
  • 7 Пример
  • 8 Реализация
  • 9 См. Также
  • 10 Ссылки

История

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

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

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

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

Двупропорциональность

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

м я п я j Икс я j бревно ( Икс я j / z я j ) {\ displaystyle min \ sum _ {i} \ sum _ {j} x_ {ij} \ log (x_ {ij} / z_ {ij})} ул, ∀ и, ∀. Лагранжиан есть. j Икс я j знак равно y я . {\ Displaystyle \ сумма _ {j} x_ {ij} = y_ {i.}} я {\ displaystyle i} я Икс я j знак равно y . j {\ Displaystyle \ сумма _ {я} x_ {ij} = y _ {. j}} j {\ displaystyle j} L знак равно я j Икс я j бревно ( Икс я j / z я j ) - я п я ( y я . - j Икс я j ) - j q j ( y . j - я Икс я j ) {\ 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})}

Таким образом, для ∀, Икс я j знак равно z я j exp - ( 1 + п я + q j ) {\ displaystyle x_ {ij} = z_ {ij} \ exp - (1 + p_ {i} + q_ {j})} я , j {\ displaystyle i, j}

что после позирования и дает п я знак равно exp - ( 1 + п я ) {\ Displaystyle Р_ {я} = \ ехр - (1 + р_ {я})} Q j знак равно exp - q j {\ displaystyle Q_ {j} = \ exp -q_ {j}}

Икс я j знак равно п я z я j Q j {\ displaystyle x_ {ij} = P_ {i} z_ {ij} Q_ {j}}, ∀, т. Е., я , j {\ displaystyle i, j} Икс знак равно п Z Q {\ Displaystyle X = PZQ}

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

п я знак равно z я . ( т + 1 ) ( j z я j Q j ( т ) ) - 1 {\ displaystyle P_ {i} = z_ {i}. ^ {(t + 1)} (\ sum _ {j} z_ {ij} Q_ {j} ^ {(t)}) ^ {- 1}}, ∀ и, ∀. я {\ displaystyle i} Q j ( т + 1 ) знак равно z . j ( я z я j п я ( т + 1 ) ) - 1 {\ Displaystyle Q_ {j} ^ {(t + 1)} = z _ {. j} (\ sum _ {i} z_ {ij} P_ {i} ^ {(t + 1)}) ^ {- 1} } j {\ displaystyle j}

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

Некоторые свойства (см. De Mesnard (1994)):

Недостаток информации: если не приносит информации, т. Е., ∀ то. Z {\ displaystyle Z} z я j знак равно z {\ displaystyle z_ {i} j = z} я , j {\ displaystyle i, j} Икс знак равно п Q {\ Displaystyle X = PQ}

Идемпотентность: если имеет те же поля, что и. Икс знак равно K ( Z , Y ) знак равно Z {\ Displaystyle X = К (Z, Y) = Z} Y {\ displaystyle Y} Z {\ displaystyle Z}

Состав biproportions: ;. K ( K ( Z , Y 1 ) , Y 2 знак равно K ( Z , Y 2 ) {\ Displaystyle К (К (Z, Y_ {1}), Y_ {2} = K (Z, Y_ {2})} K ( . . . K ( Z , Y 1 ) , Y 2 ) . . . Z N ) знак равно K ( Z , Y N ) {\ Displaystyle К (... К (Z, Y_ {1}), Y_ {2})... Z_ {N}) = K (Z, Y_ {N})}

Нули: нулевое значение проецируется как ноль дюйма. Таким образом, блочно-диагональная матрица проецируется как блочно-диагональная матрица, а треугольная матрица проецируется как треугольная матрица. Z {\ displaystyle Z} Икс {\ displaystyle X}

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

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

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

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

Выберите начальные значения и установите м ^ я j ( 0 ) знак равно Икс я j {\ displaystyle {\ hat {m}} _ {ij} ^ {(0)}: = x_ {ij}} η 1 {\ displaystyle \ eta \ geq 1}

м ^ я j ( 2 η - 1 ) знак равно м ^ я j ( 2 η - 2 ) ты я k знак равно 1 J м ^ я k ( 2 η - 2 ) {\ 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)}}}}
м ^ я j ( 2 η ) знак равно м ^ я j ( 2 η - 1 ) v j k знак равно 1 я м ^ k j ( 2 η - 1 ) . {\ 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)}}}.}.}

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

Заметки:

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

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

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

а ^ я ( η ) знак равно ты я j   Икс я j б ^ j ( η - 1 ) , {\ displaystyle {\ hat {a}} _ {i} ^ {(\ eta)} = {\ frac {u_ {i}} {\ sum _ {j} \ x_ {ij} {\ hat {b}} _ {j} ^ {(\ eta -1)}}},}
б ^ j ( η ) знак равно v j я   Икс я j а ^ я ( η ) {\ displaystyle {\ hat {b}} _ {j} ^ {(\ eta)} = {\ frac {v_ {j}} {\ sum _ {i} \ x_ {ij} {\ hat {a}} _ {я} ^ {(\ eta)}}}}

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

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

Заметки:

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

Обсуждение

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

м я j ( η ) м час k ( η ) м я k ( η ) м час j ( η ) знак равно Икс я j Икс час k Икс я k Икс час j     η 0  а также  я час , j k {\ 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}

поскольку м я j ( η ) знак равно а я ( η ) б j ( η ) Икс я j . {\ displaystyle m_ {ij} ^ {(\ eta)} = a_ {i} ^ {(\ eta)} b_ {j} ^ {(\ eta)} x_ {ij}.}

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

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

я J ( 2 + J ) + я J ( 2 + я ) знак равно я 2 J + я J 2 + 4 я J {\ Displaystyle IJ (2 + J) + IJ (2 + I) = I ^ {2} J + IJ ^ {2} + 4IJ \,}

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

я ( 1 + J ) + J ( 1 + я ) знак равно 2 я J + я + J {\ Displaystyle I (1 + J) + J (1 + I) = 2IJ + I + J \,}

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

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

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

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

  • маргиналы наблюдаемой таблицы не исчезают (то есть) и Икс я + gt; 0 ,   Икс + j gt; 0 {\ Displaystyle х_ {я +}gt; 0, \ х _ {+ j}gt; 0}
  • наблюдаемая таблица неразделима (т. е. таблица не переставляется в блочно-диагональную форму).

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

Если все наблюдаемые значения строго положительны, гарантируется существование и уникальность 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) обеспечивает многомерную реализацию традиционной итерационной процедуры пропорциональной подгонки. Пакет позволяет обновлять N- мерный массив относительно заданных целевых маргинальных распределений (которые, в свою очередь, могут быть многомерными).

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

Смотрите также

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

Последняя правка сделана 2023-04-17 09:55:35
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте