Write a program that performs the least mean squares optimization.
Given a large collection of data of the form (x0 x1 x2 x3 d), your task is to determine w0
w1 w2 w3. The LMS technique finds these weights by starting with some assumed
weights, such asw0=w1=w2=w3=0, and finding the result of the function using the first
grouping of data. For each weight wi, set wi=wi+ nxi(d−y). Assume n=0.05

I understood I was to have an update function which returns void and is pass by reference. Also another function to calculate y.
this is my code:

1  #include <iostream>
   2  #include <fstream>
   3  #include <cstdlib>
   4  using namespace std;
   5   double eval(double x0,double x1, double x2,double x3, double w0,
   6  double w1, double w2,double w3)
   7  {
   8      w0=w1=w2=w3=0.0;  //initializing weights
   9      double y;
  10      y=(w0*x0)+(w1*x1)+(w2*x2)+(w3*x3);//calculating y
  11     return y;
  12  }
  13  void update(double &w0, double &w1, double &w2, double &w3,
  14              double x0, double x1, double x2, double x3, double d)
  15  //updating weights
  16  {
  17      double n=0.05;
  18      double y;
  19      w0=w0+(n*x0)*(d-y);
  20      w1=w1+(n*x1)*(d-y);
  21      w2=w2+(n*x2)*(d-y);
  22      w3=w3+(n*x3)*(d-y);
  23  }
  24  int main()
  25  {
  26      double y=0.0, w0=0.0, w1=0.0, w2=0.0,w3=0.0;
  27  ifstream fin;
  28  string file_name;
  29  cout<<"Enter input file name: "<<endl; //asking user for file name
 30  cin>>file_name;
 31  fin.open(file_name.c_str(),ios::in); //converting to c-string
  32  if(!fin.is_open()) //condition on not being able to open file
  33  {
  34      cerr<<"Error opening file"<<endl;
  35      exit(2);
  36  }
  37  double x0,x1,x2,x3,d; //declaring x0,x1,x2,x3,d
  38      fin>>x0>>x1>>x2>>x3>>d;
  39      for(int i=0; i<100; i++) //running loop 100times
  40  {
  41  //resetting file
  42  fin.clear();
  43  fin.seekg(0);
  44  while(fin>>x0>>x1>>x2>>x3>>d)
  45  {
  46      update(w0,w1,w2,w3,x0,x1,x2,x3,d); //updating weights
  47
  48  }
  49  }
  50  y=eval(x0,x1,x2,x3,w0,w1,w2,w3); //calculating y
  51  cout<<y<<endl;                 //printing y
  52  fin.close();                  //closing file
  53  return 0;                    //exit
  54  }

We were given a bunch of test inputs and their sample outputs, for example
=== Test 2
--- Input
pa-4-input-2.txt
--- Output
Enter input file name:
Function: y = 15*x0 + -4.28*x1 + 2.25*x2 + -10*x3

but my output is always zero can someone help please!

lines 19-22. The variable y is used before it is assigned a value. Consequently it just contains some random value.

lines 39-48: Why are you reading that file 100 times? Do you really expect the data inside the file will change on you? I understand why you might do that if you are trying to profile your program, but I don't see that happening either.

Well its mainly because we were to do this:
1. Seek to the top of the file. (Use: f.clear(); then f.seekg(0);, where f is the name of
your ifstream variable.)
2. Get every line of input (containing those five doubles). For each line of input, call
a function to update the weights (the data and weights are passed to the function).
Print the function that was found by this LMS technique (see the test cases).

There are apparently several lines (number unknown) in the file with 5 doubles in each line. The first 4 are x0-x1 while the 5th one is d (from w0x0+w1x1+w2x2+w3x3).

The LMS technique finds these weights by starting with some assumed
weights, such asw0=w1=w2=w3=0, and finding the result of the function using the first
grouping of data. For example, if the first grouping is (1 2 5 3 4) (i.e. x0=1 x1=2 x2=5 x3=3, and d=4), then the result of the function is 0(1)+0(2)+0(5)+0(3), which equals 0.
This output, called y, is clearly not the same as d (which was 4 in this first group). So we
need to change our weights to closer match the true function (the true function has
output d=4 with the same inputs). For each weight wi, setwi=wi+ xi(d−y). Assume =0
05 (this is the "update rate").

This is one of the files:

