libsgdqn-1.0/0000755000355101171100000000000011220435162012461 5ustar bordesmalirelibsgdqn-1.0/lib/0000755000355101171100000000000011217745630013241 5ustar bordesmalirelibsgdqn-1.0/lib/gzstream.h0000644000355101171100000001077311217675316015261 0ustar bordesmalire// ============================================================================ // gzstream, C++ iostream classes wrapping the zlib compression library. // Copyright (C) 2001 Deepak Bandyopadhyay, Lutz Kettner // // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // Lesser General Public License for more details. // // You should have received a copy of the GNU Lesser General Public // License along with this library; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA // ============================================================================ // // File : gzstream.h // Revision : $Revision: 1.1 $ // Revision_date : $Date: 2007/07/31 20:09:14 $ // Author(s) : Deepak Bandyopadhyay, Lutz Kettner // // Standard streambuf implementation following Nicolai Josuttis, "The // Standard C++ Library". // ============================================================================ #ifndef GZSTREAM_H #define GZSTREAM_H 1 // standard C++ with new header file names and std:: namespace #include #include #include #ifdef GZSTREAM_NAMESPACE namespace GZSTREAM_NAMESPACE { #endif // ---------------------------------------------------------------------------- // Internal classes to implement gzstream. See below for user classes. // ---------------------------------------------------------------------------- class gzstreambuf : public std::streambuf { private: static const int bufferSize = 47+256; // size of data buff // totals 512 bytes under g++ for igzstream at the end. gzFile file; // file handle for compressed file char buffer[bufferSize]; // data buffer char opened; // open/close state of stream int mode; // I/O mode int flush_buffer(); public: gzstreambuf() : opened(0) { setp( buffer, buffer + (bufferSize-1)); setg( buffer + 4, // beginning of putback area buffer + 4, // read position buffer + 4); // end position // ASSERT: both input & output capabilities will not be used together } int is_open() { return opened; } gzstreambuf* open( const char* name, int open_mode); gzstreambuf* close(); ~gzstreambuf() { close(); } virtual int overflow( int c = EOF); virtual int underflow(); virtual int sync(); }; class gzstreambase : virtual public std::ios { protected: gzstreambuf buf; public: gzstreambase() { init(&buf); } gzstreambase( const char* name, int open_mode); ~gzstreambase(); void open( const char* name, int open_mode); void close(); gzstreambuf* rdbuf() { return &buf; } }; // ---------------------------------------------------------------------------- // User classes. Use igzstream and ogzstream analogously to ifstream and // ofstream respectively. They read and write files based on the gz* // function interface of the zlib. Files are compatible with gzip compression. // ---------------------------------------------------------------------------- class igzstream : public gzstreambase, public std::istream { public: igzstream() : std::istream( &buf) {} igzstream( const char* name, int open_mode = std::ios::in) : gzstreambase( name, open_mode), std::istream( &buf) {} gzstreambuf* rdbuf() { return gzstreambase::rdbuf(); } void open( const char* name, int open_mode = std::ios::in) { gzstreambase::open( name, open_mode); } }; class ogzstream : public gzstreambase, public std::ostream { public: ogzstream() : std::ostream( &buf) {} ogzstream( const char* name, int mode = std::ios::out) : gzstreambase( name, mode), std::ostream( &buf) {} gzstreambuf* rdbuf() { return gzstreambase::rdbuf(); } void open( const char* name, int open_mode = std::ios::out) { gzstreambase::open( name, open_mode); } }; #ifdef GZSTREAM_NAMESPACE } // namespace GZSTREAM_NAMESPACE #endif #endif // GZSTREAM_H // ============================================================================ // EOF // libsgdqn-1.0/lib/gzstream.cpp0000644000355101171100000001174511217675316015614 0ustar bordesmalire// ============================================================================ // gzstream, C++ iostream classes wrapping the zlib compression library. // Copyright (C) 2001 Deepak Bandyopadhyay, Lutz Kettner // // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // Lesser General Public License for more details. // // You should have received a copy of the GNU Lesser General Public // License along with this library; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA // ============================================================================ // // File : gzstream.C // Revision : $Revision: 1.1 $ // Revision_date : $Date: 2007/07/31 20:09:14 $ // Author(s) : Deepak Bandyopadhyay, Lutz Kettner // // Standard streambuf implementation following Nicolai Josuttis, "The // Standard C++ Library". // ============================================================================ #include #include #include // for memcpy #ifdef GZSTREAM_NAMESPACE namespace GZSTREAM_NAMESPACE { #endif // ---------------------------------------------------------------------------- // Internal classes to implement gzstream. See header file for user classes. // ---------------------------------------------------------------------------- // -------------------------------------- // class gzstreambuf: // -------------------------------------- gzstreambuf* gzstreambuf::open( const char* name, int open_mode) { if ( is_open()) return (gzstreambuf*)0; mode = open_mode; // no append nor read/write mode if ((mode & std::ios::ate) || (mode & std::ios::app) || ((mode & std::ios::in) && (mode & std::ios::out))) return (gzstreambuf*)0; char fmode[10]; char* fmodeptr = fmode; if ( mode & std::ios::in) *fmodeptr++ = 'r'; else if ( mode & std::ios::out) *fmodeptr++ = 'w'; *fmodeptr++ = 'b'; *fmodeptr = '\0'; file = gzopen( name, fmode); if (file == 0) return (gzstreambuf*)0; opened = 1; return this; } gzstreambuf * gzstreambuf::close() { if ( is_open()) { sync(); opened = 0; if ( gzclose( file) == Z_OK) return this; } return (gzstreambuf*)0; } int gzstreambuf::underflow() { // used for input buffer only if ( gptr() && ( gptr() < egptr())) return * reinterpret_cast( gptr()); if ( ! (mode & std::ios::in) || ! opened) return EOF; // Josuttis' implementation of inbuf int n_putback = gptr() - eback(); if ( n_putback > 4) n_putback = 4; memcpy( buffer + (4 - n_putback), gptr() - n_putback, n_putback); int num = gzread( file, buffer+4, bufferSize-4); if (num <= 0) // ERROR or EOF return EOF; // reset buffer pointers setg( buffer + (4 - n_putback), // beginning of putback area buffer + 4, // read position buffer + 4 + num); // end of buffer // return next character return * reinterpret_cast( gptr()); } int gzstreambuf::flush_buffer() { // Separate the writing of the buffer from overflow() and // sync() operation. int w = pptr() - pbase(); if ( gzwrite( file, pbase(), w) != w) return EOF; pbump( -w); return w; } int gzstreambuf::overflow( int c) { // used for output buffer only if ( ! ( mode & std::ios::out) || ! opened) return EOF; if (c != EOF) { *pptr() = c; pbump(1); } if ( flush_buffer() == EOF) return EOF; return c; } int gzstreambuf::sync() { // Changed to use flush_buffer() instead of overflow( EOF) // which caused improper behavior with std::endl and flush(), // bug reported by Vincent Ricard. if ( pptr() && pptr() > pbase()) { if ( flush_buffer() == EOF) return -1; } return 0; } // -------------------------------------- // class gzstreambase: // -------------------------------------- gzstreambase::gzstreambase( const char* name, int mode) { init( &buf); open( name, mode); } gzstreambase::~gzstreambase() { buf.close(); } void gzstreambase::open( const char* name, int open_mode) { if ( ! buf.open( name, open_mode)) clear( rdstate() | std::ios::badbit); } void gzstreambase::close() { if ( buf.is_open()) if ( ! buf.close()) clear( rdstate() | std::ios::badbit); } #ifdef GZSTREAM_NAMESPACE } // namespace GZSTREAM_NAMESPACE #endif // ============================================================================ // EOF // libsgdqn-1.0/lib/pstream.h0000644000355101171100000000576711217675316015107 0ustar bordesmalire// -*- C++ -*- // Stream that uses popen/pclose internally // Copyright (C) 2007- Leon Bottou // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA // $Id: pstream.h,v 1.3 2007/10/02 20:40:06 cvs Exp $ #ifndef PSTREAM_H #define PSTREAM_H 1 #include #include #include class pstreambuf : public std::streambuf { private: static const int bsize = 512; char buffer[bsize]; std::FILE *f; int mode; public: pstreambuf() : f(0), mode(0) { setp( buffer, buffer+bsize-1 ); setg( buffer+4, buffer+4, buffer+4 ); } int is_open() { return !!f; } pstreambuf* open(const char *cmd, int open_mode); pstreambuf* close(); ~pstreambuf() { close(); } virtual int overflow( int c = EOF); virtual int underflow(); virtual int sync(); }; class pstreambase : virtual public std::ios { protected: pstreambuf buf; public: pstreambase() { init(&buf); } pstreambase(const char *cmd, int open_mode); ~pstreambase(); void open(const char *cmd, int open_mode); void close(); pstreambuf* rdbuf() { return &buf; } }; // ---------------------------------------------------------------------------- // User classes. Use ipstream and opstream analogously to ifstream and // ofstream respectively. They read and write files using popen(). // ---------------------------------------------------------------------------- class ipstream : public pstreambase, public std::istream { public: ipstream() : std::istream( &buf) {} ipstream( const char* cmd, int open_mode = std::ios::in) : pstreambase(cmd, open_mode), std::istream( &buf) {} pstreambuf* rdbuf() { return pstreambase::rdbuf(); } void open( const char* cmd, int open_mode = std::ios::in) { pstreambase::open(cmd, open_mode); } }; class opstream : public pstreambase, public std::ostream { public: opstream() : std::ostream( &buf) {} opstream( const char *cmd, int mode = std::ios::out) : pstreambase(cmd, mode), std::ostream( &buf) {} pstreambuf* rdbuf() { return pstreambase::rdbuf(); } void open( const char *cmd, int open_mode = std::ios::out) { pstreambase::open( cmd, open_mode); } }; #endif /* ------------------------------------------------------------- Local Variables: c++-font-lock-extra-types: ("\\sw+_t" "[A-Z]\\sw*[a-z]\\sw*" "std::\\sw+") End: ------------------------------------------------------------- */ libsgdqn-1.0/lib/timer.cpp0000644000355101171100000000302711217675316015072 0ustar bordesmalire// -*- C++ -*- // A simple timer. // Copyright (C) 2007- Leon Bottou // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA // $Id: timer.cpp,v 1.6 2007/10/02 20:40:06 cvs Exp $ #include "timer.h" #include #ifdef USE_REALTIME_CLOCK # include # include static double klock() { struct timeval tv; gettimeofday(&tv, NULL); return (double) tv.tv_sec + (double) tv.tv_usec * 1e-6; return (double) std::clock() / (double) CLOCKS_PER_SEC; } #else static double klock() { return (double) std::clock() / (double) CLOCKS_PER_SEC; } #endif Timer::Timer() : a(0), s(0), r(0) { } void Timer::reset() { a = 0; s = 0; r = 0; } double Timer::elapsed() { double n = klock(); if (r) a += n - s; s = n; return a; } double Timer::start() { elapsed(); r = 1; return a; } double Timer::stop() { elapsed(); r = 0; return a; } libsgdqn-1.0/lib/vectors.cpp0000644000355101171100000004376211217675316015451 0ustar bordesmalire// -*- C++ -*- // Little library of vectors and sparse vectors // Copyright (C) 2007- Leon Bottou // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA // $Id: vectors.cpp,v 1.19 2007/10/02 20:40:06 cvs Exp $ #include "vectors.h" #include #include #include #include #include namespace { template inline T min(T a, T b) { return (a < b) ? a : b; } template inline T max(T a, T b) { return (a < b) ? b : a; } } void FVector::Rep::resize(int n) { if (size != n) { if (n > 0) { VFloat *newdata = new VFloat[n]; int i = 0; int s = min(size,n); for (; iresize(size); for (int i=0; idata[i] = data[i]; return newrep; } FVector::FVector() { } FVector::FVector(int n) { Rep *r = rep(); r->resize(n); } FVector::FVector(const SVector &v) { Rep *r = rep(); r->resize(v.size()); int npairs = v.npairs(); const SVector::Pair *pairs = v; for (int i=0; idata[pairs->i] = pairs->v; } double FVector::get(int i) const { const Rep *r = rep(); if (i >=0 && isize) return r->data[i]; assert(i>=0); return 0; } double FVector::set(int i, double v) { w.detach(); Rep *r = rep(); if (i >= r->size) r->resize(i+1); assert(i>=0); r->data[i] = v; return v; } void FVector::clear() { w.detach(); rep()->resize(0); } void FVector::resize(int n) { w.detach(); assert(n >= 0); rep()->resize(n); } void FVector::touch(int i) { if (i >= rep()->size) resize(i+1); } FVector FVector::slice(int fi, int ti) const { assert(ti >= 0); assert(ti >= fi); FVector y; int s = size(); if (s > 0) { fi = min(fi, s-1); ti = max(ti, s-1); int n = ti - fi + 1; y.resize(n); VFloat *yp = y.rep()->data; VFloat *xp = rep()->data + fi; for (int i=0; idata; for (int i=0; isize; i++) d[i] += c1; } void FVector::add(const FVector &v2) { w.detach(); Rep *r = rep(); int m = max(r->size, v2.size()); if (m > r->size) r->resize(m); VFloat *d = r->data; const VFloat *s = (const VFloat*) v2; for (int i=0; isize, v2.size()); if (m > r->size) r->resize(m); VFloat *d = r->data; int npairs = v2.npairs(); const SVector::Pair *pairs = v2; for (int i=0; ii] += pairs->v; } void FVector::add(const FVector &v2, double c2) { w.detach(); Rep *r = rep(); int m = max(r->size, v2.size()); if (m > r->size) r->resize(m); VFloat *d = r->data; const VFloat *s = (const VFloat*) v2; for (int i=0; isize, v2.size()); if (m > r->size) r->resize(m); VFloat *d = r->data; int npairs = v2.npairs(); const SVector::Pair *pairs = v2; for (int i=0; ii] += pairs->v * c2; } void FVector::add(const FVector &v2, double c2, const FVector &q2) { w.detach(); Rep *r = rep(); int m = r->size; m = max(m, v2.size()); m = min(m, q2.size()); if (m > r->size) r->resize(m); VFloat *d = r->data; const VFloat *s = (const VFloat*) v2; const VFloat *q = (const VFloat*) q2; for (int i=0; isize; m = max(m, v2.size()); m = min(m, q2.size()); if (m > r->size) r->resize(m); VFloat *d = r->data; const VFloat *q = (const VFloat*) q2; int npairs = v2.npairs(); const SVector::Pair *pairs = v2; for (int i=0; ii < m; i++, pairs++) d[pairs->i] += pairs->v * q[pairs->i] * c2; } void FVector::scale(double c1) { w.detach(); Rep *r = rep(); VFloat *d = r->data; for (int i=0; isize; i++) d[i] *= c1; } void FVector::combine(double c1, const FVector &v2, double c2) { w.detach(); Rep *r = rep(); int m = max(r->size, v2.size()); if (m > r->size) r->resize(m); VFloat *d = r->data; const VFloat *s = (const VFloat*) v2; for (int i=0; isize, v2.size()); if (m > r->size) r->resize(m); VFloat *d = r->data; int npairs = v2.npairs(); const SVector::Pair *pairs = v2; int j = 0; for (int i=0; ii; j++) d[j] = d[j] * c1; j = pairs->i; d[j] = d[j] * c1 + pairs->v * c2; j++; } if (c1 != 1) for (; j < pairs->i; j++) d[j] = d[j] * c1; } double FVector::sparsity() { w.detach(); Rep *r = rep(); int m = r->size; VFloat *d = r->data; double sparsity = 0.; for (int i=0; isize, x.size()); if (m > r->size) r->resize(m); VFloat *d = r->data; const VFloat *s = (const VFloat*) wp; const VFloat *sp = (const VFloat*) wpp; int npairs = x.npairs(); const SVector::Pair *pairs = x; int j = 0; double diffw=0; for (int i=0; ii; j++) d[j] += 1/lambda; j = pairs->i; diffw = s[j]-sp[j]; if(diffw) d[j] += diffw/ (lambda*diffw+ loss*pairs->v); else d[j] += 1/lambda; j++; } for (; jdata; int m = max(r->size, x.size()); if(m > r->size) r->resize(m); const VFloat *sx = (const VFloat*) x; const VFloat *s = (const VFloat*) wp; const VFloat *sp = (const VFloat*) wpp; for (int i=0; isize, v2.size()); if (m > r->size) r->resize(m); VFloat *d = r->data; const VFloat *s = (const VFloat*) v2; for (int i=0; i>(std::istream &f, FVector &v) { int sz = 0; int msz = 1024; v.clear(); v.resize(msz); for(;;) { int c = f.get(); if (!f.good() || (c=='\n' || c=='\r')) break; if (::isspace(c)) continue; int i; f.unget(); f >> std::skipws >> i >> std::ws; if (f.get() != ':') { f.unget(); f.setstate(std::ios::badbit); break; } double x; f >> std::skipws >> x; if (!f.good()) break; if (i >= sz) sz = i + 1; if (i >= msz) { while(i >= msz) msz += msz; v.resize(msz); } v.set(i,x); } v.resize(sz); return f; } bool FVector::save(std::ostream &f) const { int i = size(); const VFloat *d = rep()->data; f.write((const char*)&i, sizeof(int)); f.write((const char*)d, sizeof(VFloat)*i); return f.good(); } bool FVector::load(std::istream &f) { int i = 0; clear(); f.read((char*)&i, sizeof(int)); if (i<0) f.setstate(std::ios::badbit); if (!f.good()) return false; resize(i); VFloat *d = rep()->data; f.read((char*)d, sizeof(VFloat)*i); return f.good(); } // ---------------------------------------- void SVector::Rep::resize(int n) { if (n != mpairs) { Pair *p = new Pair[n+1]; int m = min(n, npairs); int i = 0; for (; i < m; i++) p[i] = pairs[i]; for (; i <= n; i++) p[i].i = -1; delete [] pairs; pairs = p; npairs = m; mpairs = n; size = (m>0) ? p[m-1].i + 1 : 0; } } SVector::Rep * SVector::Rep::copy() { int n = npairs; Pair *p = new Pair[n+1]; for (int i=0; i < n; i++) p[i] = pairs[i]; p[n].i = -1; Rep *nr = new Rep; delete [] nr->pairs; nr->pairs = p; nr->size = size; nr->npairs = nr->mpairs = n; return nr; } inline double SVector::Rep::qset(int i, double v) { assert(i >= size); if (npairs >= mpairs) { resize(max(16, mpairs+mpairs)); assert(npairs < mpairs); } Pair *p = &pairs[npairs++]; size = i + 1; p->i = i; p->v = v; return v; } SVector::SVector() { trim(); } SVector::SVector(const FVector &v) { int m = v.size(); const VFloat *f = v; Rep *r = rep(); r->resize(m); for (int i=0; iqset(i,f[i]); trim(); } namespace { SVector::Pair * search(SVector::Pair *pairs, int npairs, int i) { int lo = 0; int hi = npairs - 1; while (lo <= hi) { int d = (lo + hi + 1) / 2; if (i == pairs[d].i) return &pairs[d]; else if (i < pairs[d].i) hi = d-1; else lo = d+1; } return 0; } } double SVector::get(int i) const { const Rep *r = rep(); if (i >= r->size) return 0; // binary search assert(i >= 0); SVector::Pair *pair = search(r->pairs, r->npairs, i); if (pair) return pair->v; return 0; } double SVector::set(int i, double v) { w.detach(); Rep *r = rep(); if (v) { if (i >= r->size) return r->qset(i, v); assert(i >= 0); SVector::Pair *p = search(r->pairs, r->npairs, i); if (p) return p->v = v; if (r->npairs >= r->mpairs) { r->resize(max(16, r->mpairs + min(r->mpairs, 4096))); assert(r->npairs < r->mpairs); } SVector::Pair *s = r->pairs; p = s + r->npairs; r->npairs += 1; for (; p > s && p[-1].i > i; p--) p[0] = p[-1]; p[0].i = i; p[0].v = v; } else { SVector::Pair *s = r->pairs; SVector::Pair *p = search(s, r->npairs, i); if (p) { r->npairs -= 1; for (; p->i >= 0; p++) p[0] = p[1]; } } return v; } void SVector::clear() { w.detach(); rep()->resize(0); } void SVector::trim() { w.detach(); Rep *r = rep(); r->resize(r->npairs); } SVector SVector::slice(int fi, int ti) const { assert(ti >= 0); assert(ti >= fi); SVector y; for(Pair *p = rep()->pairs; p->i >= 0 && p->i <= ti; p++) if (p->i >= fi) y.set(p->i, p->v); return y; } void SVector::add(const SVector &v2) { operator=( ::combine(*this, 1, v2, 1) ); } void SVector::add(const SVector &v2, double c2) { operator=( ::combine(*this, 1, v2, c2) ); } void SVector::combine(double c1, const SVector &v2, double c2) { operator=( ::combine(*this, c1, v2, c2) ); } void SVector::scale(double c1) { if (c1) { w.detach(); Rep *r = rep(); Pair *pairs = r->pairs; int npairs = r->npairs; for (int i=0; ipairs; int npairs = r->npairs; std::ios::fmtflags oldflags = f.flags(); std::streamsize oldprec = f.precision(); f << std::scientific << std::setprecision(sizeof(VFloat)==4 ? 7 : 16); for (int i=0; i>(std::istream &f, SVector &v) { v.clear(); for(;;) { int c = f.get(); if (!f.good() || (c=='\n' || c=='\r')) break; if (::isspace(c)) continue; int i; f.unget(); f >> std::skipws >> i >> std::ws; if (f.get() != ':') { f.unget(); f.setstate(std::ios::badbit); break; } double x; f >> std::skipws >> x; if (!f.good()) break; v.set(i,x); } v.trim(); return f; } bool SVector::save(std::ostream &f) const { const Rep *r = rep(); const Pair *pairs = r->pairs; int npairs = r->npairs; f.write((const char*)&npairs, sizeof(int)); f.write((const char*)pairs, sizeof(Pair)*npairs); return f.good(); } bool SVector::load(std::istream &f) { clear(); int npairs = 0; f.read((char*)&npairs, sizeof(int)); if (npairs < 0) f.setstate(std::ios::badbit); if (!f.good()) return false; rep()->resize(npairs); for (int i=0; i= 0) sum += (double)(*f1++) * (double)(*f2++); return sum; } double dot(const FVector &v1, const SVector &v2) { int m = v1.size(); const VFloat *f = v1; const SVector::Pair *p = v2; double sum = 0; if (p) for( ; p->i >= 0 && p->i < m; p++) sum += (double)p->v * (double)f[p->i]; return sum; } double dot(const SVector &v1, const FVector &v2) { int m = v2.size(); const VFloat *f = v2; const SVector::Pair *p = v1; double sum = 0; if (p) for( ; p->i >= 0 && p->i < m; p++) sum += (double)p->v * (double)f[p->i]; return sum; } double dot(const SVector &v1, const SVector &v2) { const SVector::Pair *p1 = v1; const SVector::Pair *p2 = v2; double sum = 0; if (p1 && p2) while (p1->i >= 0 && p2->i >= 0) { if (p1->i < p2->i) p1++; else if (p1->i > p2->i) p2++; else sum += (double)(p1++)->v * (double)(p2++)->v; } return sum; } SVector combine(const SVector &v1, double a1, const SVector &v2, double a2) { const SVector::Pair *p1 = v1; const SVector::Pair *p2 = v2; SVector ans; SVector::Rep *r = ans.rep(); r->resize(v1.npairs() + v2.npairs()); SVector::Pair *p = r->pairs; while (p1->i >= 0 && p2->i >= 0) { if (p1->i < p2->i) { double v = (double)p1->v * a1; if (v) { p->i = p1->i; p->v = v; p++; } p1++; } else if (p1->i > p2->i) { double v = (double)p2->v * a2; if (v) { p->i = p2->i; p->v = v; p++; } p2++; } else { double v = (double)p1->v * a1 + (double)p2->v * a2; if (v) { p->i = p1->i; p->v = v; p++; } p1++; p2++; } } while (p1->i >= 0) { double v = (double)p1->v * a1; if (v) { p->i = p1->i; p->v = v; p++; } p1++; } while (p2->i >= 0) { double v = (double)p2->v * a2; if (v) { p->i = p2->i; p->v = v; p++; } p2++; } r->npairs = p - r->pairs; r->size = (r->npairs > 0) ? p[-1].i + 1 : 0; ans.trim(); return ans; } FVector combine(const FVector &v1, double a1, const SVector &v2, double a2) { FVector r = v1; r.combine(a1, v2, a2); return r; } FVector combine(const SVector &v1, double a1, const FVector &v2, double a2) { FVector r = v2; r.combine(a2, v1, a1); return r; } FVector combine(const FVector &v1, double a1, const FVector &v2, double a2) { FVector r = v1; r.combine(a1, v2, a2); return r; } /* ------------------------------------------------------------- Local Variables: c++-font-lock-extra-types: ( "\\sw+_t" "[A-Z]\\sw*[a-z]\\sw*" "std::\\sw+") End: ------------------------------------------------------------- */ libsgdqn-1.0/lib/pstream.cpp0000644000355101171100000000656111217675316015433 0ustar bordesmalire// -*- C++ -*- // Stream that uses popen/pclose internally // Copyright (C) 2007- Leon Bottou // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA // $Id: pstream.cpp,v 1.4 2007/10/02 20:40:05 cvs Exp $ #include "pstream.h" #include pstreambuf* pstreambuf::open( const char *cmd, int open_mode) { if (f) return 0; mode = open_mode; if ((mode & std::ios::ate) || (mode & std::ios::app) || ((mode & std::ios::in) && (mode & std::ios::out))) return 0; char fmode[10]; char *fmodeptr = fmode; if ( mode & std::ios::in) *fmodeptr++ = 'r'; else if ( mode & std::ios::out) *fmodeptr++ = 'w'; #ifdef WIN32 if (mode & std::ios::binary) *fmodeptr++ = 'b'; *fmodeptr = '\0'; f = ::_popen(cmd, fmode); #else *fmodeptr = '\0'; f = ::popen(cmd, fmode); #endif if (f == 0) return 0; return this; } pstreambuf* pstreambuf::close() { if (f) { sync(); #ifdef WIN32 ::_pclose(f); #else ::pclose(f); #endif f = 0; return this; } return 0; } int pstreambuf::underflow() { // used for input buffer only if ( gptr() && ( gptr() < egptr())) return *reinterpret_cast( gptr()); if ( ! (mode & std::ios::in) || ! f) return EOF; int n_putback = gptr() - eback(); if ( n_putback > 4) n_putback = 4; memcpy(buffer + (4 - n_putback), gptr()-n_putback, n_putback); int num = std::fread(buffer+4, 1, bsize-4, f); if (num <= 0) return EOF; setg( buffer + (4 - n_putback), // beginning of putback area buffer + 4, // read position buffer + 4 + num); // end of buffer // return next character return *reinterpret_cast( gptr()); } int pstreambuf::overflow(int c) { // used for output buffer only if (!(mode & std::ios::out) || !f) return EOF; if (c != EOF) { *pptr() = c; pbump(1); } if (! sync()) return c; return EOF; } int pstreambuf::sync() { if ( pptr() && pptr() > pbase()) { int w = pptr() - pbase(); if (std::fwrite( pbase(), 1, w, f ) != (size_t)w) return EOF; pbump( -w); } return 0; } pstreambase::pstreambase( const char* cmd, int mode) { init(&buf); open(cmd, mode); } pstreambase::~pstreambase() { buf.close(); } void pstreambase::open( const char* cmd, int open_mode) { if (! buf.open(cmd, open_mode)) setstate( std::ios::badbit); } void pstreambase::close() { if (buf.is_open()) if (! buf.close()) setstate(std::ios::badbit); } /* ------------------------------------------------------------- Local Variables: c++-font-lock-extra-types: ("\\sw+_t" "[A-Z]\\sw*[a-z]\\sw*" ) End: ------------------------------------------------------------- */ libsgdqn-1.0/lib/matrices.h0000644000355101171100000000541011217675316015224 0ustar bordesmalire// -*- C++ -*- // Little library of matrices and sparse matrices // Copyright (C) 2007- Leon Bottou // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA // $Id: matrices.h,v 1.4 2007/10/02 20:40:05 cvs Exp $ #ifndef MATRICES_H #define MATRICES_H 1 #include #include #include #include #include "wrapper.h" #include "vectors.h" class FMatrix { private: struct Rep { int refcount; int ncols; int nrows; std::vector rows; Rep() : ncols(0), nrows(0) { } Rep *copy() { return new Rep(*this); } }; Wrapper w; Rep *rep() { return w.rep(); } const Rep *rep() const { return w.rep(); } public: FMatrix() {} FMatrix(int rows, int cols) { resize(rows, cols); } int rows() const { return rep()->nrows; } int cols() const { return rep()->ncols; } void resize(int nrows, int ncols=-1); VFloat get(int r, int c) const; void set(int r, int c, VFloat v); FVector& operator[](int r); const FVector operator[](int r) const { const Rep *d = rep(); if (r<0 || r>=d->nrows) return FVector(); return d->rows[r]; } }; class SMatrix { private: struct Rep { int refcount; int ncols; int nrows; std::vector rows; Rep() : ncols(0), nrows(0) { } Rep *copy() { return new Rep(*this); } }; Wrapper w; Rep *rep() { return w.rep(); } const Rep *rep() const { return w.rep(); } public: SMatrix() {} SMatrix(int rows, int cols) { resize(rows,cols); } int rows() const { return rep()->nrows; } int cols() const { return rep()->ncols; } void resize(int nrows, int ncols=-1); VFloat get(int r, int c) const; void set(int r, int c, VFloat v); SVector& operator[](int r); const SVector operator[](int r) const { const Rep *d = rep(); if (r<0 || r>=d->nrows) return SVector(); return d->rows[r]; } }; #endif /* ------------------------------------------------------------- Local Variables: c++-font-lock-extra-types: ("\\sw+_t" "[A-Z]\\sw*[a-z]\\sw*" "std::\\sw+") End: ------------------------------------------------------------- */ libsgdqn-1.0/lib/timer.h0000644000355101171100000000237411217675316014543 0ustar bordesmalire// -*- C++ -*- // A simple timer. // Copyright (C) 2007- Leon Bottou // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA // $Id: timer.h,v 1.4 2007/10/02 20:40:06 cvs Exp $ #ifndef TIMER_H #define TIMER_H 1 class Timer { public: Timer(); void reset(); double start(); double stop(); double elapsed(); private: double a, s; int r; }; /* ------------------------------------------------------------- Local Variables: c++-font-lock-extra-types: ("\\sw+_t" "[A-Z]\\sw*[a-z]\\sw*" "std::\\sw+_t") End: ------------------------------------------------------------- */ #endif libsgdqn-1.0/lib/vectors.h0000644000355101171100000001225711217675316015111 0ustar bordesmalire// -*- C++ -*- // Little library of vectors and sparse vectors // Copyright (C) 2007- Leon Bottou // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA // $Id: vectors.h,v 1.13 2007/10/02 20:40:06 cvs Exp $ #ifndef VECTORS_H #define VECTORS_H 1 #include #include #include #include "wrapper.h" class FVector; class SVector; typedef float VFloat; class FVector { private: struct Rep { int refcount; int size; VFloat *data; Rep() : size(0), data(0) {} ~Rep() { delete [] data; } void resize(int n); Rep *copy(); }; Wrapper w; Rep *rep() { return w.rep(); } const Rep *rep() const { return w.rep(); } void qset(int i, double v); public: FVector(); FVector(int n); FVector(const SVector &v); int size() const { return rep()->size; } // these accessors are range-checked. // get() returns 0 when i is out-of-range. // set() expands the vector. double get(int i) const; double set(int i, double v); // warning: you can write vector[i] but // the subscripts are not range-checked! // on the other hand, that's fast. operator const VFloat* () const { return rep()->data; } operator VFloat* () { w.detach(); return rep()->data; } void clear(); void resize(int n); void touch(int i); FVector slice(int fi, int ti) const; void add(double c1); void add(const FVector &v2); void add(const SVector &v2); void add(const FVector &v2, double c2); void add(const SVector &v2, double c2); void add(const FVector &v2, double c2, const FVector &q2); void add(const SVector &v2, double c2, const FVector &q2); void scale(double c1); void combine(double c1, const FVector &v2, double c2); void combine(double c1, const SVector &v2, double c2); //new double sparsity(); void compute_ratio(const SVector &x, double lambda, const FVector &w, const FVector &wp, double loss); void compute_ratio(const FVector &x, double lambda, const FVector &w, const FVector &wp, double loss); // void scale_and_clip(double c1, double vmin, double vmax); void combine_and_clip(double c1, const FVector &v2, double c2, double vmin, double vmax); friend std::ostream& operator<<(std::ostream &f, const FVector &v); friend std::istream& operator>>(std::istream &f, FVector &v); bool save(std::ostream &f) const; bool load(std::istream &f); }; class SVector { public: struct Pair { int i; VFloat v; }; private: struct Rep { int refcount; int npairs; int mpairs; int size; struct Pair *pairs; Rep() : npairs(0), mpairs(-1), size(0), pairs(0) {} ~Rep() { delete [] pairs; } void resize(int n); double qset(int i, double v); Rep *copy(); }; Wrapper w; Rep *rep() { return w.rep(); } const Rep *rep() const { return w.rep(); } public: SVector(); SVector(const FVector &v); int size() const { return rep()->size; } // these accessors are range-checked. // get() returns 0 when i is out-of-range. // set() expands the vector. double get(int i) const; double set(int i, double v); // to quickly iterate over the non-zero coefficients, // do for(SVector::Pair *p = x; p->i>=0; p++) { ... } int npairs() const { return rep()->npairs; } operator const Pair* () const { return rep()->pairs; } void clear(); void trim(); SVector slice(int fi, int ti) const; void add(const SVector &v2); void add(const SVector &v2, double c2); void scale(double c1); void combine(double c1, const SVector &v2, double c2); friend std::ostream& operator<<(std::ostream &f, const SVector &v); friend std::istream& operator>>(std::istream &f, SVector &v); bool save(std::ostream &f) const; bool load(std::istream &f); friend SVector combine(const SVector &v1, double a1, const SVector &v2, double a2); }; double dot(const FVector &v1, const FVector &v2); double dot(const FVector &v1, const SVector &v2); double dot(const SVector &v1, const FVector &v2); double dot(const SVector &v1, const SVector &v2); SVector combine(const SVector &v1, double a1, const SVector &v2, double a2); FVector combine(const FVector &v1, double a1, const SVector &v2, double a2); FVector combine(const SVector &v1, double a1, const FVector &v2, double a2); FVector combine(const FVector &v1, double a1, const FVector &v2, double a2); #endif /* ------------------------------------------------------------- Local Variables: c++-font-lock-extra-types: ("\\sw+_t" "[A-Z]\\sw*[a-z]\\sw*" "std::\\sw+") End: ------------------------------------------------------------- */ libsgdqn-1.0/lib/matrices.cpp0000644000355101171100000000567611217675316015575 0ustar bordesmalire// -*- C++ -*- // Little library of matrices and sparse matrices // Copyright (C) 2007- Leon Bottou // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA #include #include void FMatrix::resize(int nrows, int ncols) { w.detach(); Rep *d = rep(); if (nrows >= 0) { d->rows.resize(nrows); d->nrows = nrows; } if (ncols >= 0) { d->ncols = ncols; for (int i=0; inrows; i++) d->rows[i].resize(ncols); } } VFloat FMatrix::get(int r, int c) const { const Rep *d = rep(); if (r>=0 && rnrows) return d->rows[r].get(c); assert(r >= 0); return 0; } void FMatrix::set(int r, int c, VFloat v) { w.detach(); Rep *d = rep(); if (r>=d->nrows) resize(r+1); if (c>=d->ncols) d->ncols = c+1; assert(r >= 0); d->rows[r].set(c,v); } FVector& FMatrix::operator[](int r) { w.detach(); Rep *d = rep(); if (r>=d->nrows) resize(r+1); assert(r >= 0); return d->rows[r]; } // ---------------------------------------- void SMatrix::resize(int nrows, int ncols) { w.detach(); Rep *d = rep(); if (nrows >= 0) { d->rows.resize(nrows); d->nrows = nrows; } if (ncols >= 0 && ncols < d->ncols) { d->ncols = ncols; for (int i=0; inrows; i++) if (d->rows[i].size() > ncols) { // truncate SVector s = d->rows[i]; SVector &v = d->rows[i]; v.clear(); for (const SVector::Pair *p = s; p->i >= 0 && p->i < ncols; p++) v.set(p->i, p->v); } } } VFloat SMatrix::get(int r, int c) const { const Rep *d = rep(); if (r>=0 && rnrows) return d->rows[r].get(c); assert(r>=0); return 0; } void SMatrix::set(int r, int c, VFloat v) { w.detach(); Rep *d = rep(); if (r>=d->nrows) resize(r+1); if (c>=d->ncols) d->ncols = c+1; assert(r>=0); d->rows[r].set(c,v); } SVector& SMatrix::operator[](int r) { w.detach(); Rep *d = rep(); if (r>=d->nrows) resize(r+1); assert(r>=0); return d->rows[r]; } /* ------------------------------------------------------------- Local Variables: c++-font-lock-extra-types: ("\\sw+_t" "[A-Z]\\sw*[a-z]\\sw*") End: ------------------------------------------------------------- */ libsgdqn-1.0/lib/wrapper.h0000644000355101171100000000527611217675316015107 0ustar bordesmalire// -*- C++ -*- // Little library of copy-on-write wrappers // Copyright (C) 2007- Leon Bottou // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA // $Id: wrapper.h,v 1.8 2007/10/02 20:40:06 cvs Exp $ #ifndef WRAPPER_H #define WRAPPER_H 1 template class Wrapper { private: Rep *q; Rep *ref(Rep *q) { q->refcount++; return q; } void deref(Rep *q) { if (! --(q->refcount)) delete q; } public: Wrapper() : q(new Rep) { q->refcount = 1; } Wrapper(Rep *rep) : q(rep) { q->refcount = 1; } Wrapper(const Wrapper &other) : q(ref(other.q)) {} ~Wrapper() { deref(q); } Wrapper& operator=(const Wrapper &other) { Rep *p = q; q = ref(other.q); deref(p); return *this; } void detach() { if (q->refcount > 1) { deref(q); q=q->copy(); q->refcount=1; } } Rep *rep() const { return q; } }; // Recommended usage // // #include // #include // // class String // { // private: // // struct Rep // { // int refcount; // int length; // char *data; // Rep(const char *s, int l) // : length(len), data(new char[l+1]) // { ::memcpy(data, s, l); data[len] = 0; } // Rep *copy() // { return new StringRep(data, length); } // }; // // Wrapper w; // Rep *rep() { return w.rep(); } // const Rep *rep() const { return w.rep(); } // // public: // String(const char *s, int l) // : w(new Rep(s,l)) {} // String(const char *s) // : w(new Rep(s,::strlen(s))) {} // // // function that do not mutate // int size() const { return rep()->length; } // operator const char*() const { return rep()->data; } // char operator[](int i) const { return rep()->data[i]; } // // // functions that perform a mutation // void set(int i, char c) { w.detach(); rep()->data[i] = c; } // } // #endif /* ------------------------------------------------------------- Local Variables: c++-font-lock-extra-types: ( "\\sw+_t" "[A-Z]\\sw*[a-z]\\sw*" ) End: ------------------------------------------------------------- */ libsgdqn-1.0/svm/0000755000355101171100000000000011220435245013270 5ustar bordesmalirelibsgdqn-1.0/svm/svmsgd2.cpp0000644000355101171100000003146711220203344015365 0ustar bordesmalire// -*- C++ -*- // SVM with stochastic gradient // Copyright (C) 2007- Leon Bottou // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA #include "vectors.h" #include "gzstream.h" #include "timer.h" #include #include #include #include #include #include #include #include #include #ifndef DENSE_DATA // set this value to 1 if you are not using sparse data # define DENSE_DATA 1 #endif #if DENSE_DATA #define SVector FVector #endif using namespace std; typedef vector xvec_t; typedef vector yvec_t; // Available losses #define HINGELOSS 1 #define SMOOTHHINGELOSS 2 #define SQUAREDHINGELOSS 3 #define LOGLOSS 10 #define LOGLOSSMARGIN 11 // Select loss #define LOSS SQUAREDHINGELOSS // Zero when no bias // One when bias term #define BIAS 0 // One when bias is regularized #define REGULARIZEBIAS 0 inline double loss(double z) { #if LOSS == LOGLOSS if (z >= 0) return log(1+exp(-z)); else return -z + log(1+exp(z)); #elif LOSS == LOGLOSSMARGIN if (z >= 1) return log(1+exp(1-z)); else return 1-z + log(1+exp(z-1)); #elif LOSS == SMOOTHHINGELOSS if (z < 0) return 0.5 - z; if (z < 1) return 0.5 * (1-z) * (1-z); return 0; #elif LOSS == SQUAREDHINGELOSS if (z < 1) return 0.5 * (1 - z) * (1 - z); return 0; #elif LOSS == HINGELOSS if (z < 1) return 1 - z; return 0; #else # error "Undefined loss" #endif } inline double dloss(double z) { #if LOSS == LOGLOSS if (z < 0) return 1 / (exp(z) + 1); double ez = exp(-z); return ez / (ez + 1); #elif LOSS == LOGLOSSMARGIN if (z < 1) return 1 / (exp(z-1) + 1); double ez = exp(1-z); return ez / (ez + 1); #elif LOSS == SMOOTHHINGELOSS if (z < 0) return 1; if (z < 1) return 1-z; return 0; #elif LOSS == SQUAREDHINGELOSS if (z < 1) return (1 - z); return 0; #else if (z < 1) return 1; return 0; #endif } // -- stochastic gradient class SvmSgd { public: SvmSgd(int dim, double lambda); void calibrate(int imin, int imax, const xvec_t &x, const yvec_t &y); void train(int imin, int imax, const xvec_t &x, const yvec_t &y, const char *prefix = ""); void test(int imin, int imax, const xvec_t &x, const yvec_t &y, const char *prefix, FVector &infos); private: double t; double lambda; FVector w; double bias; double bscale; int skip; int count; }; SvmSgd::SvmSgd(int dim, double l) : lambda(l), w(dim), bias(0), bscale(1), skip(1000) { // Shift t in order to have a // reasonable initial learning rate. // This assumes |x| \approx 1. double maxw = 1.0 / sqrt(lambda); double typw = sqrt(maxw); double eta0 = typw / max(1.0,dloss(-typw)); t = 1 / (eta0 * lambda); cout << "t0=" << t << endl; } void SvmSgd::calibrate(int imin, int imax, const xvec_t &xp, const yvec_t &yp) { cout << "Estimating sparsity and bscale." << endl; int j; // compute average gradient size double n = 0; double m = 0; double r = 0; #if DENSE_DATA for (j=imin; j<=imax; j++,n++) { const FVector &x = xp.at(j); n += 1; r += x.size(); } m=1000; #else FVector c(w.size()); for (j=imin; j<=imax && m<=1000; j++,n++) { const SVector &x = xp.at(j); n += 1; r += x.npairs(); const SVector::Pair *p = x; while (p->i >= 0 && p->i < c.size()) { double z = c.get(p->i) + fabs(p->v); c.set(p->i, z); m = max(m, z); p += 1; } } #endif // bias update scaling bscale = m/n; // compute weight decay skip skip = (int) ((8 * n * w.size()) / r); cout << " using " << n << " examples." << endl; cout << " skip: " << skip << " bscale: " << setprecision(6) << bscale << endl; } void SvmSgd::train(int imin, int imax, const xvec_t &xp, const yvec_t &yp, const char *prefix) { cout << prefix << "Training on [" << imin << ", " << imax << "]." << endl; assert(imin <= imax); count = skip; for (int i=imin; i<=imax; i++) { const SVector &x = xp.at(i); double y = yp.at(i); double wx = dot(w,x); double z = y * (wx + bias); double eta = 1.0 / (lambda * t); #if LOSS < LOGLOSS if (z < 1) #endif { double etd = eta * dloss(z); w.add(x, etd * y); #if BIAS #if REGULARIZEBIAS bias *= 1 - eta * lambda * bscale; #endif bias += etd * y * bscale; #endif } if (--count <= 0) { double r = 1 - eta * lambda * skip; if (r < 0.8) r = pow(1 - eta * lambda, skip); w.scale(r); count = skip; } t += 1; } cout << prefix << setprecision(6) << "Norm: " << dot(w,w) << ", Bias: " << bias << endl; } void SvmSgd::test(int imin, int imax, const xvec_t &xp, const yvec_t &yp, const char *prefix, FVector &infos) { cout << prefix << "Testing on [" << imin << ", " << imax << "]." << endl; assert(imin <= imax); int nerr = 0; double cost = 0; for (int i=imin; i<=imax; i++) { const SVector &x = xp.at(i); double y = yp.at(i); double wx = dot(w,x); double z = y * (wx + bias); if (z <= 0) nerr += 1; #if LOSS < LOGLOSS if (z < 1) #endif cost += loss(z); } int n = imax - imin + 1; double loss = cost / n; cost = loss + 0.5 * lambda * dot(w,w); cout << prefix << setprecision(4) << "Misclassification: " << (double)nerr * 100.0 / n << "%." << endl; cout << prefix << setprecision(12) << "Cost: " << cost << "." << endl; cout << prefix << setprecision(12) << "Loss: " << loss << "." << endl; infos[1]=(double)nerr/n; infos[2]=cost; } // --- options string trainfile; string testfile; string logfile; double lambda = 1e-4; int epochs = 5; int trainsize = -1; double steps = 1.; void usage() { cerr << "Usage: (sparse_)svmsgd2 [options] trainfile [testfile] [logfile]" << endl << "Options:" << endl << " -lambda " << endl << " -epochs " << endl << " -trainsize " << endl << " -steps : number of intermediate values to be printed in the logfile (including a test error)." << endl << endl; exit(10); } void parse(int argc, const char **argv) { for (int i=1; i0 && lambda<1e4); } else if (opt == "epochs" && i+10 && epochs<1e6); } else if (opt == "trainsize" && i+1 0); } else if (opt == "steps" && i+1 0); } else usage(); } } if (trainfile.empty()) usage(); } // --- loading data int dim; xvec_t xtrain; yvec_t ytrain; xvec_t xtest; yvec_t ytest; ofstream logs; void load(const char *fname, xvec_t &xp, yvec_t &yp) { cout << "Loading " << fname << "." << endl; igzstream f; f.open(fname); if (! f.good()) { cerr << "ERROR: cannot open " << fname << "." << endl; exit(10); } int pcount = 0; int ncount = 0; bool binary; string suffix = fname; if (suffix.size() >= 7) suffix = suffix.substr(suffix.size() - 7); if (suffix == ".dat.gz") binary = false; else if (suffix == ".bin.gz") binary = true; else { cerr << "ERROR: filename should end with .bin.gz or .dat.gz" << endl; exit(10); } while (f.good()) { SVector x; double y; if (binary) { y = (f.get()) ? +1 : -1; x.load(f); } else { f >> y >> x; } if (f.good()) { assert(y == +1 || y == -1); xp.push_back(x); yp.push_back(y); if (y > 0) pcount += 1; else ncount += 1; if (x.size() > dim) dim = x.size(); } if (trainsize > 0 && xp.size() > (unsigned int)trainsize) break; } cout << "Read " << pcount << "+" << ncount << "=" << pcount + ncount << " examples." << endl; } void rearrange(xvec_t& xp, int dim) { double n = xp.size(); FVector sum(dim); FVector var(dim); for(int ex=0; ex 0 && imax >= trainsize) imax = imin + trainsize -1; // prepare svm SvmSgd svm(dim, lambda); // load testing set if (! testfile.empty()) { load(testfile.c_str(), xtest, ytest); #if DENSE_DATA rearrange(xtest,dim); #endif } int tmin = 0; int tmax = xtest.size() - 1; svm.calibrate(imin, imax, xtrain, ytrain); if (! logfile.empty()) { logs.open(logfile.c_str()); logs << "# SVMSGD2. lambda = " << lambda << endl; logs << "# trnsz = " << imax-imin+1 << " , tstsz = " << tmax-tmin+1 << endl; logs << "# it time trn_err trn_cost tst_err tst_cost" << endl; FVector info(2); svm.test(imin, imax, xtrain, ytrain, "train: ",info); logs << 0 << " " << 0 << " " << info[1] << " " << info[2]; if (tmax >= tmin) { svm.test(tmin, tmax, xtest, ytest, "test: ", info); logs << " " << info[1] << " " << info[2]; } logs << endl; } Timer timer; if(! logfile.empty()) for(int i=0; i= tmin) { svm.test(tmin, tmax, xtest, ytest, "test: ", info); logs << " " << info[1] << " " << info[2]; } logs << endl; } } else for(int i=0; i= tmin) svm.test(tmin, tmax, xtest, ytest, "test: ", info); } } libsgdqn-1.0/svm/Makefile0000644000355101171100000000446611217727173014754 0ustar bordesmalire# SVM with stochastic gradient # This program is free software; you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation; either version 2 of the License, or # (at your option) any later version. # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with this program; if not, write to the Free Software # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA L=../lib CXX=g++ OPTS=-g -O2 CXXFLAGS= ${OPTS} -Wall -I$L LIBS = -lz -lm PROGRAMS = svmsgd2 svmsgdqn svmolbfgs \ sparse_svmsgd2 sparse_svmsgdqn sparse_svmolbfgs all: ${PROGRAMS} clean: -rm ${PROGRAMS} 2>/dev/null -rm *.o 2>/dev/null svmsgd2: svmsgd2.cpp vectors.o gzstream.o timer.o ${CXX} ${CXXFLAGS} -DDENSE_DATA=1 -o $@ svmsgd2.cpp vectors.o gzstream.o timer.o ${LIBS} svmsgdqn: svmsgdqn.cpp vectors.o gzstream.o timer.o ${CXX} ${CXXFLAGS} -DDENSE_DATA=1 -o $@ svmsgdqn.cpp vectors.o gzstream.o timer.o ${LIBS} svmolbfgs: svmolbfgs.cpp vectors.o gzstream.o timer.o ${CXX} ${CXXFLAGS} -DDENSE_DATA=1 -o $@ svmolbfgs.cpp vectors.o gzstream.o timer.o ${LIBS} sparse_svmsgd2: svmsgd2.cpp vectors.o gzstream.o timer.o ${CXX} ${CXXFLAGS} -DDENSE_DATA=0 -o $@ svmsgd2.cpp vectors.o gzstream.o timer.o ${LIBS} sparse_svmsgdqn: svmsgdqn.cpp vectors.o gzstream.o timer.o ${CXX} ${CXXFLAGS} -DDENSE_DATA=0 -o $@ svmsgdqn.cpp vectors.o gzstream.o timer.o ${LIBS} sparse_svmolbfgs: svmolbfgs.cpp vectors.o gzstream.o timer.o ${CXX} ${CXXFLAGS} -DDENSE_DATA=0 -o $@ svmolbfgs.cpp vectors.o gzstream.o timer.o ${LIBS} preprocess.o: preprocess.cpp $L/vectors.h $L/gzstream.h ${CXX} ${CXXFLAGS} -c -o $@ preprocess.cpp vectors.o: $L/vectors.cpp $L/vectors.h $L/wrapper.h ${CXX} ${CXXFLAGS} -c -o $@ $L/vectors.cpp matrices.o: $L/matrices.cpp $L/matrices.h $L/vectors.h $L/wrapper.h ${CXX} ${CXXFLAGS} -c -o $@ $L/matrices.cpp gzstream.o: $L/gzstream.cpp $L/gzstream.h ${CXX} ${CXXFLAGS} -c -o $@ $L/gzstream.cpp timer.o: $L/timer.cpp $L/timer.h ${CXX} ${CXXFLAGS} -c -o $@ $L/timer.cpp libsgdqn-1.0/svm/svmsgdqn.cpp0000644000355101171100000003541111220371602015636 0ustar bordesmalire// -*- C++ -*- // SVM with Stochastic Gradient Descent and diagonal Quasi-Newton approximation // Copyright (C) 2009- Antoine Bordes // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA #include "vectors.h" #include "gzstream.h" #include "timer.h" #include #include #include #include #include #include #include #include #include #include #ifndef DENSE_DATA // set this value to 1 if you are not using sparse data # define DENSE_DATA 1 #endif #if DENSE_DATA #define SVector FVector #endif using namespace std; typedef vector xvec_t; typedef vector yvec_t; // Available losses #define HINGELOSS 1 #define SMOOTHHINGELOSS 2 #define SQUAREDHINGELOSS 3 #define LOGLOSS 10 #define LOGLOSSMARGIN 11 // Select loss #define LOSS SQUAREDHINGELOSS inline double loss(double z) { #if LOSS == LOGLOSS if (z >= 0) return log(1+exp(-z)); else return -z + log(1+exp(z)); #elif LOSS == LOGLOSSMARGIN if (z >= 1) return log(1+exp(1-z)); else return 1-z + log(1+exp(z-1)); #elif LOSS == SMOOTHHINGELOSS if (z < 0) return 0.5 - z; if (z < 1) return 0.5 * (1-z) * (1-z); return 0; #elif LOSS == SQUAREDHINGELOSS if (z < 1) return 0.5 * (1 - z) * (1 - z); return 0; #elif LOSS == HINGELOSS if (z < 1) return 1 - z; return 0; #else # error "Undefined loss" #endif } inline double dloss(double z) { #if LOSS == LOGLOSS if (z < 0) return 1 / (exp(z) + 1); double ez = exp(-z); return ez / (ez + 1); #elif LOSS == LOGLOSSMARGIN if (z < 1) return 1 / (exp(z-1) + 1); double ez = exp(1-z); return ez / (ez + 1); #elif LOSS == SMOOTHHINGELOSS if (z < 0) return 1; if (z < 1) return 1-z; return 0; #elif LOSS == SQUAREDHINGELOSS if (z < 1) return (1 - z); return 0; #else if (z < 1) return 1; return 0; #endif } // -- stochastic gradient class SgdQn { public: SgdQn(int dim, double lambda, double t0); double printQnInfo(const FVector &Bb, double init); void calibrate(int imin, int imax, const xvec_t &xp, const yvec_t &yp, bool verb); void train(int imin, int imax, const xvec_t &x, const yvec_t &y, const char *prefix, bool verb); void test(int imin, int imax, const xvec_t &x, const yvec_t &y, const char *prefix, bool verb, FVector &infos); FVector copy_w() {return w;} private: double t; double lambda; FVector w; double bias; int skip; int count; FVector B; FVector Bc; }; SgdQn::SgdQn(int dim, double l, double t0) : t(t0), lambda(l), w(dim), skip(1000), B(dim), Bc(dim) { for(int i=0; ibmax) bmax = Bb[i], imax=i; bmean+=Bb[i]; if(Bb[i]==init) notchg++; } for(int i=0; iskip) Bc.combine_and_clip((t-skip)/(t+skip),B,2*skip/(t+skip), 1/(100*lambda),100/lambda); else Bc.combine_and_clip(t/(t+skip),B,skip/(t+skip), 1/(100*lambda),100/lambda); B.clear(); B.resize(w.size()); } } updateB=false; } else { if(--count <= 0) { w.add(w,-skip*lambda*eta,Bc); count = skip; updateB=true; } #if LOSS < LOGLOSS if (z < 1) #endif { w.add(x, eta*dloss(z)*y, Bc); } } t += 1; } if (verb) cout << prefix << setprecision(6) << "Norm2: " << dot(w,w) << ", Bias: " << 0 << endl; } void SgdQn::test(int imin, int imax, const xvec_t &xp, const yvec_t &yp, const char *prefix, bool verb, FVector &infos) { if (verb) cout << prefix << "Testing on [" << imin << ", " << imax << "]." << endl; assert(imin <= imax); int nerr = 0; double cost = 0; for (int i=imin; i<=imax; i++) { const SVector &x = xp.at(i); double y = yp.at(i); double wx = dot(w,x); double z = y * (wx + bias); if (z <= 0) nerr += 1; #if LOSS < LOGLOSS if (z < 1) #endif cost += loss(z); } int n = imax - imin + 1; double loss = cost / n; cost = loss + 0.5 * lambda * dot(w,w); if (verb) { cout << prefix << setprecision(4) << "Misclassification: " << (double)nerr * 100.0 / n << "%." << endl; cout << prefix << setprecision(12) << "Cost: " << cost << "." << endl; cout << prefix << setprecision(12) << "Loss: " << loss << "." << endl; } infos[1]=(double)nerr/n; infos[2]=cost; } // --- options string trainfile; string testfile; string logfile; double lambda = 1e-4; double t0 = 0; int epochs = 5; int trainsize = -1; double steps=1.; void usage() { cerr << "Usage: (sparse_)svmsgdqn [options] trainfile [testfile] [logfile]" << endl << "Options:" << endl << " -lambda (default 1e-4)" << endl << " -epochs (default 5)" << endl << " -t0 : if none given (default), an automatic procedure selects one." << endl << " -trainsize " << endl << " -steps : number of intermediate values to be printed in the logfile (including a test error)." << endl << endl; exit(10); } void parse(int argc, const char **argv) { for (int i=1; i0 && lambda<1e4); } else if (opt == "t0" && i+10); } else if (opt == "epochs" && i+10 && epochs<1e6); } else if (opt == "trainsize" && i+1 0); } else if (opt == "steps" && i+1 0); } else usage(); } } if (trainfile.empty()) usage(); } // --- loading data int dim; xvec_t xtrain; yvec_t ytrain; xvec_t xtest; yvec_t ytest; ofstream logs; void load(const char *fname, xvec_t &xp, yvec_t &yp) { cout << "Loading " << fname << "." << endl; igzstream f; f.open(fname); if (! f.good()) { cerr << "ERROR: cannot open " << fname << "." << endl; exit(10); } int pcount = 0; int ncount = 0; bool binary; string suffix = fname; if (suffix.size() >= 7) suffix = suffix.substr(suffix.size() - 7); if (suffix == ".dat.gz") binary = false; else if (suffix == ".bin.gz") binary = true; else { cerr << "ERROR: filename should end with .bin.gz or .dat.gz" << endl; exit(10); } while (f.good()) { SVector x; double y; if (binary) { y = (f.get()) ? +1 : -1; x.load(f); } else { f >> y >> x; } if (f.good()) { assert(y == +1 || y == -1); xp.push_back(x); yp.push_back(y); if (y > 0) pcount += 1; else ncount += 1; if (x.size() > dim) dim = x.size(); } if (trainsize > 0 && xp.size() > (unsigned int)trainsize) break; } cout << "Read " << pcount << "+" << ncount << "=" << pcount + ncount << " examples." << endl; } void rearrange(xvec_t& xp, int dim) { cout << "Preprocessing ..." << endl; double n = xp.size(); FVector sum(dim); FVector var(dim); for(int ex=0; ex 0 && imax >= trainsize) imax = imin + trainsize -1; // load testing set if (! testfile.empty()) { load(testfile.c_str(), xtest, ytest); #if DENSE_DATA rearrange(xtest,dim); #endif } int tmin = 0; int tmax = xtest.size() - 1; // prepare svm if(t0==0) t0 = determine_t0(imin, imax, epochs); SgdQn svm(dim, lambda, t0); svm.calibrate(0, imax, xtrain, ytrain, true); if (! logfile.empty()) { logs.open(logfile.c_str()); logs << "# SVMSGDQN. lambda = " << lambda << " , t0 = " << t0 << endl; logs << "# trnsz = " << imax-imin+1 << " , tstsz = " << tmax-tmin+1 << endl; logs << "# it time trn_err trn_cost tst_err tst_cost" << endl; FVector info(2); svm.test(imin, imax, xtrain, ytrain, "train: ", true, info); logs << 0 << " " << 0 << " " << info[1] << " " << info[2]; if (tmax >= tmin) { svm.test(tmin, tmax, xtest, ytest, "test: ", true, info); if (! logfile.empty()) logs << " " << info[1] << " " << info[2]; } logs << endl; } Timer timer; if(! logfile.empty()) for(int i=0; i= tmin) { svm.test(tmin, tmax, xtest, ytest, "test: ", true, info); logs << " " << info[1] << " " << info[2]; } logs << endl; } } else for(int i=0; i= tmin) svm.test(tmin, tmax, xtest, ytest, "test: ", true, info); } } libsgdqn-1.0/svm/redo-jmlr-experiments/0000755000355101171100000000000011220435343017523 5ustar bordesmalirelibsgdqn-1.0/svm/redo-jmlr-experiments/logs/0000755000355101171100000000000011220435270020466 5ustar bordesmalirelibsgdqn-1.0/svm/redo-jmlr-experiments/figures/0000755000355101171100000000000011220435275021173 5ustar bordesmalirelibsgdqn-1.0/svm/redo-jmlr-experiments/make_jmlr_plots.plt0000644000355101171100000000760611220373220023432 0ustar bordesmalireset terminal postscript enhanced color "Times-Roman" 24 #set terminal aqua # X-AXIS: EPOCHS set xlabel "Number of epochs" # TRAIN COST #set ylabel "Primal cost" set format y "%1.2f" set yrange[0.3:0.4] set xrange[0:10] set output "figures/alpha-prim-epoch.eps" plot "logs/alpha-svmsgd2.txt" every 4 u 1:4 w lp lw 3 ps 3 title "SVMSGD2", \ "logs/alpha-svmsgdqn.txt" every 4 u 1:4 w lp lw 3 ps 3 title "SGD-QN", \ "logs/alpha-svmolbfgs.txt" every 4 u 1:4 w lp lw 3 ps 3 title "oLBFGS" set yrange[0.305:0.32] set xrange[0:7] set output "figures/delta-prim-epoch.eps" plot "logs/delta-svmsgd2.txt" every 4 u 1:4 w lp lw 3 ps 3 title "SVMSGD2", \ "logs/delta-svmsgdqn.txt" every 4 u 1:4 w lp lw 3 ps 3 title "SGD-QN", \ "logs/delta-svmolbfgs.txt" every 4 u 1:4 w lp lw 3 ps 3 title "oLBFGS" set yrange[0.12:0.15] set xrange[0:1] set output "figures/reuters-prim-epoch.eps" plot "logs/rcv1-svmsgd2.txt" every 1 u 1:4 w lp lw 3 ps 3 title "SVMSGD2", \ "logs/rcv1-svmsgdqn.txt" every 1 u 1:4 w lp lw 3 ps 3 title "SGD-QN" # TEST ERROR (%) #set ylabel "Test Error (%)" set format y "%2.1f" set yrange[21:27] set xrange[0:10] set output "figures/alpha-test-epoch.eps" plot "logs/alpha-svmsgd2.txt" every 4 u 1:($5*100) w lp lw 3 ps 3 title "SVMSGD2", \ "logs/alpha-svmsgdqn.txt" every 4 u 1:($5*100) w lp lw 3 ps 3 title "SGD-QN", \ "logs/alpha-svmolbfgs.txt" every 4 u 1:($5*100) w lp lw 3 ps 3 title "oLBFGS" set yrange[21:25] set xrange[0:5] set output "figures/delta-test-epoch.eps" plot "logs/delta-svmsgd2.txt" every 3 u 1:($5*100) w lp lw 3 ps 3 title "SVMSGD2", \ "logs/delta-svmsgdqn.txt" every 3 u 1:($5*100) w lp lw 3 ps 3 title "SGD-QN", \ "logs/delta-svmolbfgs.txt" every 3 u 1:($5*100) w lp lw 3 ps 3 title "oLBFGS" set yrange[5.6:7] set xrange[0:2] set output "figures/reuters-test-epoch.eps" plot "logs/rcv1-svmsgd2.txt" every 1 u 1:($5*100) w lp lw 3 ps 3 title "SVMSGD2", \ "logs/rcv1-svmsgdqn.txt" every 1 u 1:($5*100) w lp lw 3 ps 3 title "SGD-QN #---------------------------- # X-AXIS: TIME set xlabel "Training time (sec.)" # TRAIN COST #set ylabel "Primal cost" set format y "%1.2f" set xrange[0:2] set yrange[0.3:0.4] set output "figures/alpha-prim-time.eps" plot "logs/alpha-svmsgd2.txt" every 4 u 2:4 w lp lw 3 ps 3 title "SVMSGD2", \ "logs/alpha-svmsgdqn.txt" every 8 u 2:4 w lp lw 3 ps 3 title "SGD-QN", \ "logs/alpha-svmolbfgs.txt" every 2 u 2:4 w lp lw 3 ps 3 title "oLBFGS" set xrange[0:2] set yrange[0.305:0.32] set output "figures/delta-prim-time.eps" plot "logs/delta-svmsgd2.txt" every 3 u 2:4 w lp lw 3 ps 3 title "SVMSGD2", \ "logs/delta-svmsgdqn.txt" every 3 u 2:4 w lp lw 3 ps 3 title "SGD-QN", \ "logs/delta-svmolbfgs.txt" u 2:4 w lp lw 3 ps 3 title "oLBFGS" set xrange[0:0.5] set yrange[0.12:0.15] set output "figures/reuters-prim-time.eps" plot "logs/rcv1-svmsgd2.txt" every 1 u 2:4 w lp lw 3 ps 3 title "SVMSGD2", \ "logs/rcv1-svmsgdqn.txt" every 1 u 2:4 w lp lw 3 ps 3 title "SGD-QN" # TEST ERROR #set ylabel "Test error(%)" set format y "%2.1f" set xrange[0:2] set yrange[21:27] set output "figures/alpha-test-time.eps" plot "logs/alpha-svmsgd2.txt" every 4 u 2:($5*100) w lp lw 3 ps 3 title "SVMSGD2", \ "logs/alpha-svmsgdqn.txt" every 8 u 2:($5*100) w lp lw 3 ps 3 title "SGD-QN", \ "logs/alpha-svmolbfgs.txt" every 2 u 2:($5*100) w lp lw 3 ps 3 title "oLBFGS" set xrange[0:1] set yrange[21:25] set output "figures/delta-test-time.eps" plot "logs/delta-svmsgd2.txt" every 3 u 2:($5*100) w lp lw 3 ps 3 title "SVMSGD2", \ "logs/delta-svmsgdqn.txt" every 3 u 2:($5*100) w lp lw 3 ps 3 title "SGD-QN", \ "logs/delta-svmolbfgs.txt" u 2:($5*100) w lp lw 3 ps 3 title "oLBFGS" set xrange[0:1] set yrange[5.6:7] set output "figures/reuters-test-time.eps" plot "logs/rcv1-svmsgd2.txt" every 1 u 2:($5*100) w lp lw 3 ps 3 title "SVMSGD2", \ "logs/rcv1-svmsgdqn.txt" every 1 u 2:($5*100) w lp lw 3 ps 3 title "SGD-QN" libsgdqn-1.0/svm/redo-jmlr-experiments/run_exp.sh0000755000355101171100000000276311220434731021552 0ustar bordesmalire#!/bin/sh # Experiments on Alpha (dense dataset) ../svmsgd2 -lambda 1e-5 -steps 10 -epochs 100 ../../data/PASCAL/alpha-train100000.dat.gz ../../data/PASCAL/alpha-test50000.dat.gz logs/alpha-svmsgd2.txt ../svmsgdqn -lambda 1e-5 -steps 10 -epochs 50 -t0 1e6 ../../data/PASCAL/alpha-train100000.dat.gz ../../data/PASCAL/alpha-test50000.dat.gz logs/alpha-svmsgdqn.txt ../svmolbfgs -lambda 1e-5 -steps 10 -epochs 50 ../../data/PASCAL/alpha-train100000.dat.gz ../../data/PASCAL/alpha-test50000.dat.gz logs/alpha-svmolbfgs.txt # Experiments on Delta (dense dataset) ../svmsgd2 -lambda 1e-4 -steps 10 -epochs 100 ../../data/PASCAL/delta-train100000.dat.gz ../../data/PASCAL/delta-test50000.dat.gz logs/delta-svmsgd2.txt ../svmsgdqn -lambda 1e-4 -steps 10 -epochs 50 -t0 1e4 ../../data/PASCAL/delta-train100000.dat.gz ../../data/PASCAL/delta-test50000.dat.gz logs/delta-svmsgdqn.txt ../svmolbfgs -lambda 1e-4 -steps 10 -epochs 50 ../../data/PASCAL/delta-train100000.dat.gz ../../data/PASCAL/delta-test50000.dat.gz logs/delta-svmolbfgs.txt # Experiments on RCV1 (sparse dataset) ../sparse_svmsgd2 -lambda 1e-4 -steps 10 -epochs 50 ../../data/rcv1/train.dat.gz ../../data/rcv1/test.dat.gz logs/rcv1-svmsgd2.txt ../sparse_svmsgdqn -lambda 1e-4 -steps 10 -epochs 50 -t0 1e5 ../../data/rcv1/train.dat.gz ../../data/rcv1/test.dat.gz logs/rcv1-svmsgdqn.txt # svmobfgs does not scale on rcv1. # Generate the curves of the JMLR paper gnuplot make_jmlr_plots.plt # Compile the latex source latex figures.tex dvipdf figures.dvi libsgdqn-1.0/svm/redo-jmlr-experiments/figures.tex0000644000355101171100000000422711217733663021732 0ustar bordesmalire\documentclass{article} \usepackage[english]{babel} \usepackage[latin1]{inputenc} \usepackage[T1]{fontenc} \usepackage{graphicx} \usepackage{epsf} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{booktabs} \begin{document} \begin{table} \begin{center} \caption{Datasets and parameters used for experiments.} \label{tab:datasets} \begin{tabular}{l|cccc|ccc} \toprule Dataset & Train. Ex. & Test. Ex. & Features & $s$ & $\lambda$ & $t_0$ & $skip$ \\ \midrule {\sc Alpha} & 100,000 & 50,000 & 500 & $1$ & $10^{-5}$ & $10^6$ & 16 \\ {\sc Delta} & 100,000 & 50,000 & 500 & $1$ & $10^{-4}$ & $10^4$ & 16 \\ {\sc RCV1} & 781,265 & 23,149 & 47,152 & $0.0016$ & $10^{-4}$ & $10^5$ & 9,965 \\ \bottomrule \end{tabular} \end{center} \end{table} \begin{figure} \begin{center} \def\bs{\!\!\!\!\!\!\!\!\!\!} \begin{tabular}{@{\bs}c@{\bs}c} \includegraphics[angle=270,width=.55\linewidth]{figures/alpha-prim-epoch} & \includegraphics[angle=270,width=.55\linewidth]{figures/alpha-prim-time}\\ \end{tabular} \caption{Primal costs according to the number of epochs (left) and the training duration (right) on the Alpha dataset.} \end{center} \end{figure} \begin{figure} \begin{center} \def\bs{\!\!\!\!\!\!\!\!\!\!} \begin{tabular}{@{\bs}c@{\bs}c} \includegraphics[angle=270,width=.55\linewidth]{figures/alpha-test-epoch} & \includegraphics[angle=270,width=.55\linewidth]{figures/alpha-test-time} \\ \multicolumn{2}{c}{\sc Alpha dataset}\\ \includegraphics[angle=270,width=.55\linewidth]{figures/delta-test-epoch} & \includegraphics[angle=270,width=.55\linewidth]{figures/delta-test-time} \\ \multicolumn{2}{c}{\sc Delta dataset}\\ \includegraphics[angle=270, width=.55\linewidth]{figures/reuters-test-epoch} & \includegraphics[angle=270, width=.55\linewidth]{figures/reuters-test-time} \\ \multicolumn{2}{c}{\sc RCV1 dataset}\\ \end{tabular} \caption{Test errors (in \%) according to the number of epochs (left) and training duration (right).} \label{fig:errors} \end{center} \end{figure} \end{document} libsgdqn-1.0/svm/svmolbfgs.cpp0000644000355101171100000003236611220371636016013 0ustar bordesmalire// -*- C++ -*- // oLBFGS // Copyright (C) 2008- Antoine Bordes // Algorithm published in "A Stochastic Quasi-Newton Method for Online Convex Optimization" // by N. Schraudolph, J. Yu and S. Gunter in Proceedings of AISTATS 2007 // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either // version 2.1 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA #include "vectors.h" #include "gzstream.h" #include "timer.h" #include #include #include #include #include #include #include #include #include #include #ifndef DENSE_DATA // set this value to 1 if you are not using sparse data # define DENSE_DATA 1 #endif #if DENSE_DATA #define SVector FVector #endif using namespace std; typedef vector xvec_t; typedef vector yvec_t; // Available losses #define HINGELOSS 1 #define SMOOTHHINGELOSS 2 #define SQUAREDHINGELOSS 3 #define LOGLOSS 10 #define LOGLOSSMARGIN 11 // Select loss #define LOSS SQUAREDHINGELOSS inline double loss(double z) { #if LOSS == LOGLOSS if (z >= 0) return log(1+exp(-z)); else return -z + log(1+exp(z)); #elif LOSS == LOGLOSSMARGIN if (z >= 1) return log(1+exp(1-z)); else return 1-z + log(1+exp(z-1)); #elif LOSS == SMOOTHHINGELOSS if (z < 0) return 0.5 - z; if (z < 1) return 0.5 * (1-z) * (1-z); return 0; #elif LOSS == SQUAREDHINGELOSS if (z < 1) return 0.5 * (1 - z) * (1 - z); return 0; #elif LOSS == HINGELOSS if (z < 1) return 1 - z; return 0; #else # error "Undefined loss" #endif } inline double dloss(double z) { #if LOSS == LOGLOSS if (z < 0) return 1 / (exp(z) + 1); double ez = exp(-z); return ez / (ez + 1); #elif LOSS == LOGLOSSMARGIN if (z < 1) return 1 / (exp(z-1) + 1); double ez = exp(1-z); return ez / (ez + 1); #elif LOSS == SMOOTHHINGELOSS if (z < 0) return 1; if (z < 1) return 1-z; return 0; #elif LOSS == SQUAREDHINGELOSS if (z < 1) return (1 - z); return 0; #else if (z < 1) return 1; return 0; #endif } // -- stochastic gradient class olbfgs { public: olbfgs(int dim, double lambda); void calibrate(int imin, int imax, const xvec_t &xp, const yvec_t &yp); void train(int imin, int imax, const xvec_t &x, const yvec_t &y, const char *prefix); void test(int imin, int imax, const xvec_t &x, const yvec_t &y, const char *prefix, FVector &infos); private: double t; double lambda; FVector w; double bias; int skip; int count; double t0; double m; vector ss; vector ys; double sum_i; int i_1; }; olbfgs::olbfgs(int dim, double l) : t(0), lambda(l), w(dim), skip(1000), sum_i(0), i_1(0) { double maxw = 1.0 / sqrt(lambda); double typw = sqrt(maxw); double eta0 = typw / max(1.0,dloss(-typw)); t0 = 1 / (eta0 * lambda); m = 1.; } void olbfgs::calibrate(int imin, int imax, const xvec_t &xp, const yvec_t &yp) { cout << "Estimating sparsity" << endl; int j; // compute average gradient size double n = 0; double r = 0; #if DENSE_DATA for (j=imin; j<=imax; j++,n++) { const FVector &x = xp.at(j); n += 1; r += x.size(); } #else for (j=imin; j<=imax; j++,n++) { const SVector &x = xp.at(j); n += 1; r += x.npairs(); } #endif // compute weight decay skip skip = (int) ((8 * n * w.size()) / r); cout << " using " << n << " examples." << endl; cout << " skip: " << skip << endl; } void olbfgs::train(int imin, int imax, const xvec_t &xp, const yvec_t &yp, const char *prefix) { cout << prefix << "Training on [" << imin << ", " << imax << "]." << endl; assert(imin <= imax); count = 0; for (int i=imin; i<=imax; i++) { const SVector &x = xp.at(i); double y = yp.at(i); double z = y * dot(w, x); double old_loss = dloss(z); FVector pt = combine(w,-lambda,x,old_loss*y); // 3 (1) vector alphas; alphas.resize((int)min(m,t)); for (int ii=0; ii0) // 3 (3) pt.scale(sum_i/min(m,t)); else pt.scale(0.0001); for (int ii=0; ii=(int)min(t,m)) idx-=(int)min(t,m); double beta = dot(ys[idx],pt) / dot(ys[idx],ss[idx]); pt.add(ss[idx],(alphas[idx]-beta)); } pt.scale(0.1*(t0/lambda)/(t+t0)); // pt -> st (c) w.add(pt);//(d) double z2 = y * dot(w,x); double diffloss = dloss(z2) - old_loss; FVector yt = combine(pt,(lambda+t0),x, -y*diffloss); // (e) if(t=m) idx-=(int)m; sum_i += dot(pt,yt)/dot(yt,yt) - dot(ss[idx],ys[idx])/dot(ys[idx],ys[idx]); ys[idx]=yt; ss[idx]=pt; i_1=idx; } t += 1;//(i) } cout << prefix << setprecision(6) << "Norm2: " << dot(w,w) << ", Bias: " << 0 << endl; } void olbfgs::test(int imin, int imax, const xvec_t &xp, const yvec_t &yp, const char *prefix, FVector &infos) { cout << prefix << "Testing on [" << imin << ", " << imax << "]." << endl; assert(imin <= imax); int nerr = 0; double cost = 0; for (int i=imin; i<=imax; i++) { const SVector &x = xp.at(i); double y = yp.at(i); double wx = dot(w,x); double z = y * (wx + bias); if (z <= 0) nerr += 1; #if LOSS < LOGLOSS if (z < 1) #endif cost += loss(z); } int n = imax - imin + 1; double loss = cost / n; cost = loss + 0.5 * lambda * dot(w,w); cout << prefix << setprecision(4) << "Misclassification: " << (double)nerr * 100.0 / n << "%." << endl; cout << prefix << setprecision(12) << "Cost: " << cost << "." << endl; cout << prefix << setprecision(12) << "Loss: " << loss << "." << endl; infos[1]=(double)nerr/n; infos[2]=cost; } // --- options string trainfile; string testfile; string logfile; double lambda = 1e-4; int epochs = 5; int trainsize = -1; double steps = 1.; void usage() { cerr << "Usage: (sparse_)svmolbfgs [options] trainfile [testfile] [logfile]" << endl << "Options:" << endl << " -lambda " << endl << " -epochs " << endl << " -trainsize " << endl << " -steps : number of intermediate values to be printed in the logfile (including a test error)." << endl << endl; exit(10); } void parse(int argc, const char **argv) { for (int i=1; i0 && lambda<1e4); } else if (opt == "epochs" && i+10 && epochs<1e6); } else if (opt == "trainsize" && i+1 0); } else if (opt == "steps" && i+1 0); } else usage(); } } if (trainfile.empty()) usage(); } // --- loading data int dim; xvec_t xtrain; yvec_t ytrain; xvec_t xtest; yvec_t ytest; ofstream logs; void load(const char *fname, xvec_t &xp, yvec_t &yp) { cout << "Loading " << fname << "." << endl; igzstream f; f.open(fname); if (! f.good()) { cerr << "ERROR: cannot open " << fname << "." << endl; exit(10); } int pcount = 0; int ncount = 0; bool binary; string suffix = fname; if (suffix.size() >= 7) suffix = suffix.substr(suffix.size() - 7); if (suffix == ".dat.gz") binary = false; else if (suffix == ".bin.gz") binary = true; else { cerr << "ERROR: filename should end with .bin.gz or .dat.gz" << endl; exit(10); } while (f.good()) { SVector x; double y; if (binary) { y = (f.get()) ? +1 : -1; x.load(f); } else { f >> y >> x; } if (f.good()) { assert(y == +1 || y == -1); xp.push_back(x); yp.push_back(y); if (y > 0) pcount += 1; else ncount += 1; if (x.size() > dim) dim = x.size(); } if (trainsize > 0 && xp.size() > (unsigned int)trainsize) break; } cout << "Read " << pcount << "+" << ncount << "=" << pcount + ncount << " examples." << endl; } void rearrange(xvec_t& xp, int dim) { double n = xp.size(); FVector sum(dim); FVector var(dim); for(int ex=0; ex 0 && imax >= trainsize) imax = imin + trainsize -1; // prepare svm olbfgs svm(dim, lambda); // load testing set if (! testfile.empty()) { load(testfile.c_str(), xtest, ytest); #if DENSE_DATA rearrange(xtest, dim); #endif } int tmin = 0; int tmax = xtest.size() - 1; svm.calibrate(imin, imax, xtrain, ytrain); if (! logfile.empty()) { logs.open(logfile.c_str()); logs << "# OLBFGS. lambda = " << lambda << endl; logs << "# trnsz = " << imax-imin+1 << " , tstsz = " << tmax-tmin+1 << endl; logs << "# it time trn_err trn_cost tst_err tst_cost" << endl; FVector info(2); svm.test(imin, imax, xtrain, ytrain, "train: ",info); logs << 0 << " " << 0 << " " << info[1] << " " << info[2]; if (tmax >= tmin) { svm.test(tmin, tmax, xtest, ytest, "test: ", info); logs << " " << info[1] << " " << info[2]; } logs << endl; } Timer timer; if(! logfile.empty()) for(int i=0; i= tmin) { svm.test(tmin, tmax, xtest, ytest, "test: ", info); if (! logfile.empty()) logs << " " << info[1] << " " << info[2]; } if (! logfile.empty()) logs << endl; } } else for(int i=0; i= tmin) { svm.test(tmin, tmax, xtest, ytest, "test: ",info); } } } libsgdqn-1.0/data/0000755000355101171100000000000011220402155013366 5ustar bordesmalirelibsgdqn-1.0/data/rcv1/0000755000355101171100000000000011220435222014242 5ustar bordesmalirelibsgdqn-1.0/data/PASCAL/0000755000355101171100000000000011220435212014331 5ustar bordesmalirelibsgdqn-1.0/data/get_data.sh0000777000355101171100000000057211220176765015524 0ustar bordesmalire#!/bin/sh # Download and unpack Alpha & Delta cd PASCAL/ wget -c http://webia.lip6.fr/~bordes/datasets/binary/alpha.tar.gz tar -zxvf alpha.tar.gz wget -c http://webia.lip6.fr/~bordes/datasets/binary/delta.tar.gz tar -zxvf delta.tar.gz # Download and unpack RCV1 cd ../rcv1/ wget -c http://webia.lip6.fr/~bordes/datasets/binary/rcv1.tar.gz tar -zxvf rcv1.tar.gz cd .. libsgdqn-1.0/README0000644000355101171100000001111211220435114013332 0ustar bordesmalire ************** ** LIBSGDQN ** ************** Libsgdqn is library proposing an implementation of the novel algorithm SGD-QN: a carefully designed and implemented quasi-Newton stochastic gradient descent solver for linear SVMs. ************** ** TABLE OF CONTENTS: * Overview of the library * Implemented algorithms * How-to use * RE-run JMLR experiments * Copyright ************** ** OVERVIEW: The SGD-QN algorithm is a stochastic gradient descent algorithm that makes careful use of second order information and splits the parameter update into independently scheduled components. Thanks to this design, SGD-QN iterates nearly as fast as a first order stochastic gradient descent but requires less iterations to achieve the same accuracy. This algorithm is extensively described in the paper: "SGD-QN: Careful Quasi-Newton Stochastic Gradient Descent" by A. Bordes, L. Bottou and P. Gallinari published in Journal of Machine Learning Research: Special Topic on Large Scale Learning (2009). Along with SGD-QN, this library proposes the implementation of two other online solvers for linear SVMs (also discussed in the JMLR paper). A script to re-run the experiments of this paper is also provided. ************** ** ALGORITHMS: The library contains the three following implementations: * SVMSGDQN: The new quasi-newton stochastic gradient proposed in the JMLR paper cited above. * SVMSGD2: An implementation of the plain stochastic gradient proposed by Leon Bottou in 2007 (see http://leon.bottou.org/projects/sgd for details). * SVMOLBFGS: An online version of the well-known LBFGS optimizer proposed by Schraudolph et al. in "A Stochastic Quasi-Newton Method for Online Convex Optimization" in the proceedings of AISTATS 2007. ************** ** HOW-TO USE: All three algorithms are implemented in C++ and does not require any additional library. Their codes are in the 'libsgdqn/svm/' directory. * Compilation: (1) cd to 'libsgdqn/svm/' and (2) simply type make. * Binaries: the compilation produces 2 binaries for each algorithm. A version for dense data and a version handling sparse data (with the prefix 'sparse_'). * Command line: typing the command with no argument print a short help. The binaries can take up to 3 files as arguments: - trainfile (required): the training set in LibSVM/SVMlight format. - testfile (optional): the test set in the same format. - logfile (optional): a file in which are written intermediate values of train time, train cost, train error, test cost and test error. * Input file format: training and testing sets must be in LibSVM/SVMLight format and gziped. ************** ** RE-RUN JMLR EXPERIMENTS: (require gnuplot and latex) Two scripts allows to re-run the experiments of the JMLR paper and produce a pdf file with the corresponding figures. Simply follow the four steps: (1) cd to 'libsgdqn/svm/' and type make to build the binaries. (2) cd to 'libsgdqn/data/' and run the 'get_data.sh' shell script (might need to change the mode of the script). It will download and unpack the datasets used in the paper (Alpha, Delta and RCV1). Each dataset is ~400MB. (3) cd to 'libsgdqn/svm/redo-jmlr-experiments/' and run the 'run_exp.sh' shell script (might need to change the mode of the script).The whole script execution can take from 30min to more than an hour due to the multiple dataset loading times which have not been optimized. The script 'run_exp.sh' successively: (a) runs svmsgd2, svmsgdqn and svmolbfgs on Alpha, Delta and RCV1 with the parameters of the JMLR paper. (b) writes the logs of these experiments in the 'libsgdqn/svm/redo-jmlr-experiments/logs/' directory. (c) runs the gnuplot script 'make_jmlr_figures.plt' to produce figures and stores them in 'libsgdqn/svm/redo-jmlr-experiments/figures'. (Note: the 'training time' x scale might need to be modified according to the CPU: see in 'make_jmlr_figures.plt'.) (d) compiles the 'figures.tex' latex file to generate the 2-pages pdf document 'figures.pdf' which displays the figures. (4) The figures of the JMLR paper are displayed in figures.pdf (in the 'libsgdqn/svm/redo-jmlr-experiments/' directory). Note: the script 'run_exp.sh' also proposes example command lines on how to use the binaries of the three algorithms. ************** ** COPYRIGHT: Copyright (C) 2007/2009 - Antoine Bordes and Leon Bottou. This library is distributed under GNU General Public License (see COPYING for details). For any questions and comments, please send your email to antoine.bordes@lip6.fr. libsgdqn-1.0/COPYING0000644000355101171100000001672711217675334013546 0ustar bordesmalire GNU LESSER GENERAL PUBLIC LICENSE Version 3, 29 June 2007 Copyright (C) 2007 Free Software Foundation, Inc. Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. This version of the GNU Lesser General Public License incorporates the terms and conditions of version 3 of the GNU General Public License, supplemented by the additional permissions listed below. 0. Additional Definitions. As used herein, "this License" refers to version 3 of the GNU Lesser General Public License, and the "GNU GPL" refers to version 3 of the GNU General Public License. "The Library" refers to a covered work governed by this License, other than an Application or a Combined Work as defined below. An "Application" is any work that makes use of an interface provided by the Library, but which is not otherwise based on the Library. Defining a subclass of a class defined by the Library is deemed a mode of using an interface provided by the Library. A "Combined Work" is a work produced by combining or linking an Application with the Library. The particular version of the Library with which the Combined Work was made is also called the "Linked Version". The "Minimal Corresponding Source" for a Combined Work means the Corresponding Source for the Combined Work, excluding any source code for portions of the Combined Work that, considered in isolation, are based on the Application, and not on the Linked Version. The "Corresponding Application Code" for a Combined Work means the object code and/or source code for the Application, including any data and utility programs needed for reproducing the Combined Work from the Application, but excluding the System Libraries of the Combined Work. 1. Exception to Section 3 of the GNU GPL. You may convey a covered work under sections 3 and 4 of this License without being bound by section 3 of the GNU GPL. 2. Conveying Modified Versions. If you modify a copy of the Library, and, in your modifications, a facility refers to a function or data to be supplied by an Application that uses the facility (other than as an argument passed when the facility is invoked), then you may convey a copy of the modified version: a) under this License, provided that you make a good faith effort to ensure that, in the event an Application does not supply the function or data, the facility still operates, and performs whatever part of its purpose remains meaningful, or b) under the GNU GPL, with none of the additional permissions of this License applicable to that copy. 3. Object Code Incorporating Material from Library Header Files. The object code form of an Application may incorporate material from a header file that is part of the Library. You may convey such object code under terms of your choice, provided that, if the incorporated material is not limited to numerical parameters, data structure layouts and accessors, or small macros, inline functions and templates (ten or fewer lines in length), you do both of the following: a) Give prominent notice with each copy of the object code that the Library is used in it and that the Library and its use are covered by this License. b) Accompany the object code with a copy of the GNU GPL and this license document. 4. Combined Works. You may convey a Combined Work under terms of your choice that, taken together, effectively do not restrict modification of the portions of the Library contained in the Combined Work and reverse engineering for debugging such modifications, if you also do each of the following: a) Give prominent notice with each copy of the Combined Work that the Library is used in it and that the Library and its use are covered by this License. b) Accompany the Combined Work with a copy of the GNU GPL and this license document. c) For a Combined Work that displays copyright notices during execution, include the copyright notice for the Library among these notices, as well as a reference directing the user to the copies of the GNU GPL and this license document. d) Do one of the following: 0) Convey the Minimal Corresponding Source under the terms of this License, and the Corresponding Application Code in a form suitable for, and under terms that permit, the user to recombine or relink the Application with a modified version of the Linked Version to produce a modified Combined Work, in the manner specified by section 6 of the GNU GPL for conveying Corresponding Source. 1) Use a suitable shared library mechanism for linking with the Library. A suitable mechanism is one that (a) uses at run time a copy of the Library already present on the user's computer system, and (b) will operate properly with a modified version of the Library that is interface-compatible with the Linked Version. e) Provide Installation Information, but only if you would otherwise be required to provide such information under section 6 of the GNU GPL, and only to the extent that such information is necessary to install and execute a modified version of the Combined Work produced by recombining or relinking the Application with a modified version of the Linked Version. (If you use option 4d0, the Installation Information must accompany the Minimal Corresponding Source and Corresponding Application Code. If you use option 4d1, you must provide the Installation Information in the manner specified by section 6 of the GNU GPL for conveying Corresponding Source.) 5. Combined Libraries. You may place library facilities that are a work based on the Library side by side in a single library together with other library facilities that are not Applications and are not covered by this License, and convey such a combined library under terms of your choice, if you do both of the following: a) Accompany the combined library with a copy of the same work based on the Library, uncombined with any other library facilities, conveyed under the terms of this License. b) Give prominent notice with the combined library that part of it is a work based on the Library, and explaining where to find the accompanying uncombined form of the same work. 6. Revised Versions of the GNU Lesser General Public License. The Free Software Foundation may publish revised and/or new versions of the GNU Lesser General Public License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. Each version is given a distinguishing version number. If the Library as you received it specifies that a certain numbered version of the GNU Lesser General Public License "or any later version" applies to it, you have the option of following the terms and conditions either of that published version or of any later version published by the Free Software Foundation. If the Library as you received it does not specify a version number of the GNU Lesser General Public License, you may choose any version of the GNU Lesser General Public License ever published by the Free Software Foundation. If the Library as you received it specifies that a proxy can decide whether future versions of the GNU Lesser General Public License shall apply, that proxy's public statement of acceptance of any version is permanent authorization for you to choose that version for the Library.