1 /**
2  *
3  *   Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU)
4  *   info_at_agrum_dot_org
5  *
6  *  This library is free software: you can redistribute it and/or modify
7  *  it under the terms of the GNU Lesser General Public License as published by
8  *  the Free Software Foundation, either version 3 of the License, or
9  *  (at your option) any later version.
10  *
11  *  This library is distributed in the hope that it will be useful,
12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  *  GNU Lesser General Public License for more details.
15  *
16  *  You should have received a copy of the GNU Lesser General Public License
17  *  along with this library.  If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 
22 /** @file
23  * @brief the class for computing Log2-Likelihood scores
24  *
25  * @author Christophe GONZALES(_at_AMU) and Pierre-Henri WUILLEMIN(_at_LIP6)
26  */
27 
28 #ifndef DOXYGEN_SHOULD_SKIP_THIS
29 
30 #  include <agrum/BN/learning/scores_and_tests/scoreLog2Likelihood.h>
31 #  include <sstream>
32 
33 namespace gum {
34 
35   namespace learning {
36 
37     /// default constructor
38     template < template < typename > class ALLOC >
ScoreLog2Likelihood(const DBRowGeneratorParser<ALLOC> & parser,const Apriori<ALLOC> & apriori,const std::vector<std::pair<std::size_t,std::size_t>,ALLOC<std::pair<std::size_t,std::size_t>>> & ranges,const Bijection<NodeId,std::size_t,ALLOC<std::size_t>> & nodeId2columns,const typename ScoreLog2Likelihood<ALLOC>::allocator_type & alloc)39     INLINE ScoreLog2Likelihood< ALLOC >::ScoreLog2Likelihood(
40        const DBRowGeneratorParser< ALLOC >&                                 parser,
41        const Apriori< ALLOC >&                                              apriori,
42        const std::vector< std::pair< std::size_t, std::size_t >,
43                           ALLOC< std::pair< std::size_t, std::size_t > > >& ranges,
44        const Bijection< NodeId, std::size_t, ALLOC< std::size_t > >&        nodeId2columns,
45        const typename ScoreLog2Likelihood< ALLOC >::allocator_type&         alloc) :
46         Score< ALLOC >(parser, apriori, ranges, nodeId2columns, alloc),
47         _internal_apriori_(parser.database(), nodeId2columns) {
48       GUM_CONSTRUCTOR(ScoreLog2Likelihood);
49     }
50 
51 
52     /// default constructor
53     template < template < typename > class ALLOC >
ScoreLog2Likelihood(const DBRowGeneratorParser<ALLOC> & parser,const Apriori<ALLOC> & apriori,const Bijection<NodeId,std::size_t,ALLOC<std::size_t>> & nodeId2columns,const typename ScoreLog2Likelihood<ALLOC>::allocator_type & alloc)54     INLINE ScoreLog2Likelihood< ALLOC >::ScoreLog2Likelihood(
55        const DBRowGeneratorParser< ALLOC >&                          parser,
56        const Apriori< ALLOC >&                                       apriori,
57        const Bijection< NodeId, std::size_t, ALLOC< std::size_t > >& nodeId2columns,
58        const typename ScoreLog2Likelihood< ALLOC >::allocator_type&  alloc) :
59         Score< ALLOC >(parser, apriori, nodeId2columns, alloc),
60         _internal_apriori_(parser.database(), nodeId2columns) {
61       GUM_CONSTRUCTOR(ScoreLog2Likelihood);
62     }
63 
64 
65     /// copy constructor with a given allocator
66     template < template < typename > class ALLOC >
ScoreLog2Likelihood(const ScoreLog2Likelihood<ALLOC> & from,const typename ScoreLog2Likelihood<ALLOC>::allocator_type & alloc)67     INLINE ScoreLog2Likelihood< ALLOC >::ScoreLog2Likelihood(
68        const ScoreLog2Likelihood< ALLOC >&                          from,
69        const typename ScoreLog2Likelihood< ALLOC >::allocator_type& alloc) :
70         Score< ALLOC >(from, alloc),
71         _internal_apriori_(from._internal_apriori_, alloc) {
72       GUM_CONS_CPY(ScoreLog2Likelihood);
73     }
74 
75 
76     /// copy constructor
77     template < template < typename > class ALLOC >
78     INLINE
ScoreLog2Likelihood(const ScoreLog2Likelihood<ALLOC> & from)79        ScoreLog2Likelihood< ALLOC >::ScoreLog2Likelihood(const ScoreLog2Likelihood< ALLOC >& from) :
80         ScoreLog2Likelihood< ALLOC >(from, from.getAllocator()) {}
81 
82 
83     /// move constructor with a given allocator
84     template < template < typename > class ALLOC >
ScoreLog2Likelihood(ScoreLog2Likelihood<ALLOC> && from,const typename ScoreLog2Likelihood<ALLOC>::allocator_type & alloc)85     INLINE ScoreLog2Likelihood< ALLOC >::ScoreLog2Likelihood(
86        ScoreLog2Likelihood< ALLOC >&&                               from,
87        const typename ScoreLog2Likelihood< ALLOC >::allocator_type& alloc) :
88         Score< ALLOC >(std::move(from), alloc),
89         _internal_apriori_(std::move(from._internal_apriori_), alloc) {
90       GUM_CONS_MOV(ScoreLog2Likelihood);
91     }
92 
93 
94     /// move constructor
95     template < template < typename > class ALLOC >
ScoreLog2Likelihood(ScoreLog2Likelihood<ALLOC> && from)96     INLINE ScoreLog2Likelihood< ALLOC >::ScoreLog2Likelihood(ScoreLog2Likelihood< ALLOC >&& from) :
97         ScoreLog2Likelihood< ALLOC >(std::move(from), from.getAllocator()) {}
98 
99 
100     /// virtual copy constructor with a given allocator
101     template < template < typename > class ALLOC >
clone(const typename ScoreLog2Likelihood<ALLOC>::allocator_type & alloc)102     ScoreLog2Likelihood< ALLOC >* ScoreLog2Likelihood< ALLOC >::clone(
103        const typename ScoreLog2Likelihood< ALLOC >::allocator_type& alloc) const {
104       ALLOC< ScoreLog2Likelihood< ALLOC > > allocator(alloc);
105       ScoreLog2Likelihood< ALLOC >*         new_score = allocator.allocate(1);
106       try {
107         allocator.construct(new_score, *this, alloc);
108       } catch (...) {
109         allocator.deallocate(new_score, 1);
110         throw;
111       }
112 
113       return new_score;
114     }
115 
116 
117     /// virtual copy constructor
118     template < template < typename > class ALLOC >
clone()119     ScoreLog2Likelihood< ALLOC >* ScoreLog2Likelihood< ALLOC >::clone() const {
120       return clone(this->getAllocator());
121     }
122 
123 
124     /// destructor
125     template < template < typename > class ALLOC >
~ScoreLog2Likelihood()126     ScoreLog2Likelihood< ALLOC >::~ScoreLog2Likelihood() {
127       GUM_DESTRUCTOR(ScoreLog2Likelihood);
128     }
129 
130 
131     /// copy operator
132     template < template < typename > class ALLOC >
133     ScoreLog2Likelihood< ALLOC >&
134        ScoreLog2Likelihood< ALLOC >::operator=(const ScoreLog2Likelihood< ALLOC >& from) {
135       if (this != &from) {
136         Score< ALLOC >::operator=(from);
137         _internal_apriori_      = from._internal_apriori_;
138       }
139       return *this;
140     }
141 
142 
143     /// move operator
144     template < template < typename > class ALLOC >
145     ScoreLog2Likelihood< ALLOC >&
146        ScoreLog2Likelihood< ALLOC >::operator=(ScoreLog2Likelihood< ALLOC >&& from) {
147       if (this != &from) {
148         Score< ALLOC >::operator=(std::move(from));
149         _internal_apriori_      = std::move(from._internal_apriori_);
150       }
151       return *this;
152     }
153 
154 
155     /// indicates whether the apriori is compatible (meaningful) with the score
156     template < template < typename > class ALLOC >
isAprioriCompatible(const std::string & apriori_type,double weight)157     std::string ScoreLog2Likelihood< ALLOC >::isAprioriCompatible(const std::string& apriori_type,
158                                                                   double             weight) {
159       // check that the apriori is compatible with the score
160       if ((apriori_type == AprioriDirichletType::type)
161           || (apriori_type == AprioriSmoothingType::type)
162           || (apriori_type == AprioriNoAprioriType::type)) {
163         return "";
164       }
165 
166       // apriori types unsupported by the type checker
167       std::stringstream msg;
168       msg << "The apriori '" << apriori_type
169           << "' is not yet compatible with the score 'Log2Likelihood'.";
170       return msg.str();
171     }
172 
173 
174     /// indicates whether the apriori is compatible (meaningful) with the score
175     template < template < typename > class ALLOC >
176     INLINE std::string
isAprioriCompatible(const Apriori<ALLOC> & apriori)177            ScoreLog2Likelihood< ALLOC >::isAprioriCompatible(const Apriori< ALLOC >& apriori) {
178       return isAprioriCompatible(apriori.getType(), apriori.weight());
179     }
180 
181 
182     /// indicates whether the apriori is compatible (meaningful) with the score
183     template < template < typename > class ALLOC >
isAprioriCompatible()184     INLINE std::string ScoreLog2Likelihood< ALLOC >::isAprioriCompatible() const {
185       return isAprioriCompatible(*(this->apriori_));
186     }
187 
188 
189     /// returns the internal apriori of the score
190     template < template < typename > class ALLOC >
internalApriori()191     INLINE const Apriori< ALLOC >& ScoreLog2Likelihood< ALLOC >::internalApriori() const {
192       return _internal_apriori_;
193     }
194 
195 
196     /// returns the score corresponding to a given nodeset
197     template < template < typename > class ALLOC >
score_(const IdCondSet<ALLOC> & idset)198     double ScoreLog2Likelihood< ALLOC >::score_(const IdCondSet< ALLOC >& idset) {
199       // get the counts for all the nodes in the idset and add the apriori
200       std::vector< double, ALLOC< double > > N_ijk(this->counter_.counts(idset, true));
201       const bool informative_external_apriori = this->apriori_->isInformative();
202       if (informative_external_apriori) this->apriori_->addAllApriori(idset, N_ijk);
203 
204       // here, we distinguish idsets with conditioning nodes from those
205       // without conditioning nodes
206       if (idset.hasConditioningSet()) {
207         // get the counts for the conditioning nodes
208         std::vector< double, ALLOC< double > > N_ij(this->marginalize_(idset[0], N_ijk));
209 
210         // compute the score: it remains to compute the log likelihood, i.e.,
211         // sum_k=1^r_i sum_j=1^q_i N_ijk log (N_ijk / N_ij), which is also
212         // equivalent to:
213         // sum_j=1^q_i sum_k=1^r_i N_ijk log N_ijk - sum_j=1^q_i N_ij log N_ij
214         double score = 0.0;
215         for (const auto n_ijk: N_ijk) {
216           if (n_ijk) { score += n_ijk * std::log(n_ijk); }
217         }
218         for (const auto n_ij: N_ij) {
219           if (n_ij) { score -= n_ij * std::log(n_ij); }
220         }
221 
222         // divide by log(2), since the log likelihood uses log_2
223         score *= this->one_log2_;
224 
225         return score;
226       } else {
227         // here, there are no conditioning nodes
228 
229         // compute the score: it remains to compute the log likelihood, i.e.,
230         // sum_k=1^r_i N_ijk log (N_ijk / N), which is also
231         // equivalent to:
232         // sum_j=1^q_i sum_k=1^r_i N_ijk log N_ijk - N log N
233         double N     = 0.0;
234         double score = 0.0;
235         for (const auto n_ijk: N_ijk) {
236           if (n_ijk) {
237             score += n_ijk * std::log(n_ijk);
238             N += n_ijk;
239           }
240         }
241         score -= N * std::log(N);
242 
243         // divide by log(2), since the log likelihood uses log_2
244         score *= this->one_log2_;
245 
246         return score;
247       }
248     }
249 
250 
251     /// returns the score corresponding to a given nodeset
252     template < template < typename > class ALLOC >
score(const IdCondSet<ALLOC> & idset)253     INLINE double ScoreLog2Likelihood< ALLOC >::score(const IdCondSet< ALLOC >& idset) {
254       return score_(idset);
255     }
256 
257 
258   } /* namespace learning */
259 
260 } /* namespace gum */
261 
262 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
263