Kernel.h

Go to the documentation of this file.

/*
 * EXCEPT FOR THE KERNEL CACHING FUNCTIONS WHICH ARE (W) THORSTEN JOACHIMS
 * COPYRIGHT (C) 1999  UNIVERSITAET DORTMUND - ALL RIGHTS RESERVED
 *
 * this program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Written (W) 1999-2009 Soeren Sonnenburg
 * Written (W) 1999-2008 Gunnar Raetsch
 * Copyright (C) 1999-2009 Fraunhofer Institute FIRST and Max-Planck-Society
 */

#ifndef _KERNEL_H___
#define _KERNEL_H___

#include <shogun/lib/config.h>

#include <shogun/lib/common.h>
#include <shogun/lib/Signal.h>
#include <shogun/io/SGIO.h>
#include <shogun/io/File.h>
#include <shogun/mathematics/Math.h>
#include <shogun/features/FeatureTypes.h>
#include <shogun/base/SGObject.h>
#include <shogun/lib/SGMatrix.h>
#include <shogun/features/Features.h>
#include <shogun/kernel/normalizer/KernelNormalizer.h>

namespace shogun
{
    class CFile;
    class CFeatures;
    class CKernelNormalizer;

#ifdef USE_SHORTREAL_KERNELCACHE

    typedef float32_t KERNELCACHE_ELEM;
#else

    typedef float64_t KERNELCACHE_ELEM;
#endif

typedef int64_t KERNELCACHE_IDX;


enum EOptimizationType
{
    FASTBUTMEMHUNGRY,
    SLOWBUTMEMEFFICIENT
};

enum EKernelType
{
    K_UNKNOWN = 0,
    K_LINEAR = 10,
    K_POLY = 20,
    K_GAUSSIAN = 30,
    K_GAUSSIANSHIFT = 32,
    K_GAUSSIANMATCH = 33,
    K_HISTOGRAM = 40,
    K_SALZBERG = 41,
    K_LOCALITYIMPROVED = 50,
    K_SIMPLELOCALITYIMPROVED = 60,
    K_FIXEDDEGREE = 70,
    K_WEIGHTEDDEGREE =    80,
    K_WEIGHTEDDEGREEPOS = 81,
    K_WEIGHTEDDEGREERBF = 82,
    K_WEIGHTEDCOMMWORDSTRING = 90,
    K_POLYMATCH = 100,
    K_ALIGNMENT = 110,
    K_COMMWORDSTRING = 120,
    K_COMMULONGSTRING = 121,
    K_SPECTRUMRBF = 122,
    K_SPECTRUMMISMATCHRBF = 123,
    K_COMBINED = 140,
    K_AUC = 150,
    K_CUSTOM = 160,
    K_SIGMOID = 170,
    K_CHI2 = 180,
    K_DIAG = 190,
    K_CONST = 200,
    K_DISTANCE = 220,
    K_LOCALALIGNMENT = 230,
    K_PYRAMIDCHI2 = 240,
    K_OLIGO = 250,
    K_MATCHWORD = 260,
    K_TPPK = 270,
    K_REGULATORYMODULES = 280,
    K_SPARSESPATIALSAMPLE = 290,
    K_HISTOGRAMINTERSECTION = 300,
    K_WAVELET = 310,
    K_WAVE = 320,
    K_CAUCHY = 330,
    K_TSTUDENT = 340,
    K_RATIONAL_QUADRATIC = 350,
    K_MULTIQUADRIC = 360,
    K_EXPONENTIAL = 370,
    K_SPHERICAL = 380,
    K_SPLINE = 390,
    K_ANOVA = 400,
    K_POWER = 410,
    K_LOG = 420,
    K_CIRCULAR = 430,
    K_INVERSEMULTIQUADRIC = 440,
    K_DISTANTSEGMENTS = 450,
    K_BESSEL = 460,
    K_JENSENSHANNON = 470,
    K_DIRECTOR = 480,
    K_PRODUCT = 490,
    K_EXPONENTIALARD = 500,
    K_GAUSSIANARD = 510,
    K_GAUSSIANARDSPARSE = 511,
    K_STREAMING = 520,
    K_PERIODIC = 530
};

enum EKernelProperty
{
    KP_NONE = 0,
    KP_LINADD = 1,  // Kernels that can be optimized via doing normal updates w + dw
    KP_KERNCOMBINATION = 2, // Kernels that are infact a linear combination of subkernels K=\sum_i b_i*K_i
    KP_BATCHEVALUATION = 4  // Kernels that can on the fly generate normals in linadd and more quickly/memory efficient process batches instead of single examples
};

class CSVM;

class CKernel : public CSGObject
{
    friend class CVarianceKernelNormalizer;
    friend class CSqrtDiagKernelNormalizer;
    friend class CAvgDiagKernelNormalizer;
    friend class CRidgeKernelNormalizer;
    friend class CFirstElementKernelNormalizer;
    friend class CMultitaskKernelNormalizer;
    friend class CMultitaskKernelMklNormalizer;
    friend class CMultitaskKernelMaskNormalizer;
    friend class CMultitaskKernelMaskPairNormalizer;
    friend class CTanimotoKernelNormalizer;
    friend class CDiceKernelNormalizer;
    friend class CZeroMeanCenterKernelNormalizer;

    friend class CStreamingKernel;

    public:

        CKernel();


        CKernel(int32_t size);

        CKernel(CFeatures* l, CFeatures* r, int32_t size);

        virtual ~CKernel();

        inline float64_t kernel(int32_t idx_a, int32_t idx_b)
        {
            REQUIRE(idx_a>=0 && idx_b>=0 && idx_a<num_lhs && idx_b<num_rhs,
                "%s::kernel(): index out of Range: idx_a=%d/%d idx_b=%d/%d\n",
                get_name(), idx_a,num_lhs, idx_b,num_rhs);

            return normalizer->normalize(compute(idx_a, idx_b), idx_a, idx_b);
        }

        SGMatrix<float64_t> get_kernel_matrix()
        {
            return get_kernel_matrix<float64_t>();
        }

        SGVector<float64_t> get_kernel_diagonal(SGVector<float64_t>
                preallocated=SGVector<float64_t>())
        {
            REQUIRE(lhs, "CKernel::get_kernel_diagonal(): Left-handside "
                    "features missing!\n");

            REQUIRE(rhs, "CKernel::get_kernel_diagonal(): Right-handside "
                        "features missing!\n");

            int32_t length=CMath::min(lhs->get_num_vectors(),rhs->get_num_vectors());

            /* allocate space if necessary */
            if (!preallocated.vector)
                preallocated=SGVector<float64_t>(length);
            else
            {
                REQUIRE(preallocated.vlen==length,
                        "%s::get_kernel_diagonal(): Preallocated vector has"
                        " wrong size!\n", get_name());
            }

            for (index_t i=0; i<preallocated.vlen; ++i)
                preallocated[i]=kernel(i, i);

            return preallocated;
        }

        virtual SGVector<float64_t> get_kernel_col(int32_t j)
        {

            SGVector<float64_t> col = SGVector<float64_t>(num_rhs);

            for (int32_t i=0; i!=num_rhs; i++)
                col[i] = kernel(i,j);

            return col;
        }


        virtual SGVector<float64_t> get_kernel_row(int32_t i)
        {
            SGVector<float64_t> row = SGVector<float64_t>(num_lhs);

            for (int32_t j=0; j!=num_lhs; j++)
                row[j] = kernel(i,j);

            return row;
        }

        virtual float64_t sum_symmetric_block(index_t block_begin,
                index_t block_size, bool no_diag=true);

        virtual float64_t sum_block(index_t block_begin_row,
                index_t block_begin_col, index_t block_size_row,
                index_t block_size_col, bool no_diag=false);

        virtual SGVector<float64_t> row_wise_sum_symmetric_block(index_t
                block_begin, index_t block_size, bool no_diag=true);

        virtual SGMatrix<float64_t> row_wise_sum_squared_sum_symmetric_block(
                index_t block_begin, index_t block_size, bool no_diag=true);

        virtual SGVector<float64_t> row_col_wise_sum_block(
                index_t block_begin_row, index_t block_begin_col,
                index_t block_size_row, index_t block_size_col,
                bool no_diag=false);

        template <class T> SGMatrix<T> get_kernel_matrix();

        virtual bool init(CFeatures* lhs, CFeatures* rhs);

        virtual bool set_normalizer(CKernelNormalizer* normalizer);

        virtual CKernelNormalizer* get_normalizer();

        virtual bool init_normalizer();

        virtual void cleanup();

        void load(CFile* loader);

        void save(CFile* writer);

        inline CFeatures* get_lhs() { SG_REF(lhs); return lhs; }

        inline CFeatures* get_rhs() { SG_REF(rhs); return rhs; }

        virtual int32_t get_num_vec_lhs()
        {
            return num_lhs;
        }

        virtual int32_t get_num_vec_rhs()
        {
            return num_rhs;
        }

        virtual bool has_features()
        {
            return lhs && rhs;
        }

        inline bool get_lhs_equals_rhs()
        {
            return lhs_equals_rhs;
        }

        virtual void remove_lhs_and_rhs();

        virtual void remove_lhs();

        virtual void remove_rhs();

        virtual EKernelType get_kernel_type()=0 ;

        virtual EFeatureType get_feature_type()=0;

        virtual EFeatureClass get_feature_class()=0;

        inline void set_cache_size(int32_t size)
        {
            cache_size = size;
#ifdef USE_SVMLIGHT
            cache_reset();
#endif //USE_SVMLIGHT
        }

        inline int32_t get_cache_size() { return cache_size; }

#ifdef USE_SVMLIGHT

        inline void cache_reset() { resize_kernel_cache(cache_size); }

        inline int32_t get_max_elems_cache() { return kernel_cache.max_elems; }

        inline int32_t get_activenum_cache() { return kernel_cache.activenum; }

        void get_kernel_row(
            int32_t docnum, int32_t *active2dnum, float64_t *buffer,
            bool full_line=false);

        void cache_kernel_row(int32_t x);

        void cache_multiple_kernel_rows(int32_t* key, int32_t varnum);

        void kernel_cache_reset_lru();

        void kernel_cache_shrink(
            int32_t totdoc, int32_t num_shrink, int32_t *after);

        void resize_kernel_cache(KERNELCACHE_IDX size,
            bool regression_hack=false);

        inline void set_time(int32_t t)
        {
            kernel_cache.time=t;
        }

        inline int32_t kernel_cache_touch(int32_t cacheidx)
        {
            if(kernel_cache.index[cacheidx] != -1)
            {
                kernel_cache.lru[kernel_cache.index[cacheidx]]=kernel_cache.time;
                return(1);
            }
            return(0);
        }

        inline int32_t kernel_cache_check(int32_t cacheidx)
        {
            return(kernel_cache.index[cacheidx] >= 0);
        }

        inline int32_t kernel_cache_space_available()
        {
            return(kernel_cache.elems < kernel_cache.max_elems);
        }

        void kernel_cache_init(int32_t size, bool regression_hack=false);

        void kernel_cache_cleanup();

#endif //USE_SVMLIGHT

        void list_kernel();

        inline bool has_property(EKernelProperty p) { return (properties & p) != 0; }

        virtual void clear_normal();

        virtual void add_to_normal(int32_t vector_idx, float64_t weight);

        inline EOptimizationType get_optimization_type() { return opt_type; }

        virtual void set_optimization_type(EOptimizationType t) { opt_type=t;}

        inline bool get_is_initialized() { return optimization_initialized; }

        virtual bool init_optimization(
            int32_t count, int32_t *IDX, float64_t *weights);

        virtual bool delete_optimization();

        bool init_optimization_svm(CSVM * svm) ;

        virtual float64_t compute_optimized(int32_t vector_idx);

        virtual void compute_batch(
            int32_t num_vec, int32_t* vec_idx, float64_t* target,
            int32_t num_suppvec, int32_t* IDX, float64_t* alphas,
            float64_t factor=1.0);

        inline float64_t get_combined_kernel_weight() { return combined_kernel_weight; }

        inline void set_combined_kernel_weight(float64_t nw) { combined_kernel_weight=nw; }

        virtual int32_t get_num_subkernels();

        virtual void compute_by_subkernel(
            int32_t vector_idx, float64_t * subkernel_contrib);

        virtual const float64_t* get_subkernel_weights(int32_t& num_weights);

        virtual SGVector<float64_t> get_subkernel_weights();

        virtual void set_subkernel_weights(SGVector<float64_t> weights);

        virtual SGMatrix<float64_t> get_parameter_gradient(
                const TParameter* param, index_t index=-1)
        {
            SG_ERROR("Can't compute derivative wrt %s parameter\n", param->m_name)
            return SGMatrix<float64_t>();
        }

        virtual SGVector<float64_t> get_parameter_gradient_diagonal(
                const TParameter* param, index_t index=-1)
        {
            return get_parameter_gradient(param,index).get_diagonal_vector();
        }

        static CKernel* obtain_from_generic(CSGObject* kernel);
    protected:
        inline void set_property(EKernelProperty p)
        {
            properties |= p;
        }

        inline void unset_property(EKernelProperty p)
        {
            properties &= (properties | p) ^ p;
        }

        inline void set_is_initialized(bool p_init) { optimization_initialized=p_init; }

        virtual float64_t compute(int32_t x, int32_t y)=0;

        int32_t compute_row_start(int64_t offs, int32_t n, bool symmetric)
        {
            int32_t i_start;

            if (symmetric)
                i_start=(int32_t) CMath::floor(n-CMath::sqrt(CMath::sq((float64_t) n)-offs));
            else
                i_start=(int32_t) (offs/int64_t(n));

            return i_start;
        }

        template <class T> static void* get_kernel_matrix_helper(void* p);

        virtual void load_serializable_post() throw (ShogunException);

        virtual void save_serializable_pre() throw (ShogunException);

        virtual void save_serializable_post() throw (ShogunException);

        virtual void register_params();

    private:
        void init();


#ifdef USE_SVMLIGHT
#ifndef DOXYGEN_SHOULD_SKIP_THIS

        struct KERNEL_CACHE {
            int32_t   *index;
            int32_t   *invindex;
            int32_t   *active2totdoc;
            int32_t   *totdoc2active;
            int32_t   *lru;
            int32_t   *occu;
            int32_t   elems;
            int32_t   max_elems;
            int32_t   time;
            int32_t   activenum;

            KERNELCACHE_ELEM  *buffer;
            KERNELCACHE_IDX   buffsize;
        };

        struct S_KTHREAD_PARAM
        {
            CKernel* kernel;
            KERNEL_CACHE* kernel_cache;
            KERNELCACHE_ELEM** cache;
            int32_t* uncached_rows;
            int32_t num_uncached;
            uint8_t* needs_computation;
            int32_t start;
            int32_t end;
            int32_t num_vectors;
        };
#endif // DOXYGEN_SHOULD_SKIP_THIS

        static void* cache_multiple_kernel_row_helper(void* p);

        void   kernel_cache_free(int32_t cacheidx);
        int32_t   kernel_cache_malloc();
        int32_t   kernel_cache_free_lru();
        KERNELCACHE_ELEM *kernel_cache_clean_and_malloc(int32_t cacheidx);
#endif //USE_SVMLIGHT


    protected:
        int32_t cache_size;

#ifdef USE_SVMLIGHT
        KERNEL_CACHE kernel_cache;
#endif //USE_SVMLIGHT

        KERNELCACHE_ELEM* kernel_matrix;

        CFeatures* lhs;
        CFeatures* rhs;

        bool lhs_equals_rhs;

        int32_t num_lhs;
        int32_t num_rhs;

        float64_t combined_kernel_weight;

        bool optimization_initialized;
        EOptimizationType opt_type;

        uint64_t  properties;

        CKernelNormalizer* normalizer;
};

}
#endif /* _KERNEL_H__ */