3660b16cc547fe93e8e6db8cec272bfc5d34342f
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
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]
9 */
12 /// \file
13 /// \brief Defines TProb<T> and Prob classes which represent (probability) vectors
14 /// \todo Rename to Vector<T>
17 #ifndef __defined_libdai_prob_h
18 #define __defined_libdai_prob_h
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>
31 namespace dai {
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;
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;
64 /// \name Constructors and destructors
65 //@{
66 /// Default constructor (constructs empty vector)
67 TProb() : _p() {}
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)) {}
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) {}
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 }
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 //@}
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;
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(); }
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(); }
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(); }
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 //@}
130 /// \name Queries
131 //@{
132 /// Returns a const reference to the wrapped vector
133 const std::vector<T> & p() const { return _p; }
135 /// Returns a reference to the wrapped vector
136 std::vector<T> & p() { return _p; }
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 }
147 /// Returns reference to the \a i 'th entry
148 T& operator[]( size_t i ) { return _p[i]; }
150 /// Returns length of the vector (i.e., the number of entries)
151 size_t size() const { return _p.size(); }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
211 /// Returns \c 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 }
222 /// Returns \c 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 }
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 }
239 /// Lexicographical comparison
240 /** \pre <tt>this->size() == q.size()</tt>
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 //@}
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 }
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 }
277 /// Returns pointwise exponent
278 TProb<T> exp() const {
279 TProb<T> e(*this);
280 e.takeExp();
281 return e;
282 }
284 /// Returns pointwise logarithm
285 /** If \a zero == \c true, uses <tt>log(0)==0</tt>; otherwise, <tt>log(0)==-Inf</tt>.
286 */
287 TProb<T> log(bool zero=false) const {
288 TProb<T> l(*this);
289 l.takeLog(zero);
290 return l;
291 }
293 /// Returns pointwise inverse
294 /** If \a zero == \c true, uses <tt>1/0==0</tt>; otherwise, <tt>1/0==Inf</tt>.
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 }
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 //@}
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 }
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 }
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 }
337 /// Applies logarithm pointwise
338 /** If \a zero == \c true, uses <tt>log(0)==0</tt>; otherwise, <tt>log(0)==-Inf</tt>.
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 }
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 //@}
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 }
373 // OBSOLETE
374 /// Sets entries that are smaller (in absolute value) than \a epsilon to 0
375 /** \note Obsolete, to be removed soon
376 */
377 TProb<T>& makeZero( T epsilon ) {
378 for( size_t i = 0; i < size(); i++ )
379 if( (_p[i] < epsilon) && (_p[i] > -epsilon) )
380 _p[i] = 0;
381 return *this;
382 }
384 // OBSOLETE
385 /// Sets entries that are smaller than \a epsilon to \a epsilon
386 /** \note Obsolete, to be removed soon
387 */
388 TProb<T>& makePositive( T epsilon ) {
389 for( size_t i = 0; i < size(); i++ )
390 if( (0 < _p[i]) && (_p[i] < epsilon) )
391 _p[i] = epsilon;
392 return *this;
393 }
395 /// Adds scalar \a x to each entry
396 TProb<T>& operator+= (T x) {
397 std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::plus<T>(), x ) );
398 return *this;
399 }
401 /// Subtracts scalar \a x from each entry
402 TProb<T>& operator-= (T x) {
403 std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::minus<T>(), x ) );
404 return *this;
405 }
407 /// Multiplies each entry with scalar \a x
408 TProb<T>& operator*= (T x) {
409 std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::multiplies<T>(), x) );
410 return *this;
411 }
413 /// Divides each entry by scalar \a x
414 TProb<T>& operator/= (T x) {
415 DAI_DEBASSERT( x != 0 );
416 std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::divides<T>(), x ) );
417 return *this;
418 }
420 /// Raises entries to the power \a x
421 TProb<T>& operator^= (T x) {
422 if( x != (T)1 )
423 std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::ptr_fun<T, T, T>(std::pow), x) );
424 return *this;
425 }
426 //@}
428 /// \name Transformations with scalars
429 //@{
430 /// Returns sum of \c *this and scalar \a x
431 TProb<T> operator+ (T x) const {
432 TProb<T> sum( *this );
433 sum += x;
434 return sum;
435 }
437 /// Returns difference of \c *this and scalar \a x
438 TProb<T> operator- (T x) const {
439 TProb<T> diff( *this );
440 diff -= x;
441 return diff;
442 }
444 /// Returns product of \c *this with scalar \a x
445 TProb<T> operator* (T x) const {
446 TProb<T> prod( *this );
447 prod *= x;
448 return prod;
449 }
451 /// Returns quotient of \c *this and scalar \a x
452 TProb<T> operator/ (T x) const {
453 TProb<T> quot( *this );
454 quot /= x;
455 return quot;
456 }
458 /// Returns *this raised to the power \a x
459 TProb<T> operator^ (T x) const {
460 TProb<T> power(*this);
461 power ^= x;
462 return power;
463 }
464 //@}
466 /// \name Operations with other equally-sized vectors
467 //@{
468 /// Pointwise addition with \a q
469 /** \pre <tt>this->size() == q.size()</tt>
470 */
471 TProb<T>& operator+= (const TProb<T> & q) {
472 DAI_DEBASSERT( size() == q.size() );
473 std::transform( _p.begin(), _p.end(), q._p.begin(), _p.begin(), std::plus<T>() );
474 return *this;
475 }
477 /// Pointwise subtraction of \a q
478 /** \pre <tt>this->size() == q.size()</tt>
479 */
480 TProb<T>& operator-= (const TProb<T> & q) {
481 DAI_DEBASSERT( size() == q.size() );
482 std::transform( _p.begin(), _p.end(), q._p.begin(), _p.begin(), std::minus<T>() );
483 return *this;
484 }
486 /// Pointwise multiplication with \a q
487 /** \pre <tt>this->size() == q.size()</tt>
488 */
489 TProb<T>& operator*= (const TProb<T> & q) {
490 DAI_DEBASSERT( size() == q.size() );
491 std::transform( _p.begin(), _p.end(), q._p.begin(), _p.begin(), std::multiplies<T>() );
492 return *this;
493 }
495 /// Pointwise division by \a q, where division by 0 yields 0
496 /** \pre <tt>this->size() == q.size()</tt>
497 * \see divide(const TProb<T> &)
498 */
499 TProb<T>& operator/= (const TProb<T> & q) {
500 DAI_DEBASSERT( size() == q.size() );
501 for( size_t i = 0; i < size(); i++ ) {
502 if( q[i] == 0.0 )
503 _p[i] = 0.0;
504 else
505 _p[i] /= q[i];
506 }
507 return *this;
508 }
510 /// Pointwise division by \a q, where division by 0 yields +Inf
511 /** \pre <tt>this->size() == q.size()</tt>
512 * \see operator/=(const TProb<T> &)
513 */
514 TProb<T>& divide (const TProb<T> & q) {
515 DAI_DEBASSERT( size() == q.size() );
516 std::transform( _p.begin(), _p.end(), q._p.begin(), _p.begin(), std::divides<T>() );
517 return *this;
518 }
519 //@}
521 /// \name Transformations with other equally-sized vectors
522 //@{
523 /// Returns sum of \c *this and \a q
524 /** \pre <tt>this->size() == q.size()</tt>
525 */
526 TProb<T> operator+ (const TProb<T> & q) const {
527 DAI_DEBASSERT( size() == q.size() );
528 TProb<T> sum( *this );
529 sum += q;
530 return sum;
531 }
533 /// Return \c *this minus \a q
534 /** \pre <tt>this->size() == q.size()</tt>
535 */
536 TProb<T> operator- (const TProb<T> & q) const {
537 DAI_DEBASSERT( size() == q.size() );
538 TProb<T> diff( *this );
539 diff -= q;
540 return diff;
541 }
543 /// Return product of \c *this with \a q
544 /** \pre <tt>this->size() == q.size()</tt>
545 */
546 TProb<T> operator* (const TProb<T> & q) const {
547 DAI_DEBASSERT( size() == q.size() );
548 TProb<T> prod( *this );
549 prod *= q;
550 return prod;
551 }
553 /// Returns quotient of \c *this with \a q, where division by 0 yields +Inf
554 /** \pre <tt>this->size() == q.size()</tt>
555 * \see divided_by(const TProb<T> &)
556 */
557 TProb<T> operator/ (const TProb<T> & q) const {
558 DAI_DEBASSERT( size() == q.size() );
559 TProb<T> quot( *this );
560 quot /= q;
561 return quot;
562 }
564 /// Pointwise division by \a q, where division by 0 yields 0
565 /** \pre <tt>this->size() == q.size()</tt>
566 * \see operator/(const TProb<T> &)
567 */
568 TProb<T> divided_by (const TProb<T> & q) const {
569 DAI_DEBASSERT( size() == q.size() );
570 TProb<T> quot( *this );
571 quot.divide(q);
572 return quot;
573 }
574 //@}
575 };
578 /// Returns distance between \a p and \a q, measured using distance measure \a dt
579 /** \relates TProb
580 * \pre <tt>this->size() == q.size()</tt>
581 */
582 template<typename T> T dist( const TProb<T> &p, const TProb<T> &q, typename TProb<T>::DistType dt ) {
583 DAI_DEBASSERT( p.size() == q.size() );
584 T result = 0;
585 switch( dt ) {
586 case TProb<T>::DISTL1:
587 for( size_t i = 0; i < p.size(); i++ )
588 result += abs(p[i] - q[i]);
589 break;
591 case TProb<T>::DISTLINF:
592 for( size_t i = 0; i < p.size(); i++ ) {
593 T z = abs(p[i] - q[i]);
594 if( z > result )
595 result = z;
596 }
597 break;
599 case TProb<T>::DISTTV:
600 for( size_t i = 0; i < p.size(); i++ )
601 result += abs(p[i] - q[i]);
602 result /= 2;
603 break;
605 case TProb<T>::DISTKL:
606 for( size_t i = 0; i < p.size(); i++ ) {
607 if( p[i] != 0.0 )
608 result += p[i] * (dai::log(p[i]) - dai::log(q[i]));
609 }
610 }
611 return result;
612 }
615 /// Writes a TProb<T> to an output stream
616 /** \relates TProb
617 */
618 template<typename T> std::ostream& operator<< (std::ostream& os, const TProb<T>& p) {
619 os << "[";
620 std::copy( p.p().begin(), p.p().end(), std::ostream_iterator<T>(os, " ") );
621 os << "]";
622 return os;
623 }
626 /// Returns the pointwise minimum of \a a and \a b
627 /** \relates TProb
628 * \pre <tt>this->size() == q.size()</tt>
629 */
630 template<typename T> TProb<T> min( const TProb<T> &a, const TProb<T> &b ) {
631 DAI_ASSERT( a.size() == b.size() );
632 TProb<T> result( a.size() );
633 for( size_t i = 0; i < a.size(); i++ )
634 if( a[i] < b[i] )
635 result[i] = a[i];
636 else
637 result[i] = b[i];
638 return result;
639 }
642 /// Returns the pointwise maximum of \a a and \a b
643 /** \relates TProb
644 * \pre <tt>this->size() == q.size()</tt>
645 */
646 template<typename T> TProb<T> max( const TProb<T> &a, const TProb<T> &b ) {
647 DAI_ASSERT( a.size() == b.size() );
648 TProb<T> result( a.size() );
649 for( size_t i = 0; i < a.size(); i++ )
650 if( a[i] > b[i] )
651 result[i] = a[i];
652 else
653 result[i] = b[i];
654 return result;
655 }
658 /// Represents a vector with entries of type dai::Real.
659 typedef TProb<Real> Prob;
662 } // end of namespace dai
665 #endif