fn_decode_codeword.hpp

Go to the documentation of this file.

// Copyright (C) 2011 the authors listed below
// http://ecocpak.sourceforge.net
//
// Authors:
// - Dimitrios Bouzas (bouzas at ieee dot org)
// - Nikolaos Arvanitopoulos (niarvani at ieee dot org)
// - Anastasios Tefas (tefas at aiia dot csd dot auth dot gr)
//
// This file is part of the ECOC PAK C++ library. It is
// provided without any warranty of fitness for any purpose.
//
// You can redistribute this file and/or modify it under
// the terms of the GNU Lesser General Public License (LGPL)
// as published by the Free Software Foundation, either
// version 3 of the License or (at your option) any later
// version.
// (see http://www.opensource.org/licenses for more info)





irowvec
sign(const rowvec& A)
  {
  const u32 n_elem = A.n_elem;

  irowvec out;
  out.set_size(n_elem);

  for(u32 i = 0; i < n_elem; i++)
    {
    if(A[i] < 0)
      {
      out[i] = -1;
      }
    else
      {
      if(A[i] > 0)
        {
        out[i] = 1;
        }
      else
        {
        out[i] = 0;
        }

      }

    }

  return out;
  }



irowvec
sign(const rowvec& A, const irowvec& B)
  {
  const u32 n_elem = A.n_elem;

  irowvec out;
  out.set_size(n_elem);

  for(u32 i = 0; i < n_elem; i++)
    {
    double tmp = A[i] * B[i];

    if(tmp < 0)
      {
      out[i] = -1;
      }
    else
      {
      if(tmp > 0)
        {
        out[i] = 1;
        }
      else
        {
        out[i] = 0;
        }

      }

    }

  return out;
  }



double
beta_density_metric
  (
  const irowvec& test_code,
  const irowvec& class_code,
  const double   u = 0.333333,
  const u32      n_points = 201
  )
  {
  // generate distribution curve and auxiliary curves
  vec distr_curve = linspace<vec>(0, 1, n_points);
  vec distr_curve_flipped = flipud(distr_curve);
  vec distr_curve_half = 0.5 * distr_curve;

  vec y_s;

  // initialization step
  if(test_code[0] == class_code[0])
    {
    y_s = distr_curve_half;
    }
  else
    {
    if(class_code[0] == 0)
      {
      y_s = ones<vec>(n_points);
      }
    else
      {
      y_s = distr_curve_flipped;
      }

    }

  for(u32 i = 1; i < test_code.n_elem; i++)
    {
    if(test_code[i] == class_code[i])
      {
      y_s = y_s % distr_curve_half;
      }
    else
      {
      if(test_code[i] != 0)
        {
        y_s = y_s % distr_curve_flipped;
        }

      }

    }

  // find y_s maximum and its associated index
  uvec inds = sort_index(y_s, 1);
  double maximum = max(y_s);

  // initialize counts
  int count_left = 1;

  const double required_area = accu(y_s) * u;

  while(maximum < required_area)
    {

    int tmp_ind = inds[0] - count_left;

    if(tmp_ind > 0)
      {
      maximum += y_s[tmp_ind];
      count_left++;
      }
    else
      {
      break;
      }

    }

  count_left++;

  if(count_left > inds[0])
    {
    (inds[0] != 0)?count_left = inds[0] : count_left = 0;
    }

  // return computed distance
  return 1.0 - distr_curve[inds[0] - count_left];
  }



