Various cleanups and documentation improvements for SmallSet and Prob
[libdai.git] / include / dai / prob.h
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * libDAI is licensed under the terms of the GNU General Public License version
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
6 *
7 * Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
9 */
10
11
12 /// \file
13 /// \brief Defines TProb<T> and Prob classes which represent (probability) vectors
14 /// \todo Rename to Vector<T>
15
16
17 #ifndef __defined_libdai_prob_h
18 #define __defined_libdai_prob_h
19
20
21 #include <cmath>
22 #include <vector>
23 #include <ostream>
24 #include <algorithm>
25 #include <numeric>
26 #include <functional>
27 #include <dai/util.h>
28 #include <dai/exceptions.h>
29
30
31 namespace dai {
32
33
34 /// Represents a vector with entries of type \a T.
35 /** It is simply a <tt>std::vector</tt><<em>T</em>> with an interface designed for dealing with probability mass functions.
36 *
37 * It is mainly used for representing measures on a finite outcome space, for example, the probability
38 * distribution of a discrete random variable. However, entries are not necessarily non-negative; it is also used to
39 * represent logarithms of probability mass functions.
40 *
41 * \tparam T Should be a scalar that is castable from and to dai::Real and should support elementary arithmetic operations.
42 */
43 template <typename T> class TProb {
44 private:
45 /// The vector
46 std::vector<T> _p;
47
48 public:
49 /// Enumerates different ways of normalizing a probability measure.
50 /**
51 * - NORMPROB means that the sum of all entries should be 1;
52 * - NORMLINF means that the maximum absolute value of all entries should be 1.
53 */
54 typedef enum { NORMPROB, NORMLINF } NormType;
55 /// Enumerates different distance measures between probability measures.
56 /**
57 * - DISTL1 is the \f$\ell_1\f$ distance (sum of absolute values of pointwise difference);
58 * - DISTLINF is the \f$\ell_\infty\f$ distance (maximum absolute value of pointwise difference);
59 * - DISTTV is the total variation distance (half of the \f$\ell_1\f$ distance);
60 * - DISTKL is the Kullback-Leibler distance (\f$\sum_i p_i (\log p_i - \log q_i)\f$).
61 */
62 typedef enum { DISTL1, DISTLINF, DISTTV, DISTKL } DistType;
63
64 /// \name Constructors and destructors
65 //@{
66 /// Default constructor (constructs empty vector)
67 TProb() : _p() {}
68
69 /// Construct uniform probability distribution over \a n outcomes (i.e., a vector of length \a n with each entry set to \f$1/n\f$)
70 explicit TProb( size_t n ) : _p(std::vector<T>(n, (T)1 / n)) {}
71
72 /// Construct vector of length \a n with each entry set to \a p
73 explicit TProb( size_t n, T p ) : _p(n, p) {}
74
75 /// Construct vector from a range
76 /** \tparam TIterator Iterates over instances that can be cast to \a T
77 * \param begin Points to first instance to be added.
78 * \param end Points just beyond last instance to be added.
79 * \param sizeHint For efficiency, the number of entries can be speficied by \a sizeHint.
80 */
81 template <typename TIterator>
82 TProb( TIterator begin, TIterator end, size_t sizeHint=0 ) : _p() {
83 _p.reserve( sizeHint );
84 _p.insert( _p.begin(), begin, end );
85 }
86
87 /// Construct vector from another vector
88 /** \tparam S type of elements in \a v (should be castable to type \a T)
89 * \param v vector used for initialization
90 */
91 template <typename S>
92 TProb( const std::vector<S> &v ) : _p() {
93 _p.reserve( v.size() );
94 _p.insert( _p.begin(), v.begin(), v.end() );
95 }
96 //@}
97
98 /// Constant iterator over the elements
99 typedef typename std::vector<T>::const_iterator const_iterator;
100 /// Iterator over the elements
101 typedef typename std::vector<T>::iterator iterator;
102 /// Constant reverse iterator over the elements
103 typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
104 /// Reverse iterator over the elements
105 typedef typename std::vector<T>::reverse_iterator reverse_iterator;
106
107 /// @name Iterator interface
108 //@{
109 /// Returns iterator that points to the first element
110 iterator begin() { return _p.begin(); }
111 /// Returns constant iterator that points to the first element
112 const_iterator begin() const { return _p.begin(); }
113
114 /// Returns iterator that points beyond the last element
115 iterator end() { return _p.end(); }
116 /// Returns constant iterator that points beyond the last element
117 const_iterator end() const { return _p.end(); }
118
119 /// Returns reverse iterator that points to the last element
120 reverse_iterator rbegin() { return _p.rbegin(); }
121 /// Returns constant reverse iterator that points to the last element
122 const_reverse_iterator rbegin() const { return _p.rbegin(); }
123
124 /// Returns reverse iterator that points beyond the first element
125 reverse_iterator rend() { return _p.rend(); }
126 /// Returns constant reverse iterator that points beyond the first element
127 const_reverse_iterator rend() const { return _p.rend(); }
128 //@}
129
130 /// \name Queries
131 //@{
132 /// Returns a const reference to the wrapped vector
133 const std::vector<T> & p() const { return _p; }
134
135 /// Returns a reference to the wrapped vector
136 std::vector<T> & p() { return _p; }
137
138 /// Returns a copy of the \a i 'th entry
139 T operator[]( size_t i ) const {
140 #ifdef DAI_DEBUG
141 return _p.at(i);
142 #else
143 return _p[i];
144 #endif
145 }
146
147 /// Returns reference to the \a i 'th entry
148 T& operator[]( size_t i ) { return _p[i]; }
149
150 /// Returns length of the vector (i.e., the number of entries)
151 size_t size() const { return _p.size(); }
152
153 /// Returns the Shannon entropy of *this, \f$-\sum_i p_i \log p_i\f$
154 T entropy() const {
155 T S = 0;
156 for( size_t i = 0; i < size(); i++ )
157 S -= (_p[i] == 0 ? 0 : _p[i] * dai::log(_p[i]));
158 return S;
159 }
160
161 /// Returns maximum value of all entries
162 T max() const {
163 T Z = *std::max_element( _p.begin(), _p.end() );
164 return Z;
165 }
166
167 /// Returns minimum value of all entries
168 T min() const {
169 T Z = *std::min_element( _p.begin(), _p.end() );
170 return Z;
171 }
172
173 /// Returns a pair consisting of the index of the maximum value and the maximum value itself
174 std::pair<size_t,T> argmax() const {
175 T max = _p[0];
176 size_t arg = 0;
177 for( size_t i = 1; i < size(); i++ ) {
178 if( _p[i] > max ) {
179 max = _p[i];
180 arg = i;
181 }
182 }
183 return std::make_pair(arg,max);
184 }
185
186 /// Returns sum of all entries
187 T sum() const {
188 T Z = std::accumulate( _p.begin(), _p.end(), (T)0 );
189 return Z;
190 }
191
192 /// Return sum of absolute value of all entries
193 T sumAbs() const {
194 T s = 0;
195 for( size_t i = 0; i < size(); i++ )
196 s += dai::abs(_p[i]);
197 return s;
198 }
199
200 /// Returns maximum absolute value of all entries
201 T maxAbs() const {
202 T Z = 0;
203 for( size_t i = 0; i < size(); i++ ) {
204 T mag = dai::abs(_p[i]);
205 if( mag > Z )
206 Z = mag;
207 }
208 return Z;
209 }
210
211 /// Returns true if one or more entries are NaN
212 bool hasNaNs() const {
213 bool foundnan = false;
214 for( typename std::vector<T>::const_iterator x = _p.begin(); x != _p.end(); x++ )
215 if( isnan( *x ) ) {
216 foundnan = true;
217 break;
218 }
219 return foundnan;
220 }
221
222 /// Returns true if one or more entries are negative
223 bool hasNegatives() const {
224 return (std::find_if( _p.begin(), _p.end(), std::bind2nd( std::less<T>(), (T)0 ) ) != _p.end());
225 }
226
227 /// Returns a random index, according to the (normalized) distribution described by *this
228 size_t draw() {
229 Real x = rnd_uniform() * sum();
230 T s = 0;
231 for( size_t i = 0; i < size(); i++ ) {
232 s += _p[i];
233 if( s > x )
234 return i;
235 }
236 return( size() - 1 );
237 }
238
239 /// Lexicographical comparison
240 /** \pre this->size() == q.size()
241 */
242 bool operator<= (const TProb<T> & q) const {
243 DAI_DEBASSERT( size() == q.size() );
244 for( size_t i = 0; i < size(); i++ )
245 if( !(_p[i] <= q[i]) )
246 return false;
247 return true;
248 }
249 //@}
250
251 /// \name Unary transformations
252 //@{
253 /// Returns pointwise signum
254 TProb<T> sgn() const {
255 TProb<T> x;
256 x._p.reserve( size() );
257 for( size_t i = 0; i < size(); i++ ) {
258 T s = 0;
259 if( _p[i] > 0 )
260 s = 1;
261 else if( _p[i] < 0 )
262 s = -1;
263 x._p.push_back( s );
264 }
265 return x;
266 }
267
268 /// Returns pointwise absolute value
269 TProb<T> abs() const {
270 TProb<T> x;
271 x._p.reserve( size() );
272 for( size_t i = 0; i < size(); i++ )
273 x._p.push_back( abs(_p[i]) );
274 return x;
275 }
276
277 /// Returns pointwise exponent
278 TProb<T> exp() const {
279 TProb<T> e(*this);
280 e.takeExp();
281 return e;
282 }
283
284 /// Returns pointwise logarithm
285 /** If zero==true, uses log(0)==0; otherwise, log(0)==-Inf.
286 */
287 TProb<T> log(bool zero=false) const {
288 TProb<T> l(*this);
289 l.takeLog(zero);
290 return l;
291 }
292
293 /// Returns pointwise inverse
294 /** If zero==true; uses 1/0==0, otherwise 1/0==Inf.
295 */
296 TProb<T> inverse(bool zero=true) const {
297 TProb<T> inv;
298 inv._p.reserve( size() );
299 if( zero )
300 for( size_t i = 0; i < size(); i++ )
301 inv._p.push_back( _p[i] == 0.0 ? 0.0 : 1.0 / _p[i] );
302 else
303 for( size_t i = 0; i < size(); i++ )
304 inv._p.push_back( 1.0 / _p[i] );
305 return inv;
306 }
307
308 /// Returns normalized copy of \c *this, using the specified norm
309 TProb<T> normalized( NormType norm = NORMPROB ) const {
310 TProb<T> result(*this);
311 result.normalize( norm );
312 return result;
313 }
314 //@}
315
316 /// \name Unary operations
317 //@{
318 /// Draws all entries i.i.d. from a uniform distribution on [0,1)
319 TProb<T>& randomize() {
320 std::generate( _p.begin(), _p.end(), rnd_uniform );
321 return *this;
322 }
323
324 /// Sets all entries to \f$1/n\f$ where \a n is the length of the vector
325 TProb<T>& setUniform () {
326 fill( (T)1 / size() );
327 return *this;
328 }
329
330 /// Applies exponent pointwise
331 const TProb<T>& takeExp() {
332 for( size_t i = 0; i < size(); i++ )
333 _p[i] = dai::exp(_p[i]);
334 return *this;
335 }
336
337 /// Applies logarithm pointwise
338 /** If zero==true, uses log(0)==0; otherwise, log(0)==-Inf.
339 */
340 const TProb<T>& takeLog(bool zero=false) {
341 if( zero ) {
342 for( size_t i = 0; i < size(); i++ )
343 _p[i] = ( (_p[i] == 0.0) ? 0.0 : dai::log(_p[i]) );
344 } else
345 for( size_t i = 0; i < size(); i++ )
346 _p[i] = dai::log(_p[i]);
347 return *this;
348 }
349
350 /// Normalizes vector using the specified norm
351 T normalize( NormType norm=NORMPROB ) {
352 T Z = 0.0;
353 if( norm == NORMPROB )
354 Z = sum();
355 else if( norm == NORMLINF )
356 Z = maxAbs();
357 if( Z == 0.0 )
358 DAI_THROW(NOT_NORMALIZABLE);
359 else
360 *this /= Z;
361 return Z;
362 }
363 //@}
364
365 /// \name Operations with scalars
366 //@{
367 /// Sets all entries to \a x
368 TProb<T> & fill(T x) {
369 std::fill( _p.begin(), _p.end(), x );
370 return *this;
371 }
372
373 /// Adds scalar \a x to each entry
374 TProb<T>& operator+= (T x) {
375 std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::plus<T>(), x ) );
376 return *this;
377 }
378
379 /// Subtracts scalar \a x from each entry
380 TProb<T>& operator-= (T x) {
381 std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::minus<T>(), x ) );
382 return *this;
383 }
384
385 /// Multiplies each entry with scalar \a x
386 TProb<T>& operator*= (T x) {
387 std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::multiplies<T>(), x) );
388 return *this;
389 }
390
391 /// Divides each entry by scalar \a x
392 TProb<T>& operator/= (T x) {
393 DAI_DEBASSERT( x != 0 );
394 std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::divides<T>(), x ) );
395 return *this;
396 }
397
398 /// Raises entries to the power \a x
399 TProb<T>& operator^= (T x) {
400 if( x != (T)1 )
401 std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::ptr_fun<T, T, T>(std::pow), x) );
402 return *this;
403 }
404 //@}
405
406 /// \name Transformations with scalars
407 //@{
408 /// Returns sum of \c *this and scalar \a x
409 TProb<T> operator+ (T x) const {
410 TProb<T> sum( *this );
411 sum += x;
412 return sum;
413 }
414
415 /// Returns difference of \c *this and scalar \a x
416 TProb<T> operator- (T x) const {
417 TProb<T> diff( *this );
418 diff -= x;
419 return diff;
420 }
421
422 /// Returns product of \c *this with scalar \a x
423 TProb<T> operator* (T x) const {
424 TProb<T> prod( *this );
425 prod *= x;
426 return prod;
427 }
428
429 /// Returns quotient of \c *this and scalar \a x
430 TProb<T> operator/ (T x) const {
431 TProb<T> quot( *this );
432 quot /= x;
433 return quot;
434 }
435
436 /// Returns *this raised to the power \a x
437 TProb<T> operator^ (T x) const {
438 TProb<T> power(*this);
439 power ^= x;
440 return power;
441 }
442 //@}
443
444 /// \name Operations with other equally-sized vectors
445 //@{
446 /// Pointwise addition with \a q
447 /** \pre this->size() == q.size()
448 */
449 TProb<T>& operator+= (const TProb<T> & q) {
450 DAI_DEBASSERT( size() == q.size() );
451 std::transform( _p.begin(), _p.end(), q._p.begin(), _p.begin(), std::plus<T>() );
452 return *this;
453 }
454
455 /// Pointwise subtraction of \a q
456 /** \pre this->size() == q.size()
457 */
458 TProb<T>& operator-= (const TProb<T> & q) {
459 DAI_DEBASSERT( size() == q.size() );
460 std::transform( _p.begin(), _p.end(), q._p.begin(), _p.begin(), std::minus<T>() );
461 return *this;
462 }
463
464 /// Pointwise multiplication with \a q
465 /** \pre this->size() == q.size()
466 */
467 TProb<T>& operator*= (const TProb<T> & q) {
468 DAI_DEBASSERT( size() == q.size() );
469 std::transform( _p.begin(), _p.end(), q._p.begin(), _p.begin(), std::multiplies<T>() );
470 return *this;
471 }
472
473 /// Pointwise division by \a q, where division by 0 yields 0
474 /** \pre this->size() == q.size()
475 * \see divide(const TProb<T> &)
476 */
477 TProb<T>& operator/= (const TProb<T> & q) {
478 DAI_DEBASSERT( size() == q.size() );
479 for( size_t i = 0; i < size(); i++ ) {
480 if( q[i] == 0.0 )
481 _p[i] = 0.0;
482 else
483 _p[i] /= q[i];
484 }
485 return *this;
486 }
487
488 /// Pointwise division by \a q, where division by 0 yields +Inf
489 /** \pre this->size() == q.size()
490 * \see operator/=(const TProb<T> &)
491 */
492 TProb<T>& divide (const TProb<T> & q) {
493 DAI_DEBASSERT( size() == q.size() );
494 std::transform( _p.begin(), _p.end(), q._p.begin(), _p.begin(), std::divides<T>() );
495 return *this;
496 }
497 //@}
498
499 /// \name Transformations with other equally-sized vectors
500 //@{
501 /// Returns sum of \c *this and \a q
502 /** \pre this->size() == q.size()
503 */
504 TProb<T> operator+ (const TProb<T> & q) const {
505 DAI_DEBASSERT( size() == q.size() );
506 TProb<T> sum( *this );
507 sum += q;
508 return sum;
509 }
510
511 /// Return \c *this minus \a q
512 /** \pre this->size() == q.size()
513 */
514 TProb<T> operator- (const TProb<T> & q) const {
515 DAI_DEBASSERT( size() == q.size() );
516 TProb<T> diff( *this );
517 diff -= q;
518 return diff;
519 }
520
521 /// Return product of \c *this with \a q
522 /** \pre this->size() == q.size()
523 */
524 TProb<T> operator* (const TProb<T> & q) const {
525 DAI_DEBASSERT( size() == q.size() );
526 TProb<T> prod( *this );
527 prod *= q;
528 return prod;
529 }
530
531 /// Returns quotient of \c *this with \a q, where division by 0 yields +Inf
532 /** \pre this->size() == q.size()
533 * \see divided_by(const TProb<T> &)
534 */
535 TProb<T> operator/ (const TProb<T> & q) const {
536 DAI_DEBASSERT( size() == q.size() );
537 TProb<T> quot( *this );
538 quot /= q;
539 return quot;
540 }
541
542 /// Pointwise division by \a q, where division by 0 yields 0
543 /** \pre this->size() == q.size()
544 * \see operator/(const TProb<T> &)
545 */
546 TProb<T> divided_by (const TProb<T> & q) const {
547 DAI_DEBASSERT( size() == q.size() );
548 TProb<T> quot( *this );
549 quot.divide(q);
550 return quot;
551 }
552 //@}
553 };
554
555
556 /// Returns distance between \a p and \a q, measured using distance measure \a dt
557 /** \relates TProb
558 * \pre this->size() == q.size()
559 */
560 template<typename T> T dist( const TProb<T> &p, const TProb<T> &q, typename TProb<T>::DistType dt ) {
561 DAI_DEBASSERT( p.size() == q.size() );
562 T result = 0;
563 switch( dt ) {
564 case TProb<T>::DISTL1:
565 for( size_t i = 0; i < p.size(); i++ )
566 result += abs(p[i] - q[i]);
567 break;
568
569 case TProb<T>::DISTLINF:
570 for( size_t i = 0; i < p.size(); i++ ) {
571 T z = abs(p[i] - q[i]);
572 if( z > result )
573 result = z;
574 }
575 break;
576
577 case TProb<T>::DISTTV:
578 for( size_t i = 0; i < p.size(); i++ )
579 result += abs(p[i] - q[i]);
580 result /= 2;
581 break;
582
583 case TProb<T>::DISTKL:
584 for( size_t i = 0; i < p.size(); i++ ) {
585 if( p[i] != 0.0 )
586 result += p[i] * (dai::log(p[i]) - dai::log(q[i]));
587 }
588 }
589 return result;
590 }
591
592
593 /// Writes a TProb<T> to an output stream
594 /** \relates TProb
595 */
596 template<typename T> std::ostream& operator<< (std::ostream& os, const TProb<T>& P) {
597 os << "[";
598 std::copy( P.p().begin(), P.p().end(), std::ostream_iterator<T>(os, " ") );
599 os << "]";
600 return os;
601 }
602
603
604 /// Returns the TProb<T> containing the pointwise minimum of a and b (which should have equal size)
605 /** \relates TProb
606 */
607 template<typename T> TProb<T> min( const TProb<T> &a, const TProb<T> &b ) {
608 DAI_ASSERT( a.size() == b.size() );
609 TProb<T> result( a.size() );
610 for( size_t i = 0; i < a.size(); i++ )
611 if( a[i] < b[i] )
612 result[i] = a[i];
613 else
614 result[i] = b[i];
615 return result;
616 }
617
618
619 /// Returns the TProb<T> containing the pointwise maximum of a and b (which should have equal size)
620 /** \relates TProb
621 */
622 template<typename T> TProb<T> max( const TProb<T> &a, const TProb<T> &b ) {
623 DAI_ASSERT( a.size() == b.size() );
624 TProb<T> result( a.size() );
625 for( size_t i = 0; i < a.size(); i++ )
626 if( a[i] > b[i] )
627 result[i] = a[i];
628 else
629 result[i] = b[i];
630 return result;
631 }
632
633
634 /// Represents a vector with entries of type dai::Real.
635 typedef TProb<Real> Prob;
636
637
638 } // end of namespace dai
639
640
641 #endif