Алгоритм Левенберга–Марквардта

Алгоритм, используемый для решения нелинейных задач наименьших квадратов

В математике и вычислениях алгоритм Левенберга-Марквардта ( LMA или просто LM ), также известный как метод затухающих наименьших квадратов ( DLS ), используется для решения нелинейных задач наименьших квадратов. Эти задачи минимизации возникают особенно при подгонке кривой наименьших квадратов . LMA интерполирует между алгоритмом Гаусса-Ньютона (GNA) и методом градиентного спуска . LMA более надежен , чем GNA, что означает, что во многих случаях он находит решение, даже если оно начинается очень далеко от конечного минимума. Для хорошо себя ведущих функций и разумных начальных параметров LMA имеет тенденцию быть медленнее, чем GNA. LMA также можно рассматривать как Гаусса -Ньютона с использованием подхода доверительной области .

Алгоритм был впервые опубликован в 1944 году Кеннетом Левенбергом ^[1] , работавшим в Франкфордском армейском арсенале . Он был заново открыт в 1963 году Дональдом Марквардтом ^[2] , работавшим статистиком в DuPont , и независимо Жираром ^[3] , Уинном ^{[4] и Моррисоном [5]} .

LMA используется во многих программных приложениях для решения общих задач подгонки кривой. Используя алгоритм Гаусса–Ньютона, он часто сходится быстрее, чем методы первого порядка. ^[6] Однако, как и другие итерационные алгоритмы оптимизации, LMA находит только локальный минимум , который не обязательно является глобальным минимумом .

Проблема

Основное применение алгоритма Левенберга–Марквардта — задача подгонки кривой методом наименьших квадратов: для заданного набора эмпирических пар независимых и зависимых переменных найти параметры ⁠ ⁠ модельной кривой так, чтобы сумма квадратов отклонений была минимизирована: ${\displaystyle m}$ ${\displaystyle \left(x_{i},y_{i}\right)}$ ${\displaystyle {\boldsymbol {\beta }}}$ ${\displaystyle f\left(x,{\boldsymbol {\beta }}\right)}$ ${\displaystyle S\left({\boldsymbol {\beta }}\right)}$

${\displaystyle {\hat {\boldsymbol {\beta }}}\in \operatorname {argmin} \limits _{\boldsymbol {\beta }}S\left({\boldsymbol {\beta }}\right)\equiv \operatorname {argmin} \limits _{\boldsymbol {\beta }}\sum _{i=1}^{m}\left[y_{i}-f\left(x_{i},{\boldsymbol {\beta }}\right)\right]^{2},}$который предполагается непустым.

Решение

Как и другие числовые алгоритмы минимизации, алгоритм Левенберга–Марквардта является итеративной процедурой. Чтобы начать минимизацию, пользователь должен предоставить начальное предположение для вектора параметров ⁠ ⁠ ${\displaystyle {\boldsymbol {\beta }}}$ . В случаях только с одним минимумом неинформированное стандартное предположение вроде будет работать нормально; в случаях с несколькими минимумами алгоритм сходится к глобальному минимуму только в том случае, если начальное предположение уже несколько близко к окончательному решению. ${\displaystyle {\boldsymbol {\beta }}^{\text{T}}={\begin{pmatrix}1,\ 1,\ \dots ,\ 1\end{pmatrix}}}$

На каждом шаге итерации вектор параметров ⁠ ⁠ ${\displaystyle {\boldsymbol {\beta }}}$ заменяется новой оценкой ⁠ ⁠ ${\displaystyle {\boldsymbol {\beta }}+{\boldsymbol {\delta }}}$ . Для определения ⁠ ⁠ ${\displaystyle {\boldsymbol {\delta }}}$ функция аппроксимируется ее линеаризацией : ${\displaystyle f\left(x_{i},{\boldsymbol {\beta }}+{\boldsymbol {\delta }}\right)}$