u32
decode_codeword
  (
  const rowvec& codeword,
  const imat& coding_matrix,
  const int decoding_strategy
  )
  {
  // used to hold the winning label (i.e., the class which has the
  // closest codeword to current testing sample's codeword)
  u32 winning_class_index = 0;

  // coding matrix number of rows
  const u32 n_rows = coding_matrix.n_rows;

  // coding matrix number of columns
  const u32 n_cols = coding_matrix.n_cols;

  // decode according to user entered decoding strategy option
  switch(decoding_strategy)
    {
    // Hamming Decoding
    case HAMMING:
      {
      // compute Hamming distance of sample's codeword from
      // first class codeword -- distance is interpreted
      // as a similarity measure (i.e., the larger max_similarity
      // gets the closer the sample's codeword to current class
      // codeword)
      double hamming_distance =
        accu((1 - sign(codeword, coding_matrix.row(0)))) / 2.0;

      // initialize winning label to first class label
      winning_class_index = 1;

      // compare sample's codeword with rest classes codewords
      // and use hamming decoding to compute the closest
      // class codeword
      for(u32 j = 1; j < n_rows; j++)
        {
        // compute current Hamming distance
        double tmp_hamming_distance =
          accu((1 - sign(codeword, coding_matrix.row(j)))) / 2.0;

        // update maximum
        if(tmp_hamming_distance < hamming_distance)
          {
          hamming_distance = tmp_hamming_distance;
          winning_class_index = j + 1;
          }
        else
          {
          // in ties random assignment for unbiased estimation
          if(tmp_hamming_distance == hamming_distance)
            {
            if((std::rand() % 2) == 0)
              {
              hamming_distance = tmp_hamming_distance;
              winning_class_index = j + 1;
              }

            }

          }

        }

      break;
      }

    // Euclidean Decoding
    case EUCLIDEAN:
      {
      // compute Euclidean distance of sample's codeword from
      // first class codeword
      double euclidean_distance =
        norm
          (
          conv_to<rowvec>::from(sign(codeword)) -
          conv_to<rowvec>::from(coding_matrix.row(0)),
          2
          );

      // initialize winning label to first class label
      winning_class_index = 1;

      // compare sample's codeword with rest classes codewords
      // and use euclidean decoding to compute the closest
      // class codeword
      for(u32 j = 1; j < n_rows; j++)
        {
        // compute current Euclidean distance
        double tmp_euclidean_distance =
          norm
            (
            conv_to<rowvec>::from(sign(codeword)) -
            conv_to<rowvec>::from(coding_matrix.row(j)),
            2
            );

        // update maximum
        if(tmp_euclidean_distance < euclidean_distance)
          {
          euclidean_distance = tmp_euclidean_distance;
          winning_class_index = j + 1;
          }
        else
          {
          // in ties random assignment for unbiased estimation
          if(tmp_euclidean_distance == euclidean_distance)
            {
            if((std::rand() % 2) == 0)
              {
              euclidean_distance = tmp_euclidean_distance;
              winning_class_index = j + 1;
              }

            }

          }

        }

      break;
      }

    // Laplacian Decoding
    case LAPLACIAN:
      {
      // number of matchings
      u32 n_matchings = accu(sign(codeword) == coding_matrix.row(0));
      double laplacian_decoding_value =
        (n_matchings + accu(sign(codeword) !=
        coding_matrix.row(0)) + 2) / double(n_matchings + 1);

      // initialize winning label to first class label
      winning_class_index = 1;

      // compare sample's codeword with rest classes codewords
      // and use laplacian decoding to compute the closest
      // class codeword
      for(u32 j = 1; j < n_rows; j++)
        {
        // compute current Laplacian decoding value
        n_matchings = accu(sign(codeword) == coding_matrix.row(j));
        double tmp_laplacian_decoding_value =
          double(n_matchings + accu(sign(codeword) !=
          coding_matrix.row(j)) + 2) / double(n_matchings + 1);

        // update maximum
        if(tmp_laplacian_decoding_value < laplacian_decoding_value)
          {
          laplacian_decoding_value = tmp_laplacian_decoding_value;
          winning_class_index = j + 1;
          }
        else
          {
          // in ties random assignment for unbiased estimation
          if(tmp_laplacian_decoding_value == laplacian_decoding_value)
            {
            if((std::rand() % 2) == 0)
              {
              laplacian_decoding_value = tmp_laplacian_decoding_value;
              winning_class_index = j + 1;
              }

            }

          }

        }

      break;
      }

    // Hamming Attenuated Decoding
    case HAMMING_ATTENUATED:
      {
      // compute decoding value
      double decoding_value =
        accu(abs(coding_matrix.row(0)) % abs(sign(codeword)) %
        abs(coding_matrix.row(0) - sign(codeword))) / 2.0;

      // initialize winning label to first class label
      winning_class_index = 1;

      // compare sample's codeword with rest classes codewords
      // and use hamming attenuated decoding to compute the closest
      // class codeword
      for(u32 j = 1; j < n_rows; j++)
        {
        // compute current decoding value
        double tmp_decoding_value =
          accu(abs(coding_matrix.row(j)) % abs(sign(codeword)) %
          abs(coding_matrix.row(j) - sign(codeword))) / 2.0;

        // update maximum
        if(tmp_decoding_value < decoding_value)
          {
          decoding_value = tmp_decoding_value;
          winning_class_index = j + 1;
          }
        else
          {
          // in ties random assignment for unbiased estimation
          if(tmp_decoding_value == decoding_value)
            {
            if((std::rand() % 2) == 0)
              {
              decoding_value = tmp_decoding_value;
              winning_class_index = j + 1;
              }

            }

          }

        }

      break;
      }

    // Euclidean Attenuated Decoding
    case EUCLIDEAN_ATTENUATED:
      {
      // compute decoding value
      double decoding_value =
        std::sqrt(accu(abs(coding_matrix.row(0)) % pow(sign(codeword)
        - coding_matrix.row(0), 2)));

      // initialize winning label to first class label
      winning_class_index = 1;

      // compare sample's codeword with rest classes codewords
      // and use euclidean decoding to compute the closest
      // class codeword
      for(u32 j = 1; j < n_rows; j++)
        {
        // compute current decoding value
        double tmp_decoding_value =
          std::sqrt(accu(abs(coding_matrix.row(j)) % pow(sign(codeword)
          - coding_matrix.row(j), 2)));

        // update maximum
        if(tmp_decoding_value < decoding_value)
          {
          decoding_value = tmp_decoding_value;
          winning_class_index = j + 1;
          }
        else
          {
          // in ties random assignment for unbiased estimation
          if(tmp_decoding_value == decoding_value)
            {
            if((std::rand() % 2) == 0)
              {
              decoding_value = tmp_decoding_value;
              winning_class_index = j + 1;
              }

            }

          }

        }

      break;
      }

    // Linear Loss Based Decoding
    case LINEAR_LOSS_BASED_DECODING:
      {
      // number of matchings
      double decoding_value =
        -1.0 *
        accu(codeword % conv_to<rowvec>::from(coding_matrix.row(0)));

      // initialize winning label to first class label
      winning_class_index = 1;

      // compare sample's codeword with rest classes codewords
      // and use linear loss based decoding to compute the closest
      // class codeword
      for(u32 j = 1; j < n_rows; j++)
        {
        // compute current decoding value
        double tmp_decoding_value =
          -1.0 *
          accu(codeword % conv_to<rowvec>::from(coding_matrix.row(j)));

        // update maximum
        if(tmp_decoding_value < decoding_value)
          {
          decoding_value = tmp_decoding_value;
          winning_class_index = j + 1;
          }
        else
          {
          // in ties random assignment for unbiased estimation
          if(tmp_decoding_value == decoding_value)
            {
            if((std::rand() % 2) == 0)
              {
              decoding_value = tmp_decoding_value;
              winning_class_index = j + 1;
              }

            }

          }

        }

      break;
      }

    // Linear Loss Based Decoding
    case EXPONENTIAL_LOSS_BASED_DECODING:
      {
      // decoding value - distance
      double decoding_value =
        accu
          (
          exp
            (
            -1.0 *
            (codeword % conv_to<rowvec>::from(coding_matrix.row(0)))
            )
          );

      // initialize winning label to first class label
      winning_class_index = 1;

      // compare sample's codeword with rest classes codewords
      // and use exponential loss based decoding to compute the closest
      // class codeword
      for(u32 j = 1; j < n_rows; j++)
        {
        // compute current decoding value
        double tmp_decoding_value =
          accu
            (
            exp
              (
              -1.0 *
              (codeword % conv_to<rowvec>::from(coding_matrix.row(j)))
              )
            );

        // update maximum
        if(tmp_decoding_value < decoding_value)
          {
          decoding_value = tmp_decoding_value;
          winning_class_index = j + 1;
          }
        else
          {
          // in ties random assignment for unbiased estimation
          if(tmp_decoding_value == decoding_value)
            {
            if((std::rand() % 2) == 0)
              {
              decoding_value = tmp_decoding_value;
              winning_class_index = j + 1;
              }

            }

          }

        }

      break;
      }

    case BETA_DENSITY_DECODING:
      {
      // decoding value - distance
      double decoding_value =
        beta_density_metric
          (
          sign(codeword),
          coding_matrix.row(0)
          );

      // initialize winning label to first class label
      winning_class_index = 1;

      // compare sample's codeword with rest classes codewords
      // and use exponential loss based decoding to compute the closest
      // class codeword
      for(u32 j = 1; j < n_rows; j++)
        {
        // compute current decoding value
        double tmp_decoding_value =
          beta_density_metric
            (
            sign(codeword),
            coding_matrix.row(j)
            );

        // update maximum
        if(tmp_decoding_value < decoding_value)
          {
          decoding_value = tmp_decoding_value;
          winning_class_index = j + 1;
          }
        else
          {
          // in ties random assignment for unbiased estimation
          if(tmp_decoding_value == decoding_value)
            {
            if((std::rand() % 2) == 0)
              {
              decoding_value = tmp_decoding_value;
              winning_class_index = j + 1;
              }

            }

          }

        }

      break;
      }

    // Inverse Hamming Decoding
    case INVERSE_HAMMING_DECODING:
      {
      mat delta = zeros<mat>(n_rows, n_rows);

      for(u32 i = 0; i < n_rows; i++)
        {
        for(u32 j = 0; j < n_rows; j++)
          {
          delta(i,j) = accu(abs(coding_matrix.row(i) - coding_matrix.row(j))) / 2.0;
          }

        }

      colvec L = zeros<colvec>(n_rows);

      // iterate to fill in values of L
      for(u32 i = 0; i < n_rows; i++)
        {
        L(i) = accu(abs(codeword - coding_matrix.row(i))) / 2.0;
        }

      // add some noise in the diagonal for robustness
      delta.diag() += (10e-15 * ones<vec>(n_rows,1));

      // compute the weight vector
      colvec q = solve(delta, L);

      // sort q in descending order to find maximum index
      uvec indices = sort_index(q, 1);

      // assign winning class label
      winning_class_index = indices[0] + 1;

      break;
      }

    default:
      {
      arma_debug_print("decode_codeword(): Unknown Decoding Option");
      }

    }

  return winning_class_index;
  }