vowpal_wabbit/0000755006612600001440000000000010723351526012256 5ustar jlusersvowpal_wabbit/hash.cc0000644006612600001440000000714610723351477013525 0ustar jlusers#include "hash.h" #define hashsize(n) ((ub4)1<<(n)) #define hashmask(n) (hashsize(n)-1) // This codes is public domain according to: http://burtleburtle.net/bob/hash/doobs.html /* mix -- mix 3 32-bit values reversibly. For every delta with one or two bits set, and the deltas of all three high bits or all three low bits, whether the original value of a,b,c is almost all zero or is uniformly distributed, * If mix() is run forward or backward, at least 32 bits in a,b,c have at least 1/4 probability of changing. * If mix() is run forward, every bit of c will change between 1/3 and 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.) mix() takes 36 machine instructions, but only 18 cycles on a superscalar machine (like a Pentium or a Sparc). No faster mixer seems to work, that's the result of my brute-force search. There were about 2^68 hashes to choose from. I only tested about a billion of those. */ #define mix(a,b,c) \ { \ a -= b; a -= c; a ^= (c>>13); \ b -= c; b -= a; b ^= (a<<8); \ c -= a; c -= b; c ^= (b>>13); \ a -= b; a -= c; a ^= (c>>12); \ b -= c; b -= a; b ^= (a<<16); \ c -= a; c -= b; c ^= (b>>5); \ a -= b; a -= c; a ^= (c>>3); \ b -= c; b -= a; b ^= (a<<10); \ c -= a; c -= b; c ^= (b>>15); \ } /* hash() -- hash a variable-length key into a 32-bit value k : the key (the unaligned variable-length array of bytes) len : the length of the key, counting by bytes initval : can be any 4-byte value Returns a 32-bit value. Every bit of the key affects every bit of the return value. Every 1-bit and 2-bit delta achieves avalanche. About 6*len+35 instructions. The best hash table sizes are powers of 2. There is no need to do mod a prime (mod is sooo slow!). If you need less than 32 bits, use a bitmask. For example, if you need only 10 bits, do h = (h & hashmask(10)); In which case, the hash table should have hashsize(10) elements. If you are hashing n strings (ub1 **)k, do it like this: for (i=0, h=0; i= 12) { a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24)); b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24)); c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24)); mix(a,b,c); k += 12; len -= 12; } /*------------------------------------- handle the last 11 bytes */ c += length; switch(len) /* all the case statements fall through */ { case 11: c+=((ub4)k[10]<<24); case 10: c+=((ub4)k[9]<<16); case 9 : c+=((ub4)k[8]<<8); /* the first byte of c is reserved for the length */ case 8 : b+=((ub4)k[7]<<24); case 7 : b+=((ub4)k[6]<<16); case 6 : b+=((ub4)k[5]<<8); case 5 : b+=k[4]; case 4 : a+=((ub4)k[3]<<24); case 3 : a+=((ub4)k[2]<<16); case 2 : a+=((ub4)k[1]<<8); case 1 : a+=k[0]; /* case 0: nothing left to add */ } mix(a,b,c); /*-------------------------------------------- report the result */ return c; } vowpal_wabbit/hash.h0000644006612600001440000000016010723351477013354 0ustar jluserstypedef unsigned long int ub4; typedef unsigned char ub1; ub4 hash(ub1* k,ub4 length,ub4 initval); vowpal_wabbit/parse_example.cc0000644006612600001440000002601610723351477015424 0ustar jlusers/* Copyright (c) 2007 Yahoo! Inc. All rights reserved. The copyrights embodied in the content of this file are licensed under the BSD (revised) open source license */ #include #include #include #include #include "parse_example.h" #include "hash.h" pthread_mutex_t input_mutex; void parse(char delim, substring s, v_array &ret) { char *last = s.start; for (; s.start != s.end; s.start++) { if (*s.start == delim) { if (s.start != last) { substring temp = {last,s.start}; push(ret, temp); } last = s.start+1; } } if (s.start != last) { substring final = {last, s.start}; push(ret, final); } } void unmark(bool* in_already, v_array &features) { for (feature* j =features.begin; j != features.end; j++) in_already[j->weight_index] = false; } void mark(bool* in_already, v_array &features) { for (feature* j =features.begin; j != features.end; j++) in_already[j->weight_index] = true; } inline size_t hashstring (substring s, unsigned long h) { return hash((unsigned char *)s.start, s.end - s.start, h); } inline void add_unique_index(bool *in_already, v_array &features, float v, size_t hashvalue) { size_t index = hashvalue; if (in_already[index] != true) { in_already[index] = true; feature f = {v,index}; push(features, f); } } void new_quadratic(bool *in_already, v_array &pair_features, const v_array &first_part, const v_array &second_part, size_t mask) { for (feature* i = first_part.begin; i != first_part.end; i++) { size_t halfhash = 16381 * i->weight_index; float i_value = i->x; for (feature* ele = second_part.begin; ele != second_part.end; ele++) add_unique_index(in_already, pair_features, i_value * ele->x, (halfhash + ele->weight_index) & mask); } } size_t neg_1 = 1; size_t general = 2; char* run_len_decode(char *p, size_t& i) {// read an int 7 bits at a time. size_t count = 0; while(*p & 128) i = i | ((*(p++) & 127) << 7*count++); i = i | (*(p++) << 7*count); return p; } pthread_mutex_t cache_lock; size_t int_size = 5; size_t char_size = 2; int read_cached_features(float& label, float& weight, io_buf &cache, v_array &tag, v_array* atomics, v_array &indicies) { char *p; pthread_mutex_lock(&cache_lock); size_t total = sizeof(label)+sizeof(weight)+int_size*2; size_t num_indicies = 0; size_t tag_size = 0; if (buf_read(cache, p, total) < total) goto badness; label = *(float *)p; p += sizeof(float); weight = *(float *)p; p += sizeof(float); p = run_len_decode(p, num_indicies); p = run_len_decode(p, tag_size); cache.set(p); if (buf_read(cache, p, tag_size) < tag_size) goto badness; push_many(tag, p, tag_size); for (;num_indicies > 0; num_indicies--) { size_t temp; if((temp = buf_read(cache,p,int_size + sizeof(size_t))) < char_size + sizeof(size_t)) { cerr << "truncated example! " << temp << " " << char_size +sizeof(size_t) << endl; goto badness; } size_t index = 0; p = run_len_decode(p, index); push(indicies, index); v_array* ours = atomics+index; size_t storage = *(size_t *)p; p += sizeof(size_t); cache.set(p); total += storage; if (buf_read(cache,p,storage) < storage) { cerr << "truncated example!" << endl; goto badness; } char *end = p+storage; size_t last = 0; for (;p!= end;) { feature f = {1., 0}; p = run_len_decode(p,f.weight_index); if (f.weight_index & neg_1) f.x = -1.; else if (f.weight_index & general) { f.x = *(float *)p; p += sizeof(float); } f.weight_index = last + (f.weight_index >> 2); last = f.weight_index; push(*ours, f); } cache.set(p); } pthread_mutex_unlock(&cache_lock); return total; badness: pthread_mutex_unlock(&cache_lock); return 0; } char* run_len_encode(char *p, size_t i) {// store an int 7 bits at a time. while (i >= 128) { *(p++) = (i & 127) | 128; i = i >> 7; } *(p++) = (i & 127); return p; } int order_features(const void* first, const void* second) { return ((feature*)first)->weight_index - ((feature*)second)->weight_index; } void cache_features(float label, float weight, io_buf &cache, v_array &tag, v_array* atomics, v_array &indicies) { char *p; pthread_mutex_lock(&cache_lock); buf_write(cache, p, sizeof(label)+sizeof(weight)+int_size*2+tag.index()); *(float *)p = label; p += sizeof(label); *(float *)p = weight; p += sizeof(weight); p = run_len_encode(p, indicies.index()); p = run_len_encode(p, tag.index()); memcpy(p,tag.begin,tag.index()); p += tag.index(); cache.set(p); for (size_t* b = indicies.begin; b != indicies.end; b++) { size_t storage = atomics[*b].index() * int_size; feature* end = atomics[*b].end; for (feature* i = atomics[*b].begin; i != end; i++) if (i->x != 1. && i->x != -1.) storage+=sizeof(float); buf_write(cache, p, int_size + storage + sizeof(size_t)); p = run_len_encode(p, *b); char *storage_size_loc = p; p += sizeof(size_t); qsort(atomics[*b].begin, atomics[*b].index(), sizeof(feature), order_features); size_t last = 0; for (feature* i = atomics[*b].begin; i != end; i++) { size_t diff = (i->weight_index - last) << 2; last = i->weight_index; if (i->x == 1.) p = run_len_encode(p, diff); else if (i->x == -1.) p = run_len_encode(p, diff | neg_1); else { p = run_len_encode(p, diff | general); *(float *)p = i->x; p += sizeof(float); } } cache.set(p); *(size_t*)storage_size_loc = p - storage_size_loc - sizeof(size_t); } pthread_mutex_unlock(&cache_lock); } inline float float_of_substring(substring s) { return atof(string(s.start, s.end-s.start).c_str()); } void feature_value(substring &s, v_array& name, float &v) { name.erase(); parse(':', s, name); switch (name.index()) { case 0: case 1: break; case 2: v = float_of_substring(name[1]); break; default: cerr << "example with a wierd name. What is "; cerr.write(s.start, s.end - s.start); cerr << "\n"; } } int read_features(thread_data &stuff, FILE* data, float &label, float &weight, v_array &tag, size_t mask) { pthread_mutex_lock(&input_mutex); int num_chars = getline (&stuff.line, &stuff.linesize, data); if (num_chars == -1) { pthread_mutex_unlock(&input_mutex); return num_chars; } substring page_offer = {stuff.line, stuff.line + num_chars-1}; stuff.channels.erase(); parse('|', page_offer, stuff.channels); stuff.words.erase(); parse(' ',stuff.channels[0], stuff.words); switch(stuff.words.index()) { case 0: label = FLT_MAX; break; case 1: label = float_of_substring(stuff.words[0]); weight = 1.; break; case 2: label = float_of_substring(stuff.words[0]); weight = float_of_substring(stuff.words[1]); break; case 3: label = float_of_substring(stuff.words[0]); weight = float_of_substring(stuff.words[1]); push_many(tag, stuff.words[2].start, stuff.words[2].end - stuff.words[2].start); break; default: cerr << "malformed example!\n"; } for (substring* i = stuff.channels.begin+1; i != stuff.channels.end; i++) { substring channel = *i; stuff.words.erase(); parse(' ',channel, stuff.words); if (stuff.words.begin == stuff.words.end) continue; float channel_v = 1.; feature_value(stuff.words[0], stuff.name, channel_v); size_t index = 0; bool new_index = false; if (stuff.name.index() > 0) { index = (unsigned char)*(stuff.name[0].start); if (stuff.atomics[index].begin == stuff.atomics[index].end) new_index = true; } size_t channel_hash = hashstring(stuff.name[0], 0); for (substring* i = stuff.words.begin+1; i != stuff.words.end; i++) { float v = channel_v; feature_value(*i, stuff.name, v); size_t word_hash = (hashstring(stuff.name[0], channel_hash)) & mask; add_unique_index(stuff.in_already, stuff.atomics[index], v, word_hash); } if (new_index && stuff.atomics[index].begin != stuff.atomics[index].end) push(stuff.indicies, index); } pthread_mutex_unlock(&input_mutex); return num_chars; } bool parse_example(thread_data &stuff, example_file &example_source, regressor ®, v_array &features, float &label, float &weight, v_array &tag) { features.erase(); tag.erase(); for (size_t* i = stuff.indicies.begin; i != stuff.indicies.end; i++) stuff.atomics[*i].erase(); stuff.indicies.erase(); if (example_source.cache.file == -1 || example_source.write_cache){ if (read_features(stuff, example_source.data, label, weight, tag, example_source.mask) <= 0) return false; if (example_source.write_cache) cache_features(label,weight, example_source.cache, tag, stuff.atomics, stuff.indicies); } else // use the read_cache. { if (read_cached_features(label, weight, example_source.cache, tag, stuff.atomics, stuff.indicies) <= 0) return false; } for (size_t* i = stuff.indicies.begin; i != stuff.indicies.end; i++) push_many(features, stuff.atomics[*i].begin, stuff.atomics[*i].index()); if (example_source.cache.file != -1 && !example_source.write_cache /*&& reg.pairs.size() > 0*/) mark(stuff.in_already, features); for (vector::iterator i = reg.pairs.begin(); i != reg.pairs.end();i++) new_quadratic(stuff.in_already, features, stuff.atomics[(int)(*i)[0]], stuff.atomics[(int)(*i)[1]], example_source.mask); add_unique_index(stuff.in_already, features, 1, 0);//a constant features unmark(stuff.in_already, features); return true; } bool inconsistent_cache(size_t numbits, io_buf &cache) { size_t total = sizeof(numbits); char *p; if (buf_read(cache, p, total) < total) return true; size_t cache_numbits = *(size_t *)p; if (cache_numbits != numbits) return true; return false; } void reset(size_t numbits, example_file &source) { if (source.write_cache) { source.cache.flush(); source.write_cache = false; close(source.cache.file); rename(source.cache.currentname.c_str(), source.cache.finalname.c_str()); source.cache.file = open(source.cache.finalname.c_str(), O_RDONLY|O_LARGEFILE); } if (source.cache.file != -1) { lseek(source.cache.file, 0, SEEK_SET); alloc(source.cache.space, 1 << 16); source.cache.fill(0); if (inconsistent_cache(numbits, source.cache)) { cout << "argh, a bug in caching of some sort! Exitting\n" ; exit(1); } } else fseek(source.data, 0, SEEK_SET); } void finalize_source(example_file &source) { fclose(source.data); if (source.cache.file != -1) { close(source.cache.file); free(source.cache.space.begin); } } vowpal_wabbit/stack.h0000644006612600001440000000330210723351477013537 0ustar jlusers#include /* Copyright (c) 2004 John Langford. All rights reserved. The copyrights embodied in the content of this file are licensed under the BSD (revised) open source license. */ #ifndef STACK_H__ #define STACK_H__ template class v_array{ public: T* begin; T* end; T* end_array; T last() { return *(end-1);} void decr() { end--;} v_array() { begin= NULL; end = NULL; end_array=NULL;} T& operator[](unsigned int i) { return begin[i]; } unsigned int index(){return end-begin;} void erase() { end = begin;} }; template void push(v_array& v, const T &new_ele) { if(v.end == v.end_array) { size_t old_length = v.end_array - v.begin; size_t new_length = 2 * old_length + 3; v.begin = (T *)realloc(v.begin,sizeof(T) * new_length); v.end = v.begin + old_length; v.end_array = v.begin + new_length; } *(v.end++) = new_ele; } template void push_many(v_array& v, const T* begin, size_t num) { if(v.end+num >= v.end_array) { size_t length = v.end - v.begin; size_t new_length = max(2 * (size_t)(v.end_array - v.begin) + 3, v.end - v.begin + num); v.begin = (T *)realloc(v.begin,sizeof(T) * new_length); v.end = v.begin + length; v.end_array = v.begin + new_length; } memcpy(v.end, begin, num * sizeof(T)); v.end += num; } template void alloc(v_array& v, size_t length) { v.begin = (T *)realloc(v.begin, sizeof(T) * length); v.end = v.begin; v.end_array = v.begin + length; } template v_array pop(v_array > &stack) { if (stack.end != stack.begin) return *(--stack.end); else return v_array(); } #endif // STACK_H__ vowpal_wabbit/License_stack.txt0000644006612600001440000000267510723351477015605 0ustar jlusersCopyright (c) 2004, John Langford All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. Neither the name of the TTI-Chicago nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. vowpal_wabbit/parse_regressor.h0000644006612600001440000000101310723351477015634 0ustar jlusers/* Copyright (c) 2007 Yahoo! Inc. All rights reserved. The copyrights embodied in the content of this file are licensed under the BSD (revised) open source license */ #ifndef PR_H #define PR_H #include using namespace std; typedef float weight; struct regressor { weight* weights; weight* other_weights; size_t numbits; size_t length; vector pairs; bool seg; }; void parse_regressor(vector ®ressors, regressor &r); void dump_regressor(ofstream &o, regressor &r); #endif vowpal_wabbit/License.txt0000644006612600001440000000453210723351477014412 0ustar jlusersThe copyrights to the software code for vowpal_wabbit.cc and accompanying code are licensed under the following terms: Copyright (c) 2007, Yahoo! Inc. All rights reserved. Redistribution and use of this software in source and binary forms, with or without modification, are permitted provided that the following conditions are met: * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. * Neither the name of Yahoo! Inc. nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission of Yahoo! Inc. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. vowpal_wabbit/README0000644006612600001440000000034710723351477013147 0ustar jlusersThis is the vowpal wabbit fast online learning code. It is Copyright (c) 2007 Yahoo! Inc, and released for use under the BSD (revised) open source license. Contributing authors are John Langford (Primary), Lihong Li, Alex Strehl.vowpal_wabbit/parse_regressor.cc0000644006612600001440000001004310723351477015775 0ustar jlusers/* Copyright (c) 2007 Yahoo! Inc. All rights reserved. The copyrights embodied in the content of this file are licensed under the BSD (revised) open source license */ #include #include "parse_regressor.h" void initialize_regressor(regressor &r) { r.length = 1 << r.numbits; if (r.seg) { r.weights = (weight *)malloc(r.length * sizeof(weight)); weight* end = r.weights+r.length; for (weight *v = r.weights; v != end; v++) *v = 1.; r.other_weights = (weight *)malloc(r.length * sizeof(weight)); end = r.other_weights + r.length; for (weight *v = r.other_weights; v != end; v++) *v = 1.; } else r.weights = (weight *)calloc(r.length, sizeof(weight)); } /* Read in regressors. If multiple regressors are specified, do a weighted average. If none are specified, initialize according to global_seg & numbits. */ void parse_regressor(vector ®ressors, regressor &r) { bool initialized = false; for (size_t i = 0; i < regressors.size(); i++) { ifstream regressor(regressors[i].c_str()); bool seg; regressor.read((char *)&seg, sizeof(seg)); if (!initialized) r.seg = seg; else if (seg != r.seg) { cout << "can't combine regressors from seg and gd!" << endl; exit (1); } size_t local_numbits; regressor.read((char *)&local_numbits, sizeof(local_numbits)); if (!initialized){ r.numbits = local_numbits; } else if (local_numbits != r.numbits) { cout << "can't combine regressors with different feature number!" << endl; exit (1); } int len; regressor.read((char *)&len, sizeof(len)); vector local_pairs; for (; len > 0; len--) { char pair[2]; regressor.read(pair, sizeof(char)*2); string temp(pair, 2); local_pairs.push_back(temp); } if (!initialized) { r.pairs = local_pairs; initialize_regressor(r); initialized = true; } else if (local_pairs != r.pairs) { cout << "can't combine regressors with different features!" << endl; for (size_t i = 0; i < local_pairs.size(); i++) cout << local_pairs[i] << " " << local_pairs[i].size() << " "; cout << endl; for (size_t i = 0; i < r.pairs.size(); i++) cout << r.pairs[i] << " " << r.pairs[i].size() << " "; cout << endl; exit (1); } if (!seg) while (regressor.good()) { size_t hash; regressor.read((char *)&hash, sizeof(hash)); weight w = 0.; regressor.read((char *)&w, sizeof(float)); if (regressor.good()) r.weights[hash] = r.weights[hash] + w; } else { while (regressor.good()) { size_t hash; regressor.read((char *)&hash, sizeof(hash)); weight first = 0.; regressor.read((char *)&first, sizeof(float)); weight second = 0.; regressor.read((char *)&second, sizeof(float)); if (regressor.good()) { r.weights[hash] = first; r.other_weights[hash] = second; } } } regressor.close(); } if (!initialized) initialize_regressor(r); } void dump_regressor(ofstream &o, regressor &r) { if (o.is_open()) { o.write((char *)&r.seg, sizeof(r.seg)); o.write((char *)&r.numbits, sizeof(r.numbits)); int len = r.pairs.size(); o.write((char *)&len, sizeof(len)); for (vector::iterator i = r.pairs.begin(); i != r.pairs.end();i++) o << (*i)[0] << (*i)[1]; if (!r.seg) { for(weight* v = r.weights; v != r.weights+r.length; v++) if (*v != 0.) { size_t dist = v - r.weights; o.write((char *)&(dist), sizeof (dist)); o.write((char *)v, sizeof (*v)); } } else { for(weight* v = r.weights; v != r.weights+r.length; v++) if (*v != 1.) { size_t dist = v - r.weights; o.write((char *)&(dist), sizeof (dist)); o.write((char *)v, sizeof (*v)); o.write((char *)&r.other_weights[dist], sizeof (r.other_weights[dist])); } } } if (r.seg) free(r.other_weights); free(r.weights); o.close(); } vowpal_wabbit/parse_example.h0000644006612600001440000000212410723351477015260 0ustar jlusers/* Copyright (c) 2007 Yahoo! Inc. All rights reserved. The copyrights embodied in the content of this file are licensed under the BSD (revised) open source license */ #ifndef PE_H #define PE_H #include "stack.h" #include "io.h" #include "parse_regressor.h" using namespace std; struct feature { float x; size_t weight_index; }; struct substring { char *start; char *end; }; struct thread_data { size_t linesize; char *line; v_array channels; v_array words; v_array name; v_array indicies; v_array atomics[256]; bool *in_already; }; struct example_file { FILE* data; io_buf cache; bool write_cache; size_t mask; }; // Parse a string 'page_off' to extract features and label. bool parse_example(thread_data &stuff, example_file &example_source, regressor ®, v_array &features, float &label, float &weight, v_array &tag); bool inconsistent_cache(size_t numbits, io_buf &cache); void reset(size_t numbits, example_file &source); void finalize_source(example_file &source); #endif vowpal_wabbit/io.h0000644006612600001440000000155110723351477013045 0ustar jlusers/* Copyright (c) 2007 Yahoo! Inc. All rights reserved. The copyrights embodied in the content of this file are licensed under the BSD (revised) open source license */ #ifndef IO_H__ #define IO_H__ #include #include #include "stack.h" using namespace std; class io_buf { public: v_array space; int file; string currentname; string finalname; io_buf() {alloc(space, 1 << 16); } void set(char *p){space.end = p;} void fill(int n) {alloc(space, n + read(file, space.begin+n, space.end_array - space.begin -n));} void flush() { if (write(file, space.begin, space.index()) != (int) space.index()) cerr << "error, failed to write to cache\n"; space.end = space.begin; fsync(file); } }; void buf_write(io_buf &o, char* &pointer, int n); unsigned int buf_read(io_buf &i, char* &pointer, int n); #endif vowpal_wabbit/vw.cc0000644006612600001440000002111110723351477013222 0ustar jlusers/* Copyright (c) 2007 Yahoo! Inc. All rights reserved. The copyrights embodied in the content of this file are licensed under the BSD (revised) open source license */ #include #include #include #include #include #include "parse_regressor.h" #include "parse_example.h" #include "parse_args.h" pthread_mutex_t weight_lock; float eta = 0.1; float t = 1.; float power_t = 0.; ofstream predictions; ofstream raw_predictions; bool training = true; float dump_interval = exp(1.); double sum_loss = 0.0; double sum_loss_since_last_dump = 0.0; long long int example_number = 0; double weighted_examples = 0.; double old_weighted_examples = 0.; double weighted_labels = 0.; regressor regressor; example_file source; ofstream final_regressor; inline float final_prediction(float ret) { if (isnan(ret)) return 0.5; if ( ret > 1.0 ) return 1.0; if (ret < 0.0) return 0.0; return ret; } float vector_sum(const v_array &features, weight* w) { float sum = 0.0; for (feature* ele = features.begin; ele != features.end; ele++) sum += w[ele->weight_index]; return sum; } float seg_predict(v_array &features, float &neg_weight_sum, float &pos_weight_sum, float &raw_prediction) { pos_weight_sum = vector_sum(features, regressor.weights); neg_weight_sum = vector_sum(features, regressor.other_weights); raw_prediction = pos_weight_sum; if (fpclassify(neg_weight_sum) == FP_ZERO) return 0.5; else return final_prediction(pos_weight_sum / (neg_weight_sum+pos_weight_sum)); } void vector_multiply(const v_array &features, weight *w, const float update) { for (feature* ele = features.begin; ele != features.end; ele++) w[ele->weight_index] *= update; } void seg_train(v_array &features, float neg_weight_update, float pos_weight_update) { vector_multiply(features, regressor.weights, pos_weight_update); vector_multiply(features, regressor.other_weights, neg_weight_update); } float predict(const v_array &features, float &norm, float & raw_prediction) { float prediction = 0.0; weight *weights = regressor.weights; for (feature* j = features.begin; j != features.end; j++) prediction += weights[j->weight_index] * j->x; if (features.end - features.begin > 0) norm = 1. / sqrtf(features.end - features.begin); else norm = 1.; raw_prediction = prediction; prediction *= norm; return final_prediction(prediction); } void train(const v_array &features, float update) { if (fabs(update) > 0.) { weight* weights = regressor.weights; for (feature* j = features.begin; j != features.end; j++) weights[j->weight_index] += update * j->x; } } void* go(void *in) { thread_data td; td.line = NULL; td.linesize = 0; td.in_already = (bool*)calloc(regressor.length, sizeof(bool)); v_array features; v_array tag; float label; float weight; while ( parse_example(td, source, regressor, features, label, weight, tag)) { if (features.end == features.begin) { cout << "You have an example with no features. Skipping.\n"; continue; } pthread_mutex_lock(&weight_lock); float norm = 0.; float neg_weight_sum = 0.; float prediction; float raw_prediction; if (regressor.seg) prediction = seg_predict(features,neg_weight_sum, norm,raw_prediction); else prediction = predict(features,norm,raw_prediction); example_number++; weighted_examples += weight; weighted_labels += label * weight; predictions << prediction; if (tag.begin != tag.end){ predictions << " "; predictions.write(tag.begin, tag.index()); } predictions << endl; raw_predictions << raw_prediction; if (tag.begin != tag.end) { raw_predictions << " "; raw_predictions.write(tag.begin,tag.index()); } raw_predictions << endl; if (label != FLT_MAX) { float example_loss = (prediction - label) * (prediction - label); example_loss *= weight; t += weight; sum_loss = sum_loss + example_loss; sum_loss_since_last_dump += example_loss; if (weighted_examples > dump_interval) { cout.precision(4); cout << sum_loss/weighted_examples << "\t" << sum_loss_since_last_dump / (weighted_examples - old_weighted_examples) << "\t" << example_number << "\t"; cout.precision(2); cout << weighted_examples << "\t"; cout.precision(4); cout << label << "\t" << prediction << "\t" << features.index() << "\t" << endl; sum_loss_since_last_dump = 0.0; old_weighted_examples = weighted_examples; dump_interval *= 2; } } if (label != FLT_MAX && training) { float eta_round = eta / pow(t, power_t); if (regressor.seg) { float update = expf(2.0 * eta_round * (label - prediction) * weight); float neg_update; if (fpclassify(norm) == FP_ZERO && fpclassify(neg_weight_sum) == FP_ZERO) neg_update = 1.; else neg_update = (norm + neg_weight_sum) / (norm * update + neg_weight_sum); if (isnan(neg_update) || isnan(update*neg_update)) { cout << "argh!, a nan! neg_update = " << neg_update << endl; cout << "label = " << label << endl; cout << "prediction = " << prediction << endl; cout << "norm = " << norm << endl; cout << "neg_weight_sum = " << neg_weight_sum << endl; cout << "feature number = " << features.index() << endl; cout << "update = " << update << endl; cout << "example_number = " << example_number << endl; for (feature* ele = features.begin; ele != features.end; ele++) cout << ele->weight_index << "\t" << regressor.weights[ele->weight_index] << " " << regressor.other_weights[ele->weight_index] << endl; } seg_train(features, neg_update, update * neg_update); float new_neg = 0.; float new_pos = 0.; float new_raw = 0.; seg_predict(features, new_neg, new_pos, new_raw); if (fabs(new_pos + new_neg - norm - neg_weight_sum) > (norm+neg_weight_sum) * 0.001) { cout.precision(20); cout << "Update isn't preserving weight!\n"; cout << new_pos + new_neg << "\t" << norm + neg_weight_sum << endl; cout << "label = " << label << endl; cout << "prediction = " << prediction << endl; cout << "norm = " << norm << endl; cout << "neg_weight_sum = " << neg_weight_sum << endl; cout << "feature number = " << features.index() << endl; cout << "update = " << update << endl; cout << "example_number = " << example_number << endl; cout << "Features = " << endl; for (feature* ele = features.begin; ele != features.end; ele++) cout << ele->weight_index << "\t" << regressor.weights[ele->weight_index] << "\t" << regressor.other_weights[ele->weight_index] << endl; } } else train(features, eta_round * (label - prediction) * 2. * norm * weight); } pthread_mutex_unlock(&weight_lock); } alloc(features,0); alloc(tag,0); free(td.in_already); free(td.line); free(td.channels.begin); free(td.words.begin); free(td.name.begin); alloc(td.indicies,0); for (int i = 0; i < 256; i++) free(td.atomics[i].begin); return NULL; } int main(int argc, char *argv[]) { int numthreads; int numpasses; float eta_decay; parse_args(argc, argv, eta, eta_decay, t, power_t, predictions, raw_predictions, training, numthreads, numpasses, regressor, source, final_regressor); cout << "average\tsince\texample\texample\tcurrent\tcurrent\tcurrent" << endl; cout << "loss\tlast\tcounter\tweight\tlabel\tpredict\tfeatures" << endl; cout.precision(4); for (; numpasses > 0; numpasses--) { pthread_t threads[numthreads]; for (int i = 0; i < numthreads; i++) pthread_create(&threads[i], NULL, go, NULL); for (int i = 0; i < numthreads; i++) pthread_join(threads[i], NULL); eta *= eta_decay; reset(regressor.numbits, source); } dump_regressor(final_regressor, regressor); finalize_source(source); float best_constant = weighted_labels / weighted_examples; float constant_loss = (best_constant*(1.0 - best_constant)*(1.0 - best_constant) + (1.0 - best_constant)*best_constant*best_constant); cout << endl << "finished run"; cout << endl << "number of examples = " << example_number; cout << endl << "weighted_examples = " << weighted_examples; cout << endl << "weighted_labels = " << weighted_labels; cout << endl << "average_loss = " << sum_loss / weighted_examples; cout << endl << "best constant's loss = " << constant_loss; cout << endl; return 0; } vowpal_wabbit/Makefile0000644006612600001440000000111510723351477013721 0ustar jlusersARCH = -msse2 -mfpmath=sse -march=pentium-m FLAGS = -Wall $(ARCH) -O3 -ffast-math -D_FILE_OFFSET_BITS=64 -Wno-deprecated -I /usr/include/boost-1_34_1 all: vw install vw.o: vw.cc parse_example.h parse_regressor.h parse_args.h g++ $(FLAGS) -c $< -o $@ parse_args.o: parse_regressor.h parse_example.h io.h parse_example.o: io.h stack.h parse_example.cc io.o: stack.h %.o: %.cc %.h g++ $(FLAGS) -c $< -o $@ vw: hash.o io.o parse_regressor.o parse_example.o parse_args.o vw.o g++ $(FLAGS) -l boost_program_options -l pthread -o vw $+ install: cp vw ~/bin clean: rm -f *.o vw *~ vowpal_wabbit/parse_args.h0000644006612600001440000000073310723351477014565 0ustar jlusers/* Copyright (c) 2007 Yahoo! Inc. All rights reserved. The copyrights embodied in the content of this file are licensed under the BSD (revised) open source license */ #ifndef PA_H #define PA_H void parse_args(int argc, char *argv[], float &eta, float &eta_decay_rate, float &initial_t, float &power_t, ofstream &predictions, ofstream &raw_predictions, bool &train, int &numthreads, int& passes, regressor &r, example_file &e, ofstream &final_regressor); #endif vowpal_wabbit/io.cc0000644006612600001440000000231710723351477013204 0ustar jlusers/* Copyright (c) 2007 Yahoo! Inc. All rights reserved. The copyrights embodied in the content of this file are licensed under the BSD (revised) open source license */ #include "io.h" unsigned int buf_read(io_buf &i, char* &pointer, int n) {//return a pointer to the next n bytes. n must be smaller than 2^24. if (i.space.end + n <= i.space.end_array) { pointer = i.space.end; i.space.end += n; return n; } else if (n > (i.space.end_array - i.space.begin)) // the file is ending or ended. { pointer = i.space.end; int ret = i.space.end_array - i.space.end; i.space.end = i.space.end_array; return ret; } else // Change locations and refill buffer. { int left = i.space.end_array - i.space.end; memmove(i.space.begin, i.space.end, left); i.fill(left); i.space.end = i.space.begin; return buf_read(i,pointer,n); } } void buf_write(io_buf &o, char* &pointer, int n) {//return a pointer to the next n bytes to write into. if (o.space.end + n <= o.space.end_array) { pointer = o.space.end; o.space.end += n; } else // Time to dump the file { o.flush(); buf_write (o, pointer,n); } } vowpal_wabbit/parse_args.cc0000644006612600001440000001374110723351477014726 0ustar jlusers/* Copyright (c) 2007 Yahoo! Inc. All rights reserved. The copyrights embodied in the content of this file are licensed under the BSD (revised) open source license */ #include #include #include #include #include "fcntl.h" #include "io.h" #include "parse_regressor.h" #include "parse_example.h" namespace po = boost::program_options; using namespace std; void make_write_cache(size_t numbits, bool &create_cache, string &newname, io_buf &cache) { cache.currentname = newname+string(".writing"); cache.file = open(cache.currentname.c_str(), O_CREAT|O_WRONLY|O_LARGEFILE|O_TRUNC,0666); if (cache.file == -1) { cerr << "can't create cache file !" << endl; return; } char *p; buf_write(cache, p, sizeof(size_t)); *(size_t *)p = numbits; cache.finalname = newname; create_cache = true; cout << "creating cache_file = " << newname << endl; } void parse_cache(po::variables_map &vm, size_t numbits, string source, example_file &e) { e.mask = (1 << numbits) - 1; if (vm.count("cache") || vm.count("cache_file")) { string cache_string; if (vm.count("cache_file")) cache_string = vm["cache_file"].as< string >(); else cache_string = source+string(".cache"); e.cache.file = open(cache_string.c_str(), O_RDONLY|O_LARGEFILE); if (e.cache.file == -1) make_write_cache(numbits, e.write_cache, cache_string, e.cache); else { e.cache.fill(0); if (inconsistent_cache(numbits, e.cache)) { close(e.cache.file); e.cache.space.erase(); make_write_cache(numbits, e.write_cache, cache_string, e.cache); } else { cout << "using cache_file = " << cache_string << endl; e.write_cache = false; } } } else { cout << "using no cache" << endl; alloc(e.cache.space,0); e.cache.file=-1; e.write_cache = false; } } void parse_args(int argc, char *argv[], float &eta, float &eta_decay_rate, float &initial_t, float &power_t, ofstream &predictions, ofstream &raw_predictions, bool &train, int &numthreads, int& passes, regressor &r, example_file &e, ofstream &final_regressor) { // Declare the supported options. po::options_description desc("Allowed options"); desc.add_options() ("bit_precision,b", po::value(&r.numbits)->default_value(18), "number of bits in the feature table") ("cache,c", "Use a cache. The default is .cache") ("cache_file", po::value< string >(), "The location of a cache_file.") ("data,d", po::value< string >()->default_value(""), "Example Set") ("decay_learning_rate", po::value(&eta_decay_rate)->default_value(1/sqrt(2.)), "Set Decay Rate of Learning Rate") ("final_regressor,f", po::value< string >(), "Final regressor") ("help,h","Output Arguments") ("initial_regressor,i", po::value< vector >(), "Initial regressor") ("initial_t", po::value(&initial_t)->default_value(1.), "initial t value") ("power_t", po::value(&power_t)->default_value(0.), "t power value") ("learning_rate,l", po::value(&eta)->default_value(0.1), "Set Learning Rate") ("passes", po::value(&passes)->default_value(1), "Number of Training Passes") ("predictions,p", po::value< string >(), "File to output predictions to") ("quadratic,q", po::value< vector > (), "Create and use quadratic features") ("raw_predictions,r", po::value< string >(), "File to output unnormalized predictions to") ("seg,s", "Use SEG algorithm") ("testonly,t", "Ignore label information and just test") ("threads", po::value(&numthreads)->default_value(1), "Number of threads") ; po::positional_options_description p; p.add("data", -1); po::variables_map vm; po::store(po::command_line_parser(argc, argv). options(desc).positional(p).run(), vm); po::notify(vm); if (vm.count("help") || argc == 1) { cout << "\n" << desc << "\n"; exit(1); } if (r.numbits > 29) { cout << "The system limits at 29 bits of precision!\n" << endl; exit(1); } if (vm.count("quadratic")) { r.pairs = vm["quadratic"].as< vector >(); cout << "creating quadratic features for pairs: "; for (vector::iterator i = r.pairs.begin(); i != r.pairs.end();i++) { cout << *i << " "; if (i->length() > 2) cout << endl << "warning, ignoring characters after the 2nd.\n"; if (i->length() < 2) { cout << endl << "error, quadratic features must involve two sets.\n"; exit(0); } } cout << endl; } r.seg = false; if (vm.count("seg")) r.seg = true; vector regs; if (vm.count("initial_regressor")) regs = vm["initial_regressor"].as< vector >(); parse_regressor(regs, r); if (r.seg) cout << "SEG being used" << endl; parse_cache(vm, r.numbits, vm["data"].as(), e); if (vm.count("data") && vm["data"].as () != string("")) { string temp = vm["data"].as< string >(); cout << "Reading from " << temp << endl; e.data = fopen64(temp.c_str(), "r"); if (e.data == NULL) { cerr << "can't open " << temp << ", bailing!" << endl; exit(0); } } else { e.data = stdin; cout << "reading from stdin" << endl; } if (vm.count("final_regressor")) { cout << "final_regressor = " << vm["final_regressor"].as() << endl; final_regressor.open(vm["final_regressor"].as().c_str()); } if (vm.count("predictions")) { cout << "predictions = " << vm["predictions"].as< string >() << endl; predictions.open(vm["predictions"].as< string >().c_str()); } if (vm.count("raw_predictions")) { cout << "raw predictions = " << vm["raw_predictions"].as< string >() << endl; raw_predictions.open(vm["raw_predictions"].as< string >().c_str()); } if (vm.count("testonly")) { cout << "only testing" << endl; train = false; } else cout << "learning_rate set to " << eta << endl; }