${\displaystyle f\left(x_{i},{\boldsymbol {\beta }}+{\boldsymbol {\delta }}\right)\approx f\left(x_{i},{\boldsymbol {\beta }}\right)+\mathbf {J} _{i}{\boldsymbol {\delta }},}$

где

${\displaystyle \mathbf {J} _{i}={\frac {\partial f\left(x_{i},{\boldsymbol {\beta }}\right)}{\partial {\boldsymbol {\beta }}}}}$

— градиент (в данном случае вектор-строка) ⁠ ⁠ ${\displaystyle f}$ относительно ⁠ ⁠ ${\displaystyle {\boldsymbol {\beta }}}$ .

Сумма квадратичных отклонений имеет минимум при нулевом градиенте относительно ⁠ ⁠ . Вышеприведенное приближение первого порядка дает ${\displaystyle S\left({\boldsymbol {\beta }}\right)}$ ${\displaystyle {\boldsymbol {\beta }}}$ ${\displaystyle f\left(x_{i},{\boldsymbol {\beta }}+{\boldsymbol {\delta }}\right)}$

${\displaystyle S\left({\boldsymbol {\beta }}+{\boldsymbol {\delta }}\right)\approx \sum _{i=1}^{m}\left[y_{i}-f\left(x_{i},{\boldsymbol {\beta }}\right)-\mathbf {J} _{i}{\boldsymbol {\delta }}\right]^{2},}$

или в векторной записи,

${\displaystyle {\begin{aligned}S\left({\boldsymbol {\beta }}+{\boldsymbol {\delta }}\right)&\approx \left\|\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)-\mathbf {J} {\boldsymbol {\delta }}\right\|^{2}\\&=\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)-\mathbf {J} {\boldsymbol {\delta }}\right]^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)-\mathbf {J} {\boldsymbol {\delta }}\right]\\&=\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)\right]^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)\right]-\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)\right]^{\mathrm {T} }\mathbf {J} {\boldsymbol {\delta }}-\left(\mathbf {J} {\boldsymbol {\delta }}\right)^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)\right]+{\boldsymbol {\delta }}^{\mathrm {T} }\mathbf {J} ^{\mathrm {T} }\mathbf {J} {\boldsymbol {\delta }}\\&=\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)\right]^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)\right]-2\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)\right]^{\mathrm {T} }\mathbf {J} {\boldsymbol {\delta }}+{\boldsymbol {\delta }}^{\mathrm {T} }\mathbf {J} ^{\mathrm {T} }\mathbf {J} {\boldsymbol {\delta }}.\end{aligned}}}$

Взяв производную этого приближения по ⁠ ⁠ и приравняв результат к нулю, получаем ${\displaystyle S\left({\boldsymbol {\beta }}+{\boldsymbol {\delta }}\right)}$ ${\displaystyle {\boldsymbol {\delta }}}$

${\displaystyle \left(\mathbf {J} ^{\mathrm {T} }\mathbf {J} \right){\boldsymbol {\delta }}=\mathbf {J} ^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)\right],}$

где — матрица Якоби , чья ⁠ ⁠ -я строка равна , и где и — векторы с ⁠ ⁠ -й компонентой и соответственно. Полученное выше выражение для ⁠ ⁠ подпадает под метод Гаусса–Ньютона. Матрица Якоби, как определено выше, не является (в общем случае) квадратной матрицей, а является прямоугольной матрицей размера , где — число параметров (размер вектора ). Умножение матриц дает требуемую квадратную матрицу, а произведение матрицы на вектор в правой части дает вектор размера . Результатом является набор линейных уравнений, которые можно решить относительно ⁠ ⁠ . ${\displaystyle \mathbf {J} }$ ${\displaystyle i}$ ${\displaystyle \mathbf {J} _{i}}$ ${\displaystyle \mathbf {f} \left({\boldsymbol {\beta }}\right)}$ ${\displaystyle \mathbf {y} }$ ${\displaystyle i}$ ${\displaystyle f\left(x_{i},{\boldsymbol {\beta }}\right)}$ ${\displaystyle y_{i}}$ ${\displaystyle {\boldsymbol {\beta }}}$ ${\displaystyle m\times n}$ ${\displaystyle n}$ ${\displaystyle {\boldsymbol {\beta }}}$ ${\displaystyle \left(\mathbf {J} ^{\mathrm {T} }\mathbf {J} \right)}$ ${\displaystyle n\times n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\boldsymbol {\delta }}}$