1.980955218 1.326279813 1.468332886 1.652523895 15.64860908
1.40138091 0.463348524 1.272578224 1.14094675 10.70959963
0.653932738 0.082169996 0.87534298 1.433041554 9.176467886
1.475811483 0.086618954 1.006660419 0.347862351 6.06048005
0.580291302 1.276568022 1.150790302 1.59729687 12.97498573
1.613175156 1.794099541 1.778114146 1.264357902 15.59314828
0.014130925 0.999273599 0.774983785 1.637557707 10.88786031
0.943589595 0.112465568 0.862761984 1.763501239 10.81081164
0.151747744 1.223161746 0.639217737 1.141623548 9.082218638
0.671624532 1.194520982 0.283798297 1.675815431 10.61532311
0.133390106 1.475703498 1.067261216 0.273056182 7.378805478
1.758499636 0.127085102 1.365271201 1.029271043 10.22556761
1.041069948 1.192406478 0.018687352 0.270822665 4.56523562
0.600397035 0.621043052 0.945757957 0.86553466 8.141895649
0.006639445 1.398809493 1.006001976 1.730769716 12.74534322
1.933515685 1.616607394 0.986497213 1.369681558 13.60494835
0.415581428 1.007890939 1.700592947 1.159591592 12.17150851
0.435676194 1.392184302 1.535143111 0.467666273 9.696139224
0.26032113 1.683630312 0.572762977 1.260438618 10.38762515
1.495531764 0.885135031 0.829025127 1.640757276 12.31590631
0.549981867 0.36581962 0.729172518 0.562733118 5.720071136
0.728051699 0.802400871 1.621374886 0.010247624 7.237968596
1.018963939 0.968495117 1.738742268 0.438962101 9.928029381
1.444740835 0.159197997 1.372988953 0.744280635 8.859226226
0.529201452 0.616189325 0.002015088 0.746285449 4.752767162
0.328591581 0.169988057 1.436836889 1.878282162 12.49220701
0.898641239 0.276781309 1.164301726 1.915784432 12.60824676
1.707724119 1.020710907 0.707665494 1.422654521 11.5627605
0.286441108 0.150021547 1.601408516 0.661246278 8.03569486
0.117537546 0.275428495 1.39107253 0.33548441 6.183549768
0.230560891 0.311360918 1.88902736 1.712646397 13.37095039
1.682525844 1.853326498 0.217651951 1.429833845 11.76147007
0.959566381 0.594864793 1.26086567 0.924390252 9.629453985
1.702223178 1.562735331 1.968508798 1.121140695 15.21778301
0.47326734 1.238132076 1.662982161 1.701947076 14.74626628

The output for it should be:

=== Test 1
--- Input
pa-4-input-1.txt
--- Output
Enter input file name:
Function: y = 1*x0 + 2*x1 + 3*x2 + 4*x3

I now understand what you're saying about the y variable. My first function calculates y, am I to do the same for line 18 as in line 10?
Sorry if my questions are stupid. I don't think I am a c++ person

The reason you only get outpout of 0 is because of function eval(). Look at line 8 -- it sets all the weights to 0, destroying all the calculations done in main(). Comment, or delete, that line.

Oh I see. I think this is what I'm supposed to do:

5  double eval(double x0,double x1, double x2,double x3, double w0,
   6               double w1, double w2,double w3)
   7       {
   8           w0=w1=w2=w3=0.0;  //initializing weights
   9           double y;
  10           y=(w0*x0)+(w1*x1)+(w2*x2)+(w3*x3);//calculating y
  11           return y;
  12       }
  13  void update(double &w0, double &w1, double &w2, double &w3,
  14              double x0, double x1, double x2, double x3, double d)
  15  //updating weights
  16  {
  17      double y;
  18      y=eval(x0,x1,x2,x3,w0,w1,w2,w3);
  19      double n=0.05;
  20      w0=w0+(n*x0)*(d-y);
  21      w1=w1+(n*x1)*(d-y);
  22      w2=w2+(n*x2)*(d-y);
  23      w3=w3+(n*x3)*(d-y);
}
 25  int main()
  26  {
  27      double y=0.0, w0=0.0, w1=0.0, w2=0.0,w3=0.0;
  28  ifstream fin;
  29  string file_name;
  30  cout<<"Enter input file name: "<<endl; //asking user for file name
  31  cin>>file_name;
  32  fin.open(file_name.c_str(),ios::in); //converting to c-string
  33  if(!fin.is_open()) //condition on not being able to open file
  34  {
  35      cerr<<"Error opening file"<<endl;
  36      exit(2);
  37     }
  38  double x0,x1,x2,x3,d; //declaring x0,x1,x2,x3,d
  39      for(int i=0; i<100; i++) //running loop 100times
  40  {
  41  //resetting file
  42  fin.clear();
  43  fin.seekg(0);
  44  fin>>x0>>x1>>x2>>x3>>d;
  45      update(w0,w1,w2,w3,x0,x1,x2,x3,d); //updating weights
  46  }
  47  cout<<w0<<endl;                 //printing w0
  48  cout<<w1<<endl;
  49  fin.close();                  //closing file
  50  return 0;                    //exit
  51  }
  52

