Zoltán Szabó avatar Zoltán Szabó committed e640efa

Phi-entropy (f-entropy) estimation based on the spacing method, Pearson chi square divergence (chi square distance) estimation based on k-nearest neighbors: added; see 'HPhi_spacing_initialization.m', 'HPhi_spacing_estimation.m', 'DChiSquare_kNN_k_initialization.m', 'DChiSquare_kNN_k_estimation.m'. Quick tests covering the estimators: introduced ('quick_test_HPhi.m', 'quick_test_DChiSquare.m'), updated accordingly ('quick_test_Dequality.m').

Comments (0)

Files changed (9)

+v0.46 (Oct 21, 2013):
+-Phi-entropy (f-entropy) estimation based on the spacing method: added; see 'HPhi_spacing_initialization.m', 'HPhi_spacing_estimation.m'.
+-Pearson chi square divergence (chi square distance) estimation based on k-nearest neighbors: added; see 'DChiSquare_kNN_k_initialization.m', 'DChiSquare_kNN_k_estimation.m'.
+-Quick test for Phi-entropy and Pearson chi square divergence: introduced; see 'quick_test_HPhi.m', 'quick_test_DChiSquare.m'.
+-Quick test 'quick_test_Dequality.m': updated to cover Pearson chi square divergence.
+
 v0.45 (Oct 9, 2013):
 -Exponentiated Jensen-Tsallis kernel estimators based on Tsallis entropy and Jensen-Tsallis divergence: added; see 'KEJT1_HT_initialization.m', 'KEJT1_HT_estimation.m', 'KEJT2_DJT_initialization.m', 'KEJT2_DJT_estimation.m'.
 -Quick tests for the exponentiated Jensen-Tsallis kernel estimators: added, see 'quick_test_EJT1.m', 'quick_test_KEJT2.m'. 'quick_test_Kpos_semidef.m': changed to cover the 2 new distribution kernel estimators.
 
 ITE can estimate 
 
-- `entropy (H)`: Shannon entropy, R�nyi entropy, Tsallis entropy (Havrda and Charv�t entropy), complex entropy,
+- `entropy (H)`: Shannon entropy, R�nyi entropy, Tsallis entropy (Havrda and Charv�t entropy), complex entropy, Phi-entropy (f-entropy),
 - `mutual information (I)`: generalized variance, kernel canonical correlation analysis, kernel generalized variance, Hilbert-Schmidt independence criterion, Shannon mutual information (total correlation, multi-information), L2 mutual information, R�nyi mutual information, Tsallis mutual information, copula-based kernel dependency, multivariate version of Hoeffding's Phi, Schweizer-Wolff's sigma and kappa, complex mutual information, Cauchy-Schwartz quadratic mutual information, Euclidean distance based quadratic mutual information, distance covariance, distance correlation, approximate correntropy independence measure,
-- `divergence (D)`: Kullback-Leibler divergence (relative entropy, I directed divergence), L2 divergence, R�nyi divergence, Tsallis divergence, Hellinger distance, Bhattacharyya distance, maximum mean discrepancy (kernel distance), J-distance (symmetrised Kullback-Leibler divergence, J divergence), Cauchy-Schwartz divergence, Euclidean distance based divergence, energy distance (specially the Cramer-Von Mises distance), Jensen-Shannon divergence, Jensen-R�nyi divergence, K divergence, L divergence, certain f-divergences (Csisz�r-Morimoto divergence, Ali-Silvey distance), non-symmetric Bregman distance (Bregman divergence), Jensen-Tsallis divergence, symmetric Bregman distance,
+- `divergence (D)`: Kullback-Leibler divergence (relative entropy, I directed divergence), L2 divergence, R�nyi divergence, Tsallis divergence, Hellinger distance, Bhattacharyya distance, maximum mean discrepancy (kernel distance), J-distance (symmetrised Kullback-Leibler divergence, J divergence), Cauchy-Schwartz divergence, Euclidean distance based divergence, energy distance (specially the Cramer-Von Mises distance), Jensen-Shannon divergence, Jensen-R�nyi divergence, K divergence, L divergence, certain f-divergences (Csisz�r-Morimoto divergence, Ali-Silvey distance), non-symmetric Bregman distance (Bregman divergence), Jensen-Tsallis divergence, symmetric Bregman distance, Pearson chi square divergence (chi square distance),
 - `association measures (A)`, including `measures of concordance`: multivariate extensions of Spearman's rho (Spearman's rank correlation coefficient, grade correlation coefficient), correntropy, centered correntropy, correntropy coefficient, correntropy induced metric, centered correntropy induced metric, multivariate extension of Blomqvist's beta (medial correlation coefficient), multivariate conditional version of Spearman's rho, lower/upper tail dependence via conditional Spearman's rho,
 - `cross quantities (C)`: cross-entropy,
 - `kernels on distributions (K)`: expected kernel, Bhattacharyya kernel, probability product kernel, Jensen-Shannon kernel, exponentiated Jensen-Shannon kernel, Jensen-Tsallis kernel, exponentiated Jensen-Renyi kernel(s), exponentiated Jensen-Tsallis kernel(s).
 
 **Download** the latest release: 
 