Вклад Левенберга заключается в замене этого уравнения «затухающей версией»:

${\displaystyle \left(\mathbf {J} ^{\mathrm {T} }\mathbf {J} +\lambda \mathbf {I} \right){\boldsymbol {\delta }}=\mathbf {J} ^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)\right],}$

где ⁠ ⁠ ${\displaystyle \mathbf {I} }$ — единичная матрица, дающая приращение ⁠ ⁠ ${\displaystyle {\boldsymbol {\delta }}}$ к оцениваемому вектору параметров ⁠ ⁠ ${\displaystyle {\boldsymbol {\beta }}}$ .

(Неотрицательный) коэффициент затухания ⁠ ⁠ ${\displaystyle \lambda }$ корректируется на каждой итерации. Если уменьшение ⁠ ⁠ ${\displaystyle S}$ происходит быстро, можно использовать меньшее значение, приближая алгоритм к алгоритму Гаусса–Ньютона , тогда как если итерация дает недостаточное уменьшение остатка, ⁠ ⁠ ${\displaystyle \lambda }$ можно увеличить, приблизив шаг к направлению градиентного спуска. Обратите внимание, что градиент ⁠ ⁠ ${\displaystyle S}$ относительно ⁠ ⁠ равен ${\displaystyle {\boldsymbol {\beta }}}$ . Поэтому для больших значений ⁠ ⁠ шаг будет сделан примерно в направлении, противоположном градиенту. Если либо длина вычисленного шага ⁠ ⁠, либо уменьшение суммы квадратов из последнего вектора параметров ⁠ ⁠ падают ниже предопределенных пределов , итерация останавливается, и последний вектор параметров ⁠ ⁠ считается решением. ${\displaystyle -2\left(\mathbf {J} ^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)\right]\right)^{\mathrm {T} }}$ ${\displaystyle \lambda }$ ${\displaystyle {\boldsymbol {\delta }}}$ ${\displaystyle {\boldsymbol {\beta }}+{\boldsymbol {\delta }}}$ ${\displaystyle {\boldsymbol {\beta }}}$

Когда коэффициент затухания ⁠ ⁠ ${\displaystyle \lambda }$ велик относительно , ​​инвертирование не требуется, поскольку обновление хорошо аппроксимируется малым шагом градиента . ${\displaystyle \|\mathbf {J} ^{\mathrm {T} }\mathbf {J} \|}$ ${\displaystyle \mathbf {J} ^{\mathrm {T} }\mathbf {J} +\lambda \mathbf {I} }$ ${\displaystyle \lambda ^{-1}\mathbf {J} ^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)\right]}$

Чтобы сделать масштаб решения инвариантным, алгоритм Марквардта решил модифицированную задачу с каждым компонентом градиента, масштабированным в соответствии с кривизной. Это обеспечивает большее движение вдоль направлений, где градиент меньше, что позволяет избежать медленной сходимости в направлении малого градиента. Флетчер в своей статье 1971 года Модифицированная подпрограмма Марквардта для нелинейных наименьших квадратов упростила форму, заменив единичную матрицу ⁠ ⁠ ${\displaystyle \mathbf {I} }$ на диагональную матрицу, состоящую из диагональных элементов ⁠ ⁠ ${\displaystyle \mathbf {J} ^{\text{T}}\mathbf {J} }$ :

${\displaystyle \left[\mathbf {J} ^{\mathrm {T} }\mathbf {J} +\lambda \operatorname {diag} \left(\mathbf {J} ^{\mathrm {T} }\mathbf {J} \right)\right]{\boldsymbol {\delta }}=\mathbf {J} ^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\right)\right].}$

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

Выбор параметра демпфирования

Были выдвинуты различные более или менее эвристические аргументы в пользу наилучшего выбора параметра затухания ⁠ ⁠ ${\displaystyle \lambda }$ . Существуют теоретические аргументы, показывающие, почему некоторые из этих выборов гарантируют локальную сходимость алгоритма; однако эти выборы могут привести к тому, что глобальная сходимость алгоритма пострадает от нежелательных свойств наискорейшего спуска , в частности, очень медленной сходимости вблизи оптимума.

Абсолютные значения любого выбора зависят от того, насколько хорошо масштабирована исходная задача. Марквардт рекомендовал начинать со значения ⁠ ⁠ ${\displaystyle \lambda _{0}}$ и фактора ⁠ ⁠ ${\displaystyle \nu >1}$ . Сначала задайте и вычислите остаточную сумму квадратов после одного шага от начальной точки с коэффициентом затухания , а затем с ⁠ ⁠ . Если оба они хуже исходной точки, то затухание увеличивается путем последовательного умножения на ⁠ ⁠ , пока не будет найдена лучшая точка с новым коэффициентом затухания ⁠ ⁠ для некоторого ⁠ ⁠ . ${\displaystyle \lambda =\lambda _{0}}$ ${\displaystyle S\left({\boldsymbol {\beta }}\right)}$ ${\displaystyle \lambda =\lambda _{0}}$ ${\displaystyle \lambda _{0}/\nu }$ ${\displaystyle \nu }$ ${\displaystyle \lambda _{0}\nu ^{k}}$ ${\displaystyle k}$

Если использование коэффициента затухания ⁠ ⁠ ${\displaystyle \lambda /\nu }$ приводит к уменьшению квадрата невязки, то это принимается за новое значение ⁠ ⁠ ${\displaystyle \lambda }$ (а новое оптимальное положение принимается за полученное с этим коэффициентом затухания), и процесс продолжается; если использование ⁠ ⁠ ${\displaystyle \lambda /\nu }$ привело к худшему остатку, но использование ⁠ ⁠ ${\displaystyle \lambda }$ привело к лучшему остатку, то ⁠ ⁠ ${\displaystyle \lambda }$ остается неизменным, а новый оптимум принимается за значение, полученное с ⁠ ⁠ ${\displaystyle \lambda }$ в качестве коэффициента затухания.

Эффективная стратегия управления параметром затухания, называемая отложенным удовлетворением , состоит в увеличении параметра на небольшую величину для каждого шага подъема и уменьшении на большую величину для каждого шага спуска. Идея этой стратегии заключается в том, чтобы избежать слишком быстрого движения вниз в начале оптимизации, тем самым ограничивая шаги, доступные в будущих итерациях, и, следовательно, замедляя сходимость. ^[7] Увеличение в 2 раза и уменьшение в 3 раза, как было показано, эффективны в большинстве случаев, в то время как для больших задач более экстремальные значения могут работать лучше, с увеличением в 1,5 раза и уменьшением в 5 раз. ^[8]

Геодезическое ускорение

При интерпретации шага Левенберга–Марквардта как скорости вдоль геодезической траектории в пространстве параметров можно улучшить метод, добавив член второго порядка, который учитывает ускорение вдоль геодезической ${\displaystyle {\boldsymbol {v}}_{k}}$ ${\displaystyle {\boldsymbol {a}}_{k}}$

${\displaystyle {\boldsymbol {v}}_{k}+{\frac {1}{2}}{\boldsymbol {a}}_{k}}$

где решение ${\displaystyle {\boldsymbol {a}}_{k}}$

${\displaystyle {\boldsymbol {J}}_{k}{\boldsymbol {a}}_{k}=-f_{vv}.}$

Поскольку этот геодезический член ускорения зависит только от производной по направлению скорости , он не требует вычисления полной матрицы производной второго порядка, требуя лишь небольших накладных расходов с точки зрения стоимости вычислений. ^[9] Поскольку производная второго порядка может быть довольно сложным выражением, может быть удобно заменить ее приближением конечной разности ${\displaystyle f_{vv}=\sum _{\mu \nu }v_{\mu }v_{\nu }\partial _{\mu }\partial _{\nu }f({\boldsymbol {x}})}$ ${\displaystyle {\boldsymbol {v}}}$

${\displaystyle {\begin{aligned}f_{vv}^{i}&\approx {\frac {f_{i}({\boldsymbol {x}}+h{\boldsymbol {\delta }})-2f_{i}({\boldsymbol {x}})+f_{i}({\boldsymbol {x}}-h{\boldsymbol {\delta }})}{h^{2}}}\\&={\frac {2}{h}}\left({\frac {f_{i}({\boldsymbol {x}}+h{\boldsymbol {\delta }})-f_{i}({\boldsymbol {x}})}{h}}-{\boldsymbol {J}}_{i}{\boldsymbol {\delta }}\right)\end{aligned}}}$

где и уже вычислены алгоритмом, поэтому требуется только одна дополнительная оценка функции для вычисления . Выбор шага конечной разности может повлиять на устойчивость алгоритма, и значение около 0,1 обычно является разумным в целом. ^[8] ${\displaystyle f({\boldsymbol {x}})}$ ${\displaystyle {\boldsymbol {J}}}$ ${\displaystyle f({\boldsymbol {x}}+h{\boldsymbol {\delta }})}$ ${\displaystyle h}$

Поскольку ускорение может быть направлено в противоположном направлении относительно скорости, чтобы предотвратить остановку метода в случае, если демпфирование слишком мало, добавляется дополнительный критерий ускорения для принятия шага, требующий, чтобы

${\displaystyle {\frac {2\left\|{\boldsymbol {a}}_{k}\right\|}{\left\|{\boldsymbol {v}}_{k}\right\|}}\leq \alpha }$

где обычно фиксируется на значении меньше 1, с меньшими значениями для более сложных задач. ^[8] ${\displaystyle \alpha }$

Добавление члена геодезического ускорения может позволить значительно увеличить скорость сходимости, и это особенно полезно, когда алгоритм движется через узкие каньоны в ландшафте целевой функции, где допустимые шаги меньше, а более высокая точность из-за члена второго порядка дает значительные улучшения. ^[8]

Пример

Плохо подходит

Лучше подходит

Лучший вариант

В этом примере мы пытаемся подогнать функцию, используя алгоритм Левенберга–Марквардта, реализованный в GNU Octave как функция leasqr . Графики показывают постепенное улучшение подгонки для параметров , используемых в начальной кривой. Только когда параметры в последнем графике выбраны наиболее близкими к оригиналу, кривые подгоняются точно. Это уравнение является примером очень чувствительных начальных условий для алгоритма Левенберга–Марквардта. Одной из причин этой чувствительности является существование множественных минимумов — функция имеет минимумы при значении параметра и . ${\displaystyle y=a\cos \left(bX\right)+b\sin \left(aX\right)}$ ${\displaystyle a=100}$ ${\displaystyle b=102}$ ${\displaystyle \cos \left(\beta x\right)}$ ${\displaystyle {\hat {\beta }}}$ ${\displaystyle {\hat {\beta }}+2n\pi }$

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

• Доверительный регион
• Метод Нелдера–Мида
• Варианты алгоритма Левенберга–Марквардта также использовались для решения нелинейных систем уравнений. ^[10]

Ссылки

1. Левенберг, Кеннет (1944). «Метод решения некоторых нелинейных задач методом наименьших квадратов». Quarterly of Applied Mathematics . 2 (2): 164–168. doi : 10.1090/qam/10666 .
2. Марквардт, Дональд (1963). «Алгоритм оценки нелинейных параметров методом наименьших квадратов». Журнал SIAM по прикладной математике . 11 (2): 431–441. doi :10.1137/0111030. hdl : 10338.dmlcz/104299 .
3. Жирар, Андре (1958). «Отрывок из Revue d'optique théorique et Instrumentale ». Рев. Опц . 37 : 225–241, 397–424.
4. Уинн, К. Г. (1959). «Проектирование линз с помощью электронного цифрового компьютера: I». Proc. Phys. Soc. Lond . 73 (5): 777–787. Bibcode : 1959PPS....73..777W. doi : 10.1088/0370-1328/73/5/310.
5. Моррисон, Дэвид Д. (1960). «Методы решения нелинейных задач наименьших квадратов и доказательства сходимости». Труды семинара Лаборатории реактивного движения по программам слежения и определению орбиты : 1–9.
6. Вильямовски, Богдан; Ю, Хао (июнь 2010 г.). «Улучшенные вычисления для обучения Левенберга–Марквардта» (PDF) . Труды IEEE по нейронным сетям и системам обучения . 21 (6).
7. Transtrum, Mark K; Machta, Benjamin B; Sethna, James P (2011). «Геометрия нелинейных наименьших квадратов с приложениями к неровным моделям и оптимизации». Physical Review E. 83 ( 3). APS: 036701. arXiv : 1010.1449 . Bibcode : 2011PhRvE..83c6701T. doi : 10.1103/PhysRevE.83.036701. PMID  21517619. S2CID  15361707.
8. Transtrum, Mark K; Sethna, James P (2012). «Улучшения алгоритма Левенберга-Марквардта для минимизации нелинейного метода наименьших квадратов». arXiv : 1201.5885 [physics.data-an].
9. "Нелинейная подгонка по методу наименьших квадратов". GNU Scientific Library. Архивировано из оригинала 2020-04-14.
10. Канзов, Кристиан; Ямашита, Нобуо; Фукусима, Масао (2004). «Методы Левенберга–Марквардта со свойствами сильной локальной сходимости для решения нелинейных уравнений с выпуклыми ограничениями». Журнал вычислительной и прикладной математики . 172 (2): 375–397. Bibcode :2004JCoAM.172..375K. doi : 10.1016/j.cam.2004.02.013 .

Дальнейшее чтение

• Море, Хорхе Дж.; Соренсен, Дэниел К. (1983). «Вычисление шага доверительной области» (PDF) . SIAM J. Sci. Stat. Comput . 4 (3): 553–572. doi :10.1137/0904038.
• Гилл, Филип Э.; Мюррей, Уолтер (1978). «Алгоритмы решения нелинейной задачи наименьших квадратов». Журнал SIAM по численному анализу . 15 (5): 977–992. Bibcode : 1978SJNA...15..977G. doi : 10.1137/0715063.
• Pujol, Jose (2007). «Решение нелинейных обратных задач и метод Левенберга-Марквардта». Геофизика . 72 (4). SEG: W1–W16. Bibcode : 2007Geop...72W...1P. doi : 10.1190/1.2732552.
• Нокедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация (2-е изд.). Springer. ISBN 978-0-387-30303-1.

Внешние ссылки

• Подробное описание алгоритма можно найти в книге «Численные рецепты на языке C», глава 15.5: Нелинейные модели.
• CT Kelley, Итеративные методы оптимизации , SIAM Frontiers in Applied Mathematics, № 18, 1999, ISBN 0-89871-433-8 . Электронная копия 
• История алгоритма в новостях SIAM
• Учебное пособие от Ананта Ранганатана
• К. Мэдсен, Х. Б. Нильсен, О. Тинглефф, Методы решения нелинейных задач наименьших квадратов (учебник по нелинейному методу наименьших квадратов; код LM: аналитический секанс Якобиана)
• T. Strutz: Подгонка данных и неопределенность (Практическое введение в метод взвешенных наименьших квадратов и далее). 2-е издание, Springer Vieweg, 2016, ISBN 978-3-658-11455-8 . 
• HP Gavin, Метод Левенберга-Марквардта для нелинейных задач наименьших квадратов аппроксимации кривых ( включая реализацию MATLAB )