Алгоритм наименьших средних квадратов (LMS) и адаптивные фильтры.
Least mean squares filter
Алгоритм LMS: адаптивный фильтр для минимизации ошибок сигнала. Основан на методе стохастического градиентного спуска, разработан профессором Видроу в 1960 году.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Статистический алгоритм
Statistical algorithm
Алгоритмы наименьших среднеквадратов (LMS) — это класс адаптивных фильтров, используемых для имитации желаемого фильтра путем определения коэффициентов фильтра, минимизирующих среднеквадратичную ошибку (разницу между желаемым и фактическим сигналом). Это метод стохастического градиентного спуска, в котором фильтр адаптируется только на основе ошибки в текущий момент времени. Алгоритм был изобретен в 1960 году профессором Стэнфордского университета Бернардом Видроу и его первым аспирантом, Тедом Хоффом, в ходе их исследований однослойных нейронных сетей (ADALINE). В частности, они использовали градиентный спуск для обучения ADALINE распознаванию образов и назвали этот метод "правилом дельты". Затем они применили это правило к фильтрам, что привело к созданию алгоритма LMS.
Least mean squares (LMS) algorithms are a class of adaptive filter used to mimic a desired filter by finding the filter coefficients that relate to producing the least mean square of the error signal (difference between the desired and the actual signal). It is a stochastic gradient descent method in that the filter is only adapted based on the error at the current time. It was invented in 1960 by Stanford University professor Bernard Widrow and his first Ph. D. student, Ted Hoff, based on their research in single layer neural networks (ADALINE). Specifically, they used gradient descent to train ADALINE to recognize patterns, and called the algorithm "delta rule". They then applied the rule to filters, resulting in the LMS algorithm.
Формулирование задачи
На рисунке показаны различные части фильтра. Это входной сигнал, который затем преобразуется неизвестным фильтром, который мы хотим идентифицировать с помощью . Выход неизвестного фильтра – , который затем подвергается воздействию шумового сигнала , в результате чего получается . Затем вычисляется сигнал ошибки , который подается обратно в адаптивный фильтр для корректировки его параметров с целью минимизации среднеквадратичной ошибки сигнала .
The picture shows the various parts of the filter. is the input signal, which is then transformed by an unknown filter that we wish to match using The output from the unknown filter is , which is then interfered with a noise signal , producing Then the error signal is computed, and it is fed back to the adaptive filter, to adjust its parameters in order to minimize the mean square of the error signal .
Идея
Основная идея фильтра LMS заключается в приближении к оптимальным весам фильтра путем последовательного обновления весов таким образом, чтобы они сходились к оптимальным. Это основано на алгоритме градиентного спуска. Алгоритм начинается с предположения о малых весах (в большинстве случаев – нулевых) и на каждом шаге, вычисляя градиент среднеквадратичной ошибки, обновляет веса. То есть, если градиент среднеквадратичной ошибки положителен, это означает, что ошибка будет продолжать возрастать при использовании того же веса в дальнейших итерациях, следовательно, необходимо уменьшить веса. Аналогично, если градиент отрицателен, необходимо увеличить веса. Уравнение обновления веса имеет вид:
The basic idea behind LMS filter is to approach the optimum filter weights , by updating the filter weights in a manner to converge to the optimum filter weight. This is based on the gradient descent algorithm. The algorithm starts by assuming small weights (zero in most cases) and, at each step, by finding the gradient of the mean square error, the weights are updated. That is, if the MSE gradient is positive, it implies the error would keep increasing positively if the same weight is used for further iterations, which means we need to reduce the weights. In the same way, if the gradient is negative, we need to increase the weights. The weight update equation is
где – среднеквадратичная ошибка, а – коэффициент сходимости. Отрицательный знак указывает на движение вниз по склону ошибки, чтобы найти веса фильтра, , которые минимизируют ошибку. Среднеквадратичная ошибка как функция весов фильтра является квадратичной, что означает наличие единственного экстремума, минимизирующего среднеквадратичную ошибку – оптимального веса. Таким образом, LMS приближается к этому оптимальному весу, спускаясь или поднимаясь вдоль кривой зависимости среднеквадратичной ошибки от веса фильтра.
where represents the mean square error and is a convergence coefficient. The negative sign shows that we go down the slope of the error, to find the filter weights, , which minimize the error. The mean square error as a function of filter weights is a quadratic function which means it has only one extremum, that minimizes the mean square error, which is the optimal weight. The LMS thus, approaches towards this optimal weights by ascending/descending down the mean square error vs filter weight curve.