-- code: [zip](https://bitbucket.org/szzoli/ite/downloads/ITE-0.45_code.zip), [tar.bz2](https://bitbucket.org/szzoli/ite/downloads/ITE-0.45_code.tar.bz2), 
-- [documentation (pdf)](https://bitbucket.org/szzoli/ite/downloads/ITE-0.45_documentation.pdf).
+- code: [zip](https://bitbucket.org/szzoli/ite/downloads/ITE-0.46_code.zip), [tar.bz2](https://bitbucket.org/szzoli/ite/downloads/ITE-0.46_code.tar.bz2), 
+- [documentation (pdf)](https://bitbucket.org/szzoli/ite/downloads/ITE-0.46_documentation.pdf).
 
 

code/estimators/base_estimators/DChiSquare_kNN_k_estimation.m

+function [D] = DChiSquare_kNN_k_estimation(Y1,Y2,co)
+%function [D] = DChiSquare_kNN_k_estimation(Y1,Y2,co)
+%Estimates the Pearson chi square divergence (D) of Y1 and Y2 using the kNN method (S={k}). 
+%
+%We use the naming convention 'D<name>_estimation' to ease embedding new divergence estimation methods.
+%
+%INPUT:
+%  Y1: Y1(:,t) is the t^th sample from the first distribution.
+%  Y2: Y2(:,t) is the t^th sample from the second distribution. Note: the number of samples in Y1 [=size(Y1,2)] and Y2 [=size(Y2,2)] can be different.
+%  co: divergence estimator object.
+%
+%REFERENCE: 
+%   Barnabas Poczos, Liang Xiong, Dougal Sutherland, and Jeff Schneider. Support distribution machines. Technical Report, Carnegie Mellon University, 2012. http://arxiv.org/abs/1202.0302. (estimation: Dtemp2 below)
+%   Karl Pearson. On the criterion that a given system of deviations from the probable in the case of correlated system of variables is such that it can be reasonable supposed to have arisen from random sampling. Philosophical Magazine Series, 50:157-172, 1900.
+
+%Copyright (C) 2013 Zoltan Szabo ("http://www.gatsby.ucl.ac.uk/~szabo/", "zoltan (dot) szabo (at) gatsby (dot) ucl (dot) ac (dot) uk")
+%
+%This file is part of the ITE (Information Theoretical Estimators) Matlab/Octave toolbox.
+%
+%ITE 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.
+%
+%This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
+%MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
+%
+%You should have received a copy of the GNU General Public License along with ITE. If not, see <http://www.gnu.org/licenses/>.
+
+%co.mult:OK. The information theoretical quantity of interest can be (and is!) estimated exactly [co.mult=1]; the computational complexity of the estimation is essentially the same as that of the 'up to multiplicative constant' case [co.mult=0].
+
+[dY1,num_of_samplesY1] = size(Y1);
+[dY2,num_of_samplesY2] = size(Y2);
+
+%verification:
+    if dY1~=dY2
+        error('The dimension of the samples in Y1 and Y2 must be equal.');
+    end
+    
+if co.p %[p(x)dx]
+    D = estimate_Dtemp2(Y1,Y2,co) - 1;
+else %[q(x)dx]
+    D = estimate_Dtemp2(Y2,Y1,co) - 1;
+end
+

code/estimators/base_estimators/DChiSquare_kNN_k_initialization.m

+function [co] = DChiSquare_kNN_k_initialization(mult,post_init)
+%function [co] = DChiSquare_kNN_k_initialization(mult)
+%function [co] = DChiSquare_kNN_k_initialization(mult,post_init)
+%Initialization of the kNN (k-nearest neighbor, S={k}) based Pearson chi square divergence estimator.
+%
+%Note:
+%   1)The estimator is treated as a cost object (co).
+%   2)We use the naming convention 'D<name>_initialization' to ease embedding new divergence estimation methods.
+%
+%INPUT:
+%   mult: is a multiplicative constant relevant (needed) in the estimation; '=1' means yes, '=0' no.
+%   post_init: {field_name1,field_value1,field_name2,field_value2,...}; cell array containing the names and the values of the cost object fields that are to be used
+%   (instead of their default values). For further details, see 'post_initialization.m'.
+%OUTPUT:
+%   co: cost object (structure).
+
+%Copyright (C) 2013 Zoltan Szabo ("http://www.gatsby.ucl.ac.uk/~szabo/", "zoltan (dot) szabo (at) gatsby (dot) ucl (dot) ac (dot) uk")
+%
+%This file is part of the ITE (Information Theoretical Estimators) Matlab/Octave toolbox.
+%
+%ITE 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.
+%
+%This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
+%MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
+%
+%You should have received a copy of the GNU General Public License along with ITE. If not, see <http://www.gnu.org/licenses/>.
+
+%mandatory fields (following the template structure of the estimators to make uniform usage of the estimators possible):
+    co.name = 'ChiSquare_kNN_k';
+    co.mult = mult;
+    
+%other fields:
+    %Possibilities for 'co.kNNmethod' (see 'kNN_squared_distances.m'): 
+        %I: 'knnFP1': fast pairwise distance computation and C++ partial sort; parameter: co.k.                
+        %II: 'knnFP2': fast pairwise distance computation; parameter: co.k. 						
+        %III: 'knnsearch' (Matlab Statistics Toolbox): parameters: co.k, co.NSmethod ('kdtree' or 'exhaustive').
+        %IV: 'ANN' (approximate nearest neighbor); parameters: co.k, co.epsi. 
+		%I:
+            co.kNNmethod = 'knnFP1';
+            co.k = 3;%k-nearest neighbors				
+		%II:
+            %co.kNNmethod = 'knnFP2';
+            %co.k = 3;%k-nearest neighbors				
+        %III:
+            %co.kNNmethod = 'knnsearch';
+            %co.k = 3;%k-nearest neighbors
+            %co.NSmethod = 'kdtree';
+        %IV:
+            %co.kNNmethod = 'ANN';
+            %co.k = 3;%k-nearest neighbors
+            %co.epsi = 0; %=0: exact kNN; >0: approximate kNN, the true (not squared) distances can not exceed the real distance more than a factor of (1+epsi).
+	%Possibilities for rewriting the Chi^2 distance:
+		%I [\int p^2(x)q^{-1}(x)dx - 1 = \int p^1(x)q^{-1}(x) p(x)dx - 1]:
+			co.p = 1; %use p [p(x)dx]
+		%II [\int p^2(x)q^{-1}(x)dx - 1= \int q^{-2}(x)p^2(x) q(x)dx -1]:
+			%co.p = 0; %use q instead [q(x)dx]
+        %fixed, do not change it (co.p => co.a, co.b):
+            if co.p
+                co.a = 1; 
+                co.b = -1;
+            else
+                co.a = -2;
+                co.b = 2;
+            end
+
+%initialize the ann wrapper in Octave, if needed:
+    initialize_Octave_ann_wrapper_if_needed(co.kNNmethod);
+
+%post initialization (put it _before_ initialization of the members in case of a meta estimator):    
+    if nargin==2 %there are given (name,value) cost object fields
+        co = post_initialization(co,post_init);
+    end     

code/estimators/base_estimators/HPhi_spacing_estimation.m

+function [H] = HPhi_spacing_estimation(Y,co)
+%function [H] = HPhi_spacing_estimation(Y,co)
+%Estimates the Phi-entropy (H) of Y using the spacing method.
+%
+%We use the naming convention 'H<name>_estimation' to ease embedding new entropy estimation methods.
+%
+%INPUT:
+%   Y: Y(:,t) is the t^th sample.
+%  co: entropy estimator object.
+%
+%REFERENCE: 
+%  Bert van Es. Estimating Functionals Related to a Density by a Class of Statistics Based on Spacings. Scandinavian Journal of Statistics, 19:61-72, 1992.
+
+%Copyright (C) 2013 Zoltan Szabo ("http://www.gatsby.ucl.ac.uk/~szabo/", "zoltan (dot) szabo (at) gatsby (dot) ucl (dot) ac (dot) uk")
+%
+%This file is part of the ITE (Information Theoretical Estimators) Matlab/Octave toolbox.
+%
+%ITE 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.
+%
+%This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
+%MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+%
+%You should have received a copy of the GNU General Public License along with ITE. If not, see <http://www.gnu.org/licenses/>.
+
+%co.mult:OK. The information theoretical quantity of interest can be (and is!) estimated exactly [co.mult=1]; the computational complexity of the estimation is essentially the same as that of the 'up to multiplicative constant' case [co.mult=0].
+
+[d,num_of_samples] = size(Y);
+
+%verification:
+    if d~=1
+        error('The samples must be one-dimensional for this estimator.');
+    end
+
+m = floor(sqrt(num_of_samples));%m/num_of_samples->0; m/log(num_of_samples)->infty; m,num_of_samples->infty
+Y_sorted = sort(Y);
+
+Y1 = Y_sorted(1:num_of_samples-m); %y_{(1)},...,y_{(T-m)}
+Y2 = Y_sorted(m+1:end); %y_{(m+1)},...,y_{(T)}
+
+H = mean(co.Phi((m/(num_of_samples+1)) ./(Y2-Y1)) .* (co.w(Y1) + co.w(Y2))) / 2;

code/estimators/base_estimators/HPhi_spacing_initialization.m

+function [co] = HPhi_spacing_initialization(mult,post_init)
+%function [co] = HPhi_spacing_initialization(mult)
+%function [co] = HPhi_spacing_initialization(mult,post_init)
+%Initialization of the spacing method based Phi-entropy estimator.
+%
+%Note:
+%   1)The estimator is treated as a cost object (co).
+%   2)We use the naming convention 'H<name>_initialization' to ease embedding new entropy estimation methods.
+%
+%INPUT:
+%   mult: is a multiplicative constant relevant (needed) in the estimation; '=1' means yes, '=0' no.
+%   post_init: {field_name1,field_value1,field_name2,field_value2,...}; cell array containing the names and the values of the cost object fields that are to be used
+%   (instead of their default values). For further details, see 'post_initialization.m'.
+%OUTPUT:
+%   co: cost object (structure).
+
+%Copyright (C) 2013 Zoltan Szabo ("http://www.gatsby.ucl.ac.uk/~szabo/", "zoltan (dot) szabo (at) gatsby (dot) ucl (dot) ac (dot) uk")
+%
+%This file is part of the ITE (Information Theoretical Estimators) Matlab/Octave toolbox.
+%
+%ITE 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.
+%
+%This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
+%MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+%
+%You should have received a copy of the GNU General Public License along with ITE. If not, see <http://www.gnu.org/licenses/>.
+
+%mandatory fields (following the template structure of the estimators to make uniform usage of the estimators possible):
+    co.name = 'Phi_spacing';
+    co.mult = mult;
+    
+%other fields:  
+    co.w = @(t)(1); %weight
+    co.Phi = @(t)(t.^2); %Phi in the Phi-entropy
+    
+%post initialization (put it _before_ initialization of the members in case of a meta estimator):    
+    if nargin==2 %there are given (name,value) cost object fields
+        co = post_initialization(co,post_init);
+    end      
+            

code/estimators/quick_tests/quick_test_DChiSquare.m

+%function [] = quick_test_DChiSquare()
+%Quick test for (Pearson) chi^2 divergence estimators: analytical expression vs estimated value as a function of the sample number. In the test, uniform variables are considered.
+
+%Copyright (C) 2013 Zoltan Szabo ("http://www.gatsby.ucl.ac.uk/~szabo/", "zoltan (dot) szabo (at) gatsby (dot) ucl (dot) ac (dot) uk")
+%
+%This file is part of the ITE (Information Theoretical Estimators) Matlab/Octave toolbox.
+%
+%ITE 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.
+%
+%This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
+%MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+%
+%You should have received a copy of the GNU General Public License along with ITE. If not, see <http://www.gnu.org/licenses/>.
+
+%clear start:
+    clear all; close all;
+    
+%parameters:  
+    distr = 'uniform'; %fixed
+    d = 1; %dimension of the distribution
+    num_of_samples_v = [1000:1000:50*1000]; %sample numbers used for estimation
+    %estimator (for the chi^2 divergence), base:
+        cost_name = 'ChiSquare_kNN_k';
+        
+%initialization:    
+    L = length(num_of_samples_v);    
+    co = D_initialization(cost_name,1);
+    D_hat_v = zeros(L,1);  %vector of estimated divergence values
+    num_of_samples_max = num_of_samples_v(end);  
+    
+%generate samples (Y1<<Y2), analytical value (D):
+   switch distr
+        case 'uniform'
+            b = 3*rand(d,1);
+            a = b.*rand(d,1);
+            Y1 = rand(d,num_of_samples_max) .* repmat(a,1,num_of_samples_max); %~U[0,a]
+            Y2 = rand(d,num_of_samples_max) .* repmat(b,1,num_of_samples_max); %U[0,b], a<=b (coordinate-wise) => Y1<<Y2
+            %analytical value (of chi^2 divergence):
+                D = prod(b)/prod(a) - 1;
+        otherwise
+            error('Distribution=?');                 
+   end
+    
+%estimation:
+    Tk = 0;%index of the sample number examined   
+    for num_of_samples = num_of_samples_v
+        Tk = Tk + 1;
+        D_hat_v(Tk) = D_estimation(Y1(:,1:num_of_samples),Y2(:,1:num_of_samples),co);
+        disp(strcat('Tk=',num2str(Tk),'/',num2str(L)));
+    end
+    
+%plot:
+    plot(num_of_samples_v,D_hat_v,'r',num_of_samples_v,D*ones(1,L),'g');
+    legend({'estimation','analytical value'});
+    xlabel('Number of samples (T)');
+    ylabel('\chi^2 divergence');
+        

code/estimators/quick_tests/quick_test_Dequality.m

              %cost_name = 'EnergyDist';
              %cost_name = 'Bregman_kNN_k';
              %cost_name = 'symBregman_kNN_k';
+             %cost_name = 'ChiSquare_kNN_k';
         %meta:
              %cost_name = 'Jdistance';        
              %cost_name = 'KL_CCE_HShannon';

code/estimators/quick_tests/quick_test_HPhi.m

+%function [] = quick_test_HPhi()
+%Quick test for Phi-entropy estimators: analytical expression vs estimated value as a function of the sample number. In the test, uniform variables are considered.
+
+%Copyright (C) 2013 Zoltan Szabo ("http://www.gatsby.ucl.ac.uk/~szabo/", "zoltan (dot) szabo (at) gatsby (dot) ucl (dot) ac (dot) uk")
+%
+%This file is part of the ITE (Information Theoretical Estimators) Matlab/Octave toolbox.
+%
+%ITE 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.
+%
+%This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
+%MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+%
+%You should have received a copy of the GNU General Public License along with ITE. If not, see <http://www.gnu.org/licenses/>.
+
+%clear start:
+    clear all; close all;
+
+%parameters:
+    distr = 'uniform'; %fixed
+    %Phi (in the Phi-entropy):
+        c = 2; %>=1; c is also used in the analytical expression: 'H = ...'
+        Phi = @(t)(t.^c);
+    num_of_samples_v = [1000:1000:100*1000]; %sample numbers used for estimation
+    %estimator (of Phi-entropy), base:
+        %base:
+            cost_name = 'Phi_spacing'; %d=1
+    
+%initialization:  
+    d = 1;%dimension of the distribution
+    num_of_samples_max = num_of_samples_v(end);
+    L = length(num_of_samples_v);
+    co = H_initialization(cost_name,1,{'Phi',Phi}); %{'Phi',Phi}: we also set the Phi function here
+    H_hat_v = zeros(L,1);%vector of estimated entropies
+    
+%distr -> samples (Y), analytical formula for the entropy (H):
+    switch distr 
+        case 'uniform'
+            %U[a,b]:
+                a = rand; b = a + 4*rand;%guaranteed that a<=b
+            %generate samples:
+                Y =  (b-a) * rand(1,num_of_samples_max) + a;
+            %analytical value of the Phi-entropy:
+                H = 1 / (b-a)^c; 
+        otherwise
+            error('Distribution=?');
+    end  
+
+%estimation:
+    Tk = 0;%index of the sample number examined
+    for num_of_samples = num_of_samples_v
+        Tk = Tk + 1;
+        H_hat_v(Tk) = H_estimation(Y(:,1:num_of_samples),co);
+        disp(strcat('Tk=',num2str(Tk),'/',num2str(L)));
+    end
+    
+%plot:
+    plot(num_of_samples_v,H_hat_v,'r',num_of_samples_v,H*ones(L,1),'g');
+    legend({'estimation','analytical value'});
+    xlabel('Number of samples');
+    ylabel('\Phi-entropy');
+
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.