only thing is my numbers are still wrong for example w0 in the sample case above is 1 and mine gives 154.996

Edited 6 Years Ago by aqidis: n/a

Please stop adding the line numbers yourself. The code tags will do that. If I want to copy/paste your code into my own compiler I have to delete those numbers that you posted. I did that the first time, but I'm not going to do it again. So repost the code without those numbers that you put there.

#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
double eval(double x0,double x1, double x2,double x3, double w0,
             double w1, double w2,double w3)
     {
         w0=w1=w2=w3=0.0;  //initializing weights
         double y;
         y=(w0*x0)+(w1*x1)+(w2*x2)+(w3*x3);//calculating y
         return y;
     }
void update(double &w0, double &w1, double &w2, double &w3,
            double x0, double x1, double x2, double x3, double d)
//updating weights
{
    double y;
    y=eval(x0,x1,x2,x3,w0,w1,w2,w3);
    double n=0.05;
    w0=w0+(n*x0)*(d-y);
    w1=w1+(n*x1)*(d-y);
    w2=w2+(n*x2)*(d-y);
    w3=w3+(n*x3)*(d-y);
 }
int main()
{
    double y=0.0, w0=0.0, w1=0.0, w2=0.0,w3=0.0;
ifstream fin;
string file_name;
cout<<"Enter input file name: "<<endl; //asking user for file name
cin>>file_name;
fin.open(file_name.c_str(),ios::in); //converting to c-string
if(!fin.is_open()) //condition on not being able to open file
{
    cerr<<"Error opening file"<<endl;
    exit(2);
}
double x0,x1,x2,x3,d; //declaring x0,x1,x2,x3,d
    for(int i=0; i<100; i++) //running loop 100times
{
//resetting file
fin.clear();
fin.seekg(0);
fin>>x0>>x1>>x2>>x3>>d;
    update(w0,w1,w2,w3,x0,x1,x2,x3,d); //updating weights
}
cout<<w0<<endl;                 //printing w0
cout<<w1<<endl;
fin.close();                  //closing file
return 0;                    //exit
}

Much better :) Replace the header cstring with string. Your program uses nothing from string.h (cstring) but does use the c++ std::string class from string.

Well now all your program is doing is reading the first line of the file 100 times. What are you to do with all the rest of the data in that file? Your program might as well read the first line of the file once then call update() 100 times with the same values. Like this

double x0,x1,x2,x3,d; //declaring x0,x1,x2,x3,d

fin>>x0>>x1>>x2>>x3>>d;
for(int i=0; i<100; i++) //running loop 100times
{

    update(w0,w1,w2,w3,x0,x1,x2,x3,d); //updating weights
}

Edited 6 Years Ago by Ancient Dragon: n/a

I'm sorry I dont really understand what you mean :(
I tried to set the loop the way you had it, it still gave me the same numbers

Edited 6 Years Ago by aqidis: n/a

Yup -- that's why I said there is no point reading the same line of the file 100 times.

I don't know the correct solution to your problem because I don't really understand the math. First sit down with pencil & paper and work out the math by hand. Once you understand the math then you can program it.

I am playing around learning algorithms these days and after a few try, I make a toy example of LMS, both batch gradient descent and stochastic gradient descent.

I go through your code and finds something. tough not sure about wich you are trying, batch or stochastic, I am wondering you needs to sum up and loop the whole training set when uodating one thet(parameter) for batch gradient descent.

