LMS算法被认为是机器学习中最基本最有用的算法。 在神经网络中，LMS的思想被用于参数的学习，在通信信号处理领域中LMS也像自适应滤波器一样非常常见。
本文主要对最小均值(LMS )算法进行了简要的梳理，包括内容。
)1)理论上介绍了一种基于LMS的梯度下降算法(包括BACH/STOCHASTIC )，并给出了matlab的实现
)2) DSP上的实现主要使用c语言
1. LMS算法理论问题引出
本人感兴趣的领域是机器学习，所以在这里先说明一下学习的过程。 某个地方的房价、住宅区的面积和卧室的数量之间有如下关系。
livingarea(feet2) # bedrooms price (1000 $ s ) ) ) ) ) )。
2104 3 400
1600 3 330
2400 3 369
1416 2 232
3000 4 540
由此，通过分析上面的数据，学习用于预测其他情况(例如面积2000，卧室数5 )的房价的模型。 这是一个学习问题，更简单地说，是一个概率回归问题。 在这里固定几个符号。 x表示输入[Living area，bedrooms]，y表示输出Price，h表示要学习的模型，m表示输入数据的各维[在此为2]，n表示输入数据的个数[在此为5]。
这个学习过程可以如下图所示进行记述。
同调
h一定与面积和卧室数量相关联。这里不考虑复杂的情况，假设模型是线性的(实际其它问题中很可能是其它关系模型，比如exp) )。
同调
如果. x1=1。 在此，考虑到上述房价问题，还是无视w0。
为了获得h(x )，现在的问题是什么呢？ 那就是如何得到h(x )的w1~w2的值。
讨论问题：
——上的数据表，知道线性模型(不知道参数) )。
求解——参数w1~w2
引入损失函数这个函数
这是用最小二乘法计算误差的函数，只是在前面追加了1/2，是什么意思呢？ 损失函数越小，表示模型与当前已知数据的拟合度越好，否则越差。 因此，求解w1￣w2的目标是使j(w )最小化，其用于LMS算法。
LMS算法
LMS算法是搜索算法，假设w从某个给定的初始值开始反复，直到j(w )达到一个值使j ) w )收敛为止，使j ) w )向最小的方向逐渐变化。 考虑坡度下降算法(gradient descent algorithm )，在给定的w值下迅速执行以下更新操作。
其中学习率(Learning rate )。
w要更新，必须先完成上述指南，求出指南的结果请参考以下算法流程。
对于单一训练实例j，
以上更新方法中，多个实例的更新规则如下
Repeat untilconvergence { (
for every j，exec
}
这种更新梯度下降方法被称为batchgradient descent。 另一种更新方法是采用随机示例数据实例，如下所示
Repeat untilconvergence { (
for every j，exec
}
此方法称为静态梯度设计(或增量梯度设计)。 两种方法的明显区别在于batch训练时间多于stochastic，但效果可能更好。 在实际问题中，stochastic更常用，因为它只需要找到接近使j(w )最小的值的值。
这么久了，LMS到底能用来做什么，其实上面很清楚。参数训练中的求极值
静态梯度设计在matlab中的实现如下：
函数[ test _ targets，a，updates]=LMS(train_patterns，train_targets，test_patterns， params ) % classifyusingtheleastmeanssquarealgorithm % inputs : % train _ patterns-train _ targets-traintargetts rgencecriterion )，convergence rate ] % outputs % test _ targets-predicted ta
rgets% a - Weights vector% updates - Updates throughout the learning iterations%% NOTE: Suitable for only two classes%[c, n] = size(train_patterns);[Max_iter, theta, eta]= process_params(params);y = [train_patterns ; ones(1,n)];train_zero = find(train_targets == 0);%Preprocessingprocessed_patterns = y;processed_patterns(:,train_zero) = -processed_patterns(:,train_zero);b = 2*train_targets - 1; %Initial weightsa = sum(processed_patterns')';iter = 1;k= 0;update = 1e3;updates = 1e3;while ((sum(abs(update)) > theta) & (iter < Max_iter)) iter = iter + 1; %k <- (k+1) mod n k = mod(k+1,n); if (k == 0), k = n; end % a <- a + eta*(b-a'*Yk)*Yk' update = eta*(b(k) - a'*y(:,k))*y(:,k); a = a + update; updates(iter) = sum(abs(update));endif (iter == Max_iter), disp(['Maximum iteration (' num2str(Max_iter) ') reached']);else disp(['Did ' num2str(iter) ' iterations'])end%Classify the test patternstest_targets = a'*[test_patterns; ones(1, size(test_patterns,2))];test_targets = test_targets > 0;2. 基于LMS的梯度下降算法在DSP上的实现
下面是我在DSP6713上使用软件仿真实现的LMS算法，
/* * zx_lms.h * * Created on: 2013-8-4 * Author: monkeyzx */#ifndef ZX_LMS_H_#define ZX_LMS_H_/* * methods for @lms_st.method */#define STOCHASTIC (0x01) /* 随机梯度下降 */#define BATCH (0x02) /* BATCH梯度下降 */struct lms_st {short method; /* 0/1 */double *x; /* features, x0,...,x[n-1] */int n; /* dimension of features */double *y; /* given output, y0,..,y[m-1] */int m; /* number of data set */double *weight; /* weighs that want to train by using LMS, w0,w1,..,w[n-1] */double lrate; /* learning rate */double threshhold; /* if error < threshold, stop iteration */int max_iter; /* if iter numbers > max_iter, stop iteration, if max_iter<0, then max_iter is unused */};extern void zx_lms(void);#endif /* ZX_LMS_H_ *//* * zx_lms.c * Least Mean Squares Algorithm * Created on: 2013-8-4 * Author: monkeyzx */#include "zx_lms.h"#include "config.h"#include <stdio.h>#include <stdlib.h>static double init_y[] = {4.00,3.30,3.69,2.32};static double init_x[] = {2.104,3,1.600,3,2.400,3,3.000,4};static double weight[2] = {0.1, 0.1};/* * Least Mean Square Algorithm * return value @error when stop iteration * use @lms_prob->method to choose a method. */double lms(struct lms_st *lms_prob){double err;double error;int i = 0;int j = 0;int iter = 0;static double *h = 0; /* 加static,防止栈溢出*/h = (double *)malloc(sizeof(double) * lms_prob->m);if (!h) {return -1;}do {error = 0;if (lms_prob->method != STOCHASTIC) {i = 0;} else {/* i=(i+1) mod m */i = i + 1;if (i >= lms_prob->m) {i = 0;}}for ( ; i<lms_prob->m; i++) {h[i] = 0;for (j=0; j<lms_prob->n; j++) {h[i] += lms_prob->weight[j] * lms_prob->x[i*lms_prob->n+j]; /* h(x) */}if (lms_prob->method == STOCHASTIC) break; /* handle STOCHASTIC */}for (j=0; j<lms_prob->n; j++) {if (lms_prob->method != STOCHASTIC) {i = 0;}for ( ; i<lms_prob->m; i++) {err = lms_prob->lrate* (lms_prob->y[i] - h[i]) * lms_prob->x[i*lms_prob->n+j];lms_prob->weight[j] += err; /* Update weights */error += ABS(err);if (lms_prob->method == STOCHASTIC) break; /* handle STOCHASTIC */}}iter = iter + 1;if ((lms_prob->max_iter > 0) && ((iter > lms_prob->max_iter))) {break;}} while (error >= lms_prob->threshhold);free(h);return error;}#define DEBUGvoid zx_lms(void){int i = 0;double error = 0;struct lms_st lms_prob;lms_prob.lrate = 0.01;lms_prob.m = 4;lms_prob.n = 2;lms_prob.weight = weight;lms_prob.threshhold = 0.2;lms_prob.max_iter = 1000;lms_prob.x = init_x;lms_prob.y = init_y;//lms_prob.method = STOCHASTIC;lms_prob.method = BATCH;//error = lms(init_x, 2, init_y, 4, weight, 0.01, 0.1, 1000);error = lms(&lms_prob);#ifdef DEBUGfor (i=0; i<sizeof(weight)/sizeof(weight[0]); i++) {printf("%fn", weight[i]);}printf("error:%fn", error);#endif}
输入、输出、初始权值为
static double init_y[] = {4.00,3.30,3.69,2.32};
static double init_x[] = { /* 用一维数组保存 */
2.104, 3,
1.600, 3,
2.400, 3,
3.000, 4
};
static double weight[2] = {0.1, 0.1};
main函数中只需要调用zx_lms()就可以运行了，本文对两种梯度下降方法做了个简单对比，
max_iter=1000w1w2errorCPU Cyclesbatch-0.62073691.4197370.209472181500stochastic
0.1454400.1852200.130640995
需要说明的是：batch算法是达到最大迭代次数1000退出的，而stochastic是收敛退出的，因此这里batch算法应该没有对数据做到较好的拟合。stochastic算法则在时钟周期上只有995，远比batch更有时间上的优势。
注：这里的error没有太大的可比性，因为batch的error针对的整体数据集的error，而stochastic 的error是针对一个随机的数据实例。
LMS有个很重要的问题：收敛。开始时可以根据给定数据集设置w值，使h(x)尽可能与接近y，如果不确定可以将w设置直率的秋天点。
这里顺便记录下在调试过程中遇到的一个问题：在程序运行时发现有变量的值为1.#QNAN。
解决：QNAN是Quiet Not a Number简写，是常见的浮点溢出错误，在网上找到了解释
AQNaNis a NaN with the most significant fraction bit set. QNaN’s propagate freely through most arithmetic operations. These values pop out of an operation when the result is not mathematically defined.
在开始调试过程中因为迭代没有收敛，发散使得w和error等值逐渐累积，超过了浮点数的范围，从而出现上面的错误，通过修改使程序收敛后上面的问题自然而然解决了。
参考：
[1]Andrew Ng的机器学习课程
[2] Richard O.Duda 等，《模式分类》