ECOCPAK v0.9
fn_decode_codeword.hpp
Go to the documentation of this file.
00001 // Copyright (C) 2011 the authors listed below
00002 // http://ecocpak.sourceforge.net
00003 //
00004 // Authors:
00005 // - Dimitrios Bouzas (bouzas at ieee dot org)
00006 // - Nikolaos Arvanitopoulos (niarvani at ieee dot org)
00007 // - Anastasios Tefas (tefas at aiia dot csd dot auth dot gr)
00008 //
00009 // This file is part of the ECOC PAK C++ library. It is
00010 // provided without any warranty of fitness for any purpose.
00011 //
00012 // You can redistribute this file and/or modify it under
00013 // the terms of the GNU Lesser General Public License (LGPL)
00014 // as published by the Free Software Foundation, either
00015 // version 3 of the License or (at your option) any later
00016 // version.
00017 // (see http://www.opensource.org/licenses for more info)
00018 
00019 
00022 
00023 
00024 
00038 irowvec
00039 sign(const rowvec& A)
00040   {
00041   const u32 n_elem = A.n_elem;
00042 
00043   irowvec out;
00044   out.set_size(n_elem);
00045 
00046   for(u32 i = 0; i < n_elem; i++)
00047     {
00048     if(A[i] < 0)
00049       {
00050       out[i] = -1;
00051       }
00052     else
00053       {
00054       if(A[i] > 0)
00055         {
00056         out[i] = 1;
00057         }
00058       else
00059         {
00060         out[i] = 0;
00061         }
00062 
00063       }
00064 
00065     }
00066 
00067   return out;
00068   }
00069 
00070 
00071 
00087 irowvec
00088 sign(const rowvec& A, const irowvec& B)
00089   {
00090   const u32 n_elem = A.n_elem;
00091 
00092   irowvec out;
00093   out.set_size(n_elem);
00094 
00095   for(u32 i = 0; i < n_elem; i++)
00096     {
00097     double tmp = A[i] * B[i];
00098 
00099     if(tmp < 0)
00100       {
00101       out[i] = -1;
00102       }
00103     else
00104       {
00105       if(tmp > 0)
00106         {
00107         out[i] = 1;
00108         }
00109       else
00110         {
00111         out[i] = 0;
00112         }
00113 
00114       }
00115 
00116     }
00117 
00118   return out;
00119   }
00120 
00121 
00122 
00140 double
00141 beta_density_metric
00142   (
00143   const irowvec& test_code,
00144   const irowvec& class_code,
00145   const double   u = 0.333333,
00146   const u32      n_points = 201
00147   )
00148   {
00149   // generate distribution curve and auxiliary curves
00150   vec distr_curve = linspace<vec>(0, 1, n_points);
00151   vec distr_curve_flipped = flipud(distr_curve);
00152   vec distr_curve_half = 0.5 * distr_curve;
00153 
00154   vec y_s;
00155 
00156   // initialization step
00157   if(test_code[0] == class_code[0])
00158     {
00159     y_s = distr_curve_half;
00160     }
00161   else
00162     {
00163     if(class_code[0] == 0)
00164       {
00165       y_s = ones<vec>(n_points);
00166       }
00167     else
00168       {
00169       y_s = distr_curve_flipped;
00170       }
00171 
00172     }
00173 
00174   for(u32 i = 1; i < test_code.n_elem; i++)
00175     {
00176     if(test_code[i] == class_code[i])
00177       {
00178       y_s = y_s % distr_curve_half;
00179       }
00180     else
00181       {
00182       if(test_code[i] != 0)
00183         {
00184         y_s = y_s % distr_curve_flipped;
00185         }
00186 
00187       }
00188 
00189     }
00190 
00191   // find y_s maximum and its associated index
00192   uvec inds = sort_index(y_s, 1);
00193   double maximum = max(y_s);
00194 
00195   // initialize counts
00196   int count_left = 1;
00197 
00198   const double required_area = accu(y_s) * u;
00199 
00200   while(maximum < required_area)
00201     {
00202 
00203     int tmp_ind = inds[0] - count_left;
00204 
00205     if(tmp_ind > 0)
00206       {
00207       maximum += y_s[tmp_ind];
00208       count_left++;
00209       }
00210     else
00211       {
00212       break;
00213       }
00214 
00215     }
00216 
00217   count_left++;
00218 
00219   if(count_left > inds[0])
00220     {
00221     (inds[0] != 0)?count_left = inds[0] : count_left = 0;
00222     }
00223 
00224   // return computed distance
00225   return 1.0 - distr_curve[inds[0] - count_left];
00226   }
00227 
00228 
00229 
00250 u32
00251 decode_codeword
00252   (
00253   const rowvec& codeword,
00254   const imat& coding_matrix,
00255   const int decoding_strategy
00256   )
00257   {
00258   // used to hold the winning label (i.e., the class which has the
00259   // closest codeword to current testing sample's codeword)
00260   u32 winning_class_index = 0;
00261 
00262   // coding matrix number of rows
00263   const u32 n_rows = coding_matrix.n_rows;
00264 
00265   // coding matrix number of columns
00266   const u32 n_cols = coding_matrix.n_cols;
00267 
00268   // decode according to user entered decoding strategy option
00269   switch(decoding_strategy)
00270     {
00271     // Hamming Decoding
00272     case HAMMING:
00273       {
00274       // compute Hamming distance of sample's codeword from
00275       // first class codeword -- distance is interpreted
00276       // as a similarity measure (i.e., the larger max_similarity
00277       // gets the closer the sample's codeword to current class
00278       // codeword)
00279       double hamming_distance =
00280         accu((1 - sign(codeword, coding_matrix.row(0)))) / 2.0;
00281 
00282       // initialize winning label to first class label
00283       winning_class_index = 1;
00284 
00285       // compare sample's codeword with rest classes codewords
00286       // and use hamming decoding to compute the closest
00287       // class codeword
00288       for(u32 j = 1; j < n_rows; j++)
00289         {
00290         // compute current Hamming distance
00291         double tmp_hamming_distance =
00292           accu((1 - sign(codeword, coding_matrix.row(j)))) / 2.0;
00293 
00294         // update maximum
00295         if(tmp_hamming_distance < hamming_distance)
00296           {
00297           hamming_distance = tmp_hamming_distance;
00298           winning_class_index = j + 1;
00299           }
00300         else
00301           {
00302           // in ties random assignment for unbiased estimation
00303           if(tmp_hamming_distance == hamming_distance)
00304             {
00305             if((std::rand() % 2) == 0)
00306               {
00307               hamming_distance = tmp_hamming_distance;
00308               winning_class_index = j + 1;
00309               }
00310 
00311             }
00312 
00313           }
00314 
00315         }
00316 
00317       break;
00318       }
00319 
00320     // Euclidean Decoding
00321     case EUCLIDEAN:
00322       {
00323       // compute Euclidean distance of sample's codeword from
00324       // first class codeword
00325       double euclidean_distance =
00326         norm
00327           (
00328           conv_to<rowvec>::from(sign(codeword)) -
00329           conv_to<rowvec>::from(coding_matrix.row(0)),
00330           2
00331           );
00332 
00333       // initialize winning label to first class label
00334       winning_class_index = 1;
00335 
00336       // compare sample's codeword with rest classes codewords
00337       // and use euclidean decoding to compute the closest
00338       // class codeword
00339       for(u32 j = 1; j < n_rows; j++)
00340         {
00341         // compute current Euclidean distance
00342         double tmp_euclidean_distance =
00343           norm
00344             (
00345             conv_to<rowvec>::from(sign(codeword)) -
00346             conv_to<rowvec>::from(coding_matrix.row(j)),
00347             2
00348             );
00349 
00350         // update maximum
00351         if(tmp_euclidean_distance < euclidean_distance)
00352           {
00353           euclidean_distance = tmp_euclidean_distance;
00354           winning_class_index = j + 1;
00355           }
00356         else
00357           {
00358           // in ties random assignment for unbiased estimation
00359           if(tmp_euclidean_distance == euclidean_distance)
00360             {
00361             if((std::rand() % 2) == 0)
00362               {
00363               euclidean_distance = tmp_euclidean_distance;
00364               winning_class_index = j + 1;
00365               }
00366 
00367             }
00368 
00369           }
00370 
00371         }
00372 
00373       break;
00374       }
00375 
00376     // Laplacian Decoding
00377     case LAPLACIAN:
00378       {
00379       // number of matchings
00380       u32 n_matchings = accu(sign(codeword) == coding_matrix.row(0));
00381       double laplacian_decoding_value =
00382         (n_matchings + accu(sign(codeword) !=
00383         coding_matrix.row(0)) + 2) / double(n_matchings + 1);
00384 
00385       // initialize winning label to first class label
00386       winning_class_index = 1;
00387 
00388       // compare sample's codeword with rest classes codewords
00389       // and use laplacian decoding to compute the closest
00390       // class codeword
00391       for(u32 j = 1; j < n_rows; j++)
00392         {
00393         // compute current Laplacian decoding value
00394         n_matchings = accu(sign(codeword) == coding_matrix.row(j));
00395         double tmp_laplacian_decoding_value =
00396           double(n_matchings + accu(sign(codeword) !=
00397           coding_matrix.row(j)) + 2) / double(n_matchings + 1);
00398 
00399         // update maximum
00400         if(tmp_laplacian_decoding_value < laplacian_decoding_value)
00401           {
00402           laplacian_decoding_value = tmp_laplacian_decoding_value;
00403           winning_class_index = j + 1;
00404           }
00405         else
00406           {
00407           // in ties random assignment for unbiased estimation
00408           if(tmp_laplacian_decoding_value == laplacian_decoding_value)
00409             {
00410             if((std::rand() % 2) == 0)
00411               {
00412               laplacian_decoding_value = tmp_laplacian_decoding_value;
00413               winning_class_index = j + 1;
00414               }
00415 
00416             }
00417 
00418           }
00419 
00420         }
00421 
00422       break;
00423       }
00424 
00425     // Hamming Attenuated Decoding
00426     case HAMMING_ATTENUATED:
00427       {
00428       // compute decoding value
00429       double decoding_value =
00430         accu(abs(coding_matrix.row(0)) % abs(sign(codeword)) %
00431         abs(coding_matrix.row(0) - sign(codeword))) / 2.0;
00432 
00433       // initialize winning label to first class label
00434       winning_class_index = 1;
00435 
00436       // compare sample's codeword with rest classes codewords
00437       // and use hamming attenuated decoding to compute the closest
00438       // class codeword
00439       for(u32 j = 1; j < n_rows; j++)
00440         {
00441         // compute current decoding value
00442         double tmp_decoding_value =
00443           accu(abs(coding_matrix.row(j)) % abs(sign(codeword)) %
00444           abs(coding_matrix.row(j) - sign(codeword))) / 2.0;
00445 
00446         // update maximum
00447         if(tmp_decoding_value < decoding_value)
00448           {
00449           decoding_value = tmp_decoding_value;
00450           winning_class_index = j + 1;
00451           }
00452         else
00453           {
00454           // in ties random assignment for unbiased estimation
00455           if(tmp_decoding_value == decoding_value)
00456             {
00457             if((std::rand() % 2) == 0)
00458               {
00459               decoding_value = tmp_decoding_value;
00460               winning_class_index = j + 1;
00461               }
00462 
00463             }
00464 
00465           }
00466 
00467         }
00468 
00469       break;
00470       }
00471 
00472     // Euclidean Attenuated Decoding
00473     case EUCLIDEAN_ATTENUATED:
00474       {
00475       // compute decoding value
00476       double decoding_value =
00477         std::sqrt(accu(abs(coding_matrix.row(0)) % pow(sign(codeword)
00478         - coding_matrix.row(0), 2)));
00479 
00480       // initialize winning label to first class label
00481       winning_class_index = 1;
00482 
00483       // compare sample's codeword with rest classes codewords
00484       // and use euclidean decoding to compute the closest
00485       // class codeword
00486       for(u32 j = 1; j < n_rows; j++)
00487         {
00488         // compute current decoding value
00489         double tmp_decoding_value =
00490           std::sqrt(accu(abs(coding_matrix.row(j)) % pow(sign(codeword)
00491           - coding_matrix.row(j), 2)));
00492 
00493         // update maximum
00494         if(tmp_decoding_value < decoding_value)
00495           {
00496           decoding_value = tmp_decoding_value;
00497           winning_class_index = j + 1;
00498           }
00499         else
00500           {
00501           // in ties random assignment for unbiased estimation
00502           if(tmp_decoding_value == decoding_value)
00503             {
00504             if((std::rand() % 2) == 0)
00505               {
00506               decoding_value = tmp_decoding_value;
00507               winning_class_index = j + 1;
00508               }
00509 
00510             }
00511 
00512           }
00513 
00514         }
00515 
00516       break;
00517       }
00518 
00519     // Linear Loss Based Decoding
00520     case LINEAR_LOSS_BASED_DECODING:
00521       {
00522       // number of matchings
00523       double decoding_value =
00524         -1.0 *
00525         accu(codeword % conv_to<rowvec>::from(coding_matrix.row(0)));
00526 
00527       // initialize winning label to first class label
00528       winning_class_index = 1;
00529 
00530       // compare sample's codeword with rest classes codewords
00531       // and use linear loss based decoding to compute the closest
00532       // class codeword
00533       for(u32 j = 1; j < n_rows; j++)
00534         {
00535         // compute current decoding value
00536         double tmp_decoding_value =
00537           -1.0 *
00538           accu(codeword % conv_to<rowvec>::from(coding_matrix.row(j)));
00539 
00540         // update maximum
00541         if(tmp_decoding_value < decoding_value)
00542           {
00543           decoding_value = tmp_decoding_value;
00544           winning_class_index = j + 1;
00545           }
00546         else
00547           {
00548           // in ties random assignment for unbiased estimation
00549           if(tmp_decoding_value == decoding_value)
00550             {
00551             if((std::rand() % 2) == 0)
00552               {
00553               decoding_value = tmp_decoding_value;
00554               winning_class_index = j + 1;
00555               }
00556 
00557             }
00558 
00559           }
00560 
00561         }
00562 
00563       break;
00564       }
00565 
00566     // Linear Loss Based Decoding
00567     case EXPONENTIAL_LOSS_BASED_DECODING:
00568       {
00569       // decoding value - distance
00570       double decoding_value =
00571         accu
00572           (
00573           exp
00574             (
00575             -1.0 *
00576             (codeword % conv_to<rowvec>::from(coding_matrix.row(0)))
00577             )
00578           );
00579 
00580       // initialize winning label to first class label
00581       winning_class_index = 1;
00582 
00583       // compare sample's codeword with rest classes codewords
00584       // and use exponential loss based decoding to compute the closest
00585       // class codeword
00586       for(u32 j = 1; j < n_rows; j++)
00587         {
00588         // compute current decoding value
00589         double tmp_decoding_value =
00590           accu
00591             (
00592             exp
00593               (
00594               -1.0 *
00595               (codeword % conv_to<rowvec>::from(coding_matrix.row(j)))
00596               )
00597             );
00598 
00599         // update maximum
00600         if(tmp_decoding_value < decoding_value)
00601           {
00602           decoding_value = tmp_decoding_value;
00603           winning_class_index = j + 1;
00604           }
00605         else
00606           {
00607           // in ties random assignment for unbiased estimation
00608           if(tmp_decoding_value == decoding_value)
00609             {
00610             if((std::rand() % 2) == 0)
00611               {
00612               decoding_value = tmp_decoding_value;
00613               winning_class_index = j + 1;
00614               }
00615 
00616             }
00617 
00618           }
00619 
00620         }
00621 
00622       break;
00623       }
00624 
00625     case BETA_DENSITY_DECODING:
00626       {
00627       // decoding value - distance
00628       double decoding_value =
00629         beta_density_metric
00630           (
00631           sign(codeword),
00632           coding_matrix.row(0)
00633           );
00634 
00635       // initialize winning label to first class label
00636       winning_class_index = 1;
00637 
00638       // compare sample's codeword with rest classes codewords
00639       // and use exponential loss based decoding to compute the closest
00640       // class codeword
00641       for(u32 j = 1; j < n_rows; j++)
00642         {
00643         // compute current decoding value
00644         double tmp_decoding_value =
00645           beta_density_metric
00646             (
00647             sign(codeword),
00648             coding_matrix.row(j)
00649             );
00650 
00651         // update maximum
00652         if(tmp_decoding_value < decoding_value)
00653           {
00654           decoding_value = tmp_decoding_value;
00655           winning_class_index = j + 1;
00656           }
00657         else
00658           {
00659           // in ties random assignment for unbiased estimation
00660           if(tmp_decoding_value == decoding_value)
00661             {
00662             if((std::rand() % 2) == 0)
00663               {
00664               decoding_value = tmp_decoding_value;
00665               winning_class_index = j + 1;
00666               }
00667 
00668             }
00669 
00670           }
00671 
00672         }
00673 
00674       break;
00675       }
00676 
00677     // Inverse Hamming Decoding
00678     case INVERSE_HAMMING_DECODING:
00679       {
00680       mat delta = zeros<mat>(n_rows, n_rows);
00681 
00682       for(u32 i = 0; i < n_rows; i++)
00683         {
00684         for(u32 j = 0; j < n_rows; j++)
00685           {
00686           delta(i,j) = accu(abs(coding_matrix.row(i) - coding_matrix.row(j))) / 2.0;
00687           }
00688 
00689         }
00690 
00691       colvec L = zeros<colvec>(n_rows);
00692 
00693       // iterate to fill in values of L
00694       for(u32 i = 0; i < n_rows; i++)
00695         {
00696         L(i) = accu(abs(codeword - coding_matrix.row(i))) / 2.0;
00697         }
00698 
00699       // add some noise in the diagonal for robustness
00700       delta.diag() += (10e-15 * ones<vec>(n_rows,1));
00701 
00702       // compute the weight vector
00703       colvec q = solve(delta, L);
00704 
00705       // sort q in descending order to find maximum index
00706       uvec indices = sort_index(q, 1);
00707 
00708       // assign winning class label
00709       winning_class_index = indices[0] + 1;
00710 
00711       break;
00712       }
00713 
00714     default:
00715       {
00716       arma_debug_print("decode_codeword(): Unknown Decoding Option");
00717       }
00718 
00719     }
00720 
00721   return winning_class_index;
00722   }
00723 
00724 
00725 
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerator Defines