For the implementation, the learning rate, alpha, (n) in your program is important. Large ones makes it diverge and small ones takes trememdous of step to converge. It needs some guess here.

I post my code here:
sorry about the opencv codes here, but I think that part is easy to understand

// regression.cpp :
//

#include "stdafx.h"
#include <opencv\cv.h>
#include <opencv\highgui.h>

using namespace std;
using namespace cv;

int _tmain(int argc, _TCHAR* argv[])
{
    vector<Point2f> Point_list;

    Point_list.push_back(Point2f(208,21.6));
    Point_list.push_back(Point2f(152,15.5));
    Point_list.push_back(Point2f(113,10.4));
    Point_list.push_back(Point2f(227,31.0));
    Point_list.push_back(Point2f(137,13.0));
    Point_list.push_back(Point2f(238,32.4));
    Point_list.push_back(Point2f(178,19.0));
    Point_list.push_back(Point2f(104,10.4));
    Point_list.push_back(Point2f(191,19.0));
    Point_list.push_back(Point2f(130,11.8));

    double theta_0=0;
    double theta_1=0;
    //y=theta_0+theta_1*x
    float alpha=0.00001;

    int count=0;

    //stochastic gradient descent
    while(1)
    {
        count++;
        //check j(theta)
        vector<Point2f>::iterator it=Point_list.begin();
        //long j_theta=abs((theta_0 + (theta_1*it->x)) - it->y);
        double test=(theta_0 + (theta_1*it->x)) - it->y;
        cout<<theta_0<<endl;
        cout<<theta_1<<endl;
        double j_theta=std::pow((theta_0 + (theta_1*it->x)) - it->y,2.0);
        //double j_theta=std::abs((theta_0 + (theta_1*it->x)) - it->y);
        it++;
        while(it!=Point_list.end())
        {
            //j_theta+=abs((theta_0 + (theta_1*it->x)) - it->y);
            j_theta+=std::pow((theta_0 + (theta_1*it->x)) - it->y,2.0);
            it++;
        }

        j_theta/=2;

        cout<<j_theta<<endl;

        if(j_theta<25)
            break;

        it=Point_list.begin();

        while(it!=Point_list.end())
        {
            double temp=it->y - (theta_0 + (theta_1*it->x));
            theta_0=theta_0 + alpha*(it->y - (theta_0 + (theta_1*it->x)));
            double temp2=(it->y - (theta_0 + (theta_1*it->x)))*it->x;
            theta_1=theta_1 + alpha*(it->y - (theta_0 + (theta_1*it->x)))*it->x;
            it++;
        }
    }

    //batch gradient descent
    //while(1)
    //{
    //  //check j theta
    //  vector<Point2f>::iterator it=Point_list.begin();
    //  double test=(theta_0 + (theta_1*it->x)) - it->y;
    //  cout<<theta_0<<endl;
    //  cout<<theta_1<<endl;
    //  double j_theta=std::pow((theta_0 + (theta_1*it->x)) - it->y,2.0);
    //  //double j_theta=std::abs((theta_0 + (theta_1*it->x)) - it->y);
    //  it++;
    //  while(it!=Point_list.end())
    //  {
    //      //j_theta+=abs((theta_0 + (theta_1*it->x)) - it->y);
    //      j_theta+=std::pow((theta_0 + (theta_1*it->x)) - it->y,2.0);
    //      it++;
    //  }

    //  j_theta/=2;

    //  cout<<j_theta<<endl;

    //  //if(j_theta<50)
    //  //  break;

    //  it=Point_list.begin();
    //  double temp=it->y - (theta_0 + (theta_1*it->x));
    //  while(it!=Point_list.end())
    //  {
    //      temp+=it->y - (theta_0 + (theta_1*it->x));
    //      it++;
    //  }

    //  theta_0=theta_0+alpha*temp;

    //  it=Point_list.begin();
    //  temp=it->x * (it->y - (theta_0 + (theta_1*it->x)));
    //  while(it!=Point_list.end())
    //  {
    //      temp+=it->x * (it->y - (theta_0 + (theta_1*it->x)));
    //      it++;
    //  }

    //  theta_1=theta_1+alpha*temp;

    //}

    cout<<"count:"<<count<<endl;
    system("pause");

    return 0;
}
This article has been dead for over six months. Start a new discussion instead.