Changeset 8437

Timestamp:

08/08/12 16:46:53 (12 years ago)

Author:

abeham

Message:

#1913:

• Improved speed of NCA
• Reorganized things

Location:

branches/NCA

Files:

• HeuristicLab.Algorithms.NCA.Tests/MatrixTest.cs (modified) (1 diff)
• HeuristicLab.Algorithms.NCA.Views/3.3/HeuristicLab.Algorithms.NCA.Views-3.3.csproj (modified) (2 diffs)
• HeuristicLab.Algorithms.NCA.Views/3.3/NCADimensionReductionView.Designer.cs (added)
• HeuristicLab.Algorithms.NCA.Views/3.3/NCADimensionReductionView.cs (added)
• HeuristicLab.Algorithms.NCA.Views/3.3/NCADimensionReductionView.resx (added)
• HeuristicLab.Algorithms.NCA.Views/3.3/NCADimensionalityReductionView.Designer.cs (deleted)
• HeuristicLab.Algorithms.NCA.Views/3.3/NCADimensionalityReductionView.cs (deleted)
• HeuristicLab.Algorithms.NCA.Views/3.3/NCADimensionalityReductionView.resx (deleted)
• HeuristicLab.Algorithms.NCA/3.3/Auxiliary.cs (added)
• HeuristicLab.Algorithms.NCA/3.3/HeuristicLab.Algorithms.NCA-3.3.csproj (modified) (2 diffs)
• HeuristicLab.Algorithms.NCA/3.3/INCAClassificationSolution.cs (added)
• HeuristicLab.Algorithms.NCA/3.3/INCAModel.cs (modified) (1 diff)
• HeuristicLab.Algorithms.NCA/3.3/Initialization/RandomInitializer.cs (modified) (1 diff)
• HeuristicLab.Algorithms.NCA/3.3/Matrix.cs (modified) (1 diff)
• HeuristicLab.Algorithms.NCA/3.3/NCA.cs (deleted)
• HeuristicLab.Algorithms.NCA/3.3/NCAClassificationSolution.cs (modified) (1 diff)
• HeuristicLab.Algorithms.NCA/3.3/NCAModel.cs (modified) (1 diff)
• HeuristicLab.Algorithms.NCA/3.3/NeighborhoodComponentsAnalysis.cs (modified) (2 diffs)
• NCA.sln (modified) (4 diffs)

branches/NCA/HeuristicLab.Algorithms.NCA.Tests/MatrixTest.cs

@@ -122 +122 @@
     public void LengthTest() {
       var vector = new double[] { 5, 4, 2, 2 };
-      Assert.AreEqual(new Matrix_Accessor(vector, vector.Length).Length(), 7);
+      Assert.AreEqual(new Matrix_Accessor(vector, vector.Length).VectorLength(), 7);
       vector = new double[] { 5, -4, 2, 2 };
-      Assert.AreEqual(new Matrix_Accessor(vector, vector.Length).Length(), 7);
+      Assert.AreEqual(new Matrix_Accessor(vector, vector.Length).VectorLength(), 7);
       vector = new double[] { 3, 2, 1, 5 };
-      Assert.IsTrue(new Matrix_Accessor(vector, vector.Length).Length().IsAlmost(6.2449979983983982058468931209398));
+      Assert.IsTrue(new Matrix_Accessor(vector, vector.Length).VectorLength().IsAlmost(6.2449979983983982058468931209398));
     }
 

branches/NCA/HeuristicLab.Algorithms.NCA.Views/3.3/HeuristicLab.Algorithms.NCA.Views-3.3.csproj

@@ -168 +168 @@
   <ItemGroup>
     <None Include="Plugin.cs.frame" />
-    <Compile Include="NCADimensionalityReductionView.cs">
+    <Compile Include="NCADimensionReductionView.cs">
       <SubType>UserControl</SubType>
     </Compile>
-    <Compile Include="NCADimensionalityReductionView.Designer.cs">
-      <DependentUpon>NCADimensionalityReductionView.cs</DependentUpon>
+    <Compile Include="NCADimensionReductionView.Designer.cs">
+      <DependentUpon>NCADimensionReductionView.cs</DependentUpon>
     </Compile>
     <Compile Include="Plugin.cs" />
@@ -188 +188 @@
   </ItemGroup>
   <ItemGroup>
-    <EmbeddedResource Include="NCADimensionalityReductionView.resx">
-      <DependentUpon>NCADimensionalityReductionView.cs</DependentUpon>
+    <EmbeddedResource Include="NCADimensionReductionView.resx">
+      <DependentUpon>NCADimensionReductionView.cs</DependentUpon>
     </EmbeddedResource>
   </ItemGroup>

branches/NCA/HeuristicLab.Algorithms.NCA/3.3/HeuristicLab.Algorithms.NCA-3.3.csproj

@@ -99 +99 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="INCAClassificationSolution.cs" />
     <Compile Include="Initialization\INCAInitializer.cs" />
     <Compile Include="INCAModel.cs" />
@@ -105 +106 @@
     <Compile Include="Initialization\RandomInitializer.cs" />
     <Compile Include="Matrix.cs" />
-    <Compile Include="NCA.cs" />
+    <Compile Include="NeighborhoodComponentsAnalysis.cs" />
     <Compile Include="NCAClassificationSolution.cs" />
     <Compile Include="NCAModel.cs" />
-    <Compile Include="NeighborhoodComponentsAnalysis.cs" />
+    <Compile Include="Auxiliary.cs" />
     <Compile Include="Plugin.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />

branches/NCA/HeuristicLab.Algorithms.NCA/3.3/INCAModel.cs

@@ -20 +20 @@
 #endregion
 
+using System.Collections.Generic;
 using HeuristicLab.Problems.DataAnalysis;
 
 namespace HeuristicLab.Algorithms.NCA {
   public interface INCAModel : IClassificationModel {
-    double[,] TransformationMatrix { get; }
+    double[,] Reduce(Dataset dataset, IEnumerable<int> rows);
   }
 }

branches/NCA/HeuristicLab.Algorithms.NCA/3.3/Initialization/RandomInitializer.cs

@@ -74 +74 @@
       var matrix = new double[attributes * dimensions];
       for (int i = 0; i < matrix.Length; i++)
-        matrix[i] = random.NextDouble() * range[i / dimensions];
+        matrix[i] = random.NextDouble() / range[i / dimensions];
 
       return matrix;

branches/NCA/HeuristicLab.Algorithms.NCA/3.3/Matrix.cs

@@ -125 +125 @@
     }
 
-    public double Length() {
+    public double VectorLength() {
+      return Math.Sqrt(SquaredVectorLength());
+    }
+
+    public double SquaredVectorLength() {
       if (Rows != 1) throw new ArgumentException("Length only works on vectors.");
-      return Math.Sqrt(values.Sum(x => x * x));
+      return values.Sum(x => x * x);
     }
 

branches/NCA/HeuristicLab.Algorithms.NCA/3.3/NCAClassificationSolution.cs

@@ -28 +28 @@
   [Item("NCAClassificationSolution", "")]
   [StorableClass]
-  public class NCAClassificationSolution : ClassificationSolution {
+  public class NCAClassificationSolution : ClassificationSolution, INCAClassificationSolution {
 
     public new INCAModel Model {

branches/NCA/HeuristicLab.Algorithms.NCA/3.3/NCAModel.cs

@@ -129 +129 @@
       return CreateClassificationSolution(problemData);
     }
+
+    public double[,] Reduce(Dataset dataset, IEnumerable<int> rows) {
+      var result = new double[rows.Count(), transformationMatrix.GetLength(1)];
+      int v = 0;
+      foreach (var r in rows) {
+        int i = 0;
+        foreach (var variable in allowedInputVariables) {
+          double val = dataset.GetDoubleValue(variable, r);
+          for (int j = 0; j < result.GetLength(1); j++)
+            result[v, j] += val * transformationMatrix[i, j];
+          i++;
+        }
+        v++;
+      }
+      return result;
+    }
   }
 }

branches/NCA/HeuristicLab.Algorithms.NCA/3.3/NeighborhoodComponentsAnalysis.cs

@@ -1 @@
-#region License Information
+#region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
@@ -20 +20 @@
 #endregion
 
-using System;
-using System.Collections.Generic;
 using System.Linq;
+using HeuristicLab.Algorithms.DataAnalysis;
 using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.PluginInfrastructure;
 using HeuristicLab.Problems.DataAnalysis;
 
 namespace HeuristicLab.Algorithms.NCA {
-  public class NeighborhoodComponentsAnalysis {
+  /// <summary>
+  /// Neighborhood Components Analysis
+  /// </summary>
+  [Item("Neighborhood Components Analysis", "NCA is described in J. Goldberger, S. Roweis, G. Hinton, R. Salakhutdinov. 2005. Neighbourhood Component Analysis. Advances in Neural Information Processing Systems, 17. pp. 513-520.")]
+  [Creatable("Data Analysis")]
+  [StorableClass]
+  public sealed class NeighborhoodComponentsAnalysis : FixedDataAnalysisAlgorithm<IClassificationProblem> {
+    #region Parameter Properties
+    public IValueLookupParameter<IntValue> KParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["k"]; }
+    }
+    public IValueLookupParameter<IntValue> ReduceDimensionsParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["ReduceDimensions"]; }
+    }
+    private IConstrainedValueParameter<INCAInitializer> InitializationParameter {
+      get { return (IConstrainedValueParameter<INCAInitializer>)Parameters["Initialization"]; }
+    }
+    #endregion
 
-    public static INCAModel Train(IClassificationProblemData data, int k, int reduceDimensions, INCAInitializer initializer) {
-      var instances = data.TrainingIndices.Count();
-      var attributes = data.AllowedInputVariables.Count();
+    #region Properties
+    public IntValue K {
+      get { return KParameter.Value; }
+    }
+    public IntValue ReduceDimensions {
+      get { return ReduceDimensionsParameter.Value; }
+    }
+    #endregion
 
-      double[] matrix = initializer.Initialize(data, reduceDimensions);
+    [StorableConstructor]
+    private NeighborhoodComponentsAnalysis(bool deserializing) : base(deserializing) { }
+    private NeighborhoodComponentsAnalysis(NeighborhoodComponentsAnalysis original, Cloner cloner) : base(original, cloner) { }
+    public NeighborhoodComponentsAnalysis()
+      : base() {
+      Parameters.Add(new ValueLookupParameter<IntValue>("k", "The k for the nearest neighbor.", new IntValue(1)));
+      Parameters.Add(new ValueLookupParameter<IntValue>("ReduceDimensions", "The number of dimensions that NCA should reduce the data to.", new IntValue(2)));
+      Parameters.Add(new ConstrainedValueParameter<INCAInitializer>("Initialization", "Which method should be used to initialize the matrix. Typically LDA (linear discriminant analysis) should provide a good estimate."));
 
-      alglib.mincgstate state;
-      alglib.mincgreport rep;
+      INCAInitializer defaultInitializer = null;
+      foreach (var initializer in ApplicationManager.Manager.GetInstances<INCAInitializer>().OrderBy(x => x.ItemName)) {
+        if (initializer is LDAInitializer) defaultInitializer = initializer;
+        InitializationParameter.ValidValues.Add(initializer);
+      }
+      if (defaultInitializer != null) InitializationParameter.Value = defaultInitializer;
 
-      // first run
-      alglib.mincgcreate(matrix, out state);
-      alglib.mincgsetcond(state, 0.0000000001, 0, 0, 0);
-      alglib.mincgoptimize(state, Gradient, null, new OptimizationInfo(data, reduceDimensions));
-      alglib.mincgresults(state, out matrix, out rep);
-
-      var transformationMatrix = new double[attributes, reduceDimensions];
-      var counter = 0;
-      for (var i = 0; i < attributes; i++)
-        for (var j = 0; j < reduceDimensions; j++)
-          transformationMatrix[i, j] = matrix[counter++];
-
-      var transformedTrainingset = new double[instances, reduceDimensions];
-      var rowCount = 0;
-      foreach (var r in data.TrainingIndices) {
-        var i = 0;
-        foreach (var v in data.AllowedInputVariables) {
-          var val = data.Dataset.GetDoubleValue(v, r);
-          for (var j = 0; j < reduceDimensions; j++)
-            transformedTrainingset[rowCount, j] += val * transformationMatrix[i, j];
-          i++;
-        }
-        rowCount++;
-      }
-
-      return new NCAModel(transformedTrainingset, transformationMatrix, k, data.TargetVariable, data.AllowedInputVariables,
-        data.Dataset.GetDoubleValues(data.TargetVariable)
-          .Select((v, i) => new { I = i, V = v })
-          .Where(x => x.I >= data.TrainingPartition.Start && x.I < data.TrainingPartition.End
-              && !(x.I >= data.TestPartition.Start && x.I < data.TestPartition.End))
-          .Select(x => x.V).ToArray());
+      Problem = new ClassificationProblem();
     }
 
-    private static void Gradient(double[] A, ref double func, double[] grad, object obj) {
-      var info = (OptimizationInfo)obj;
-      var instances = info.ProblemData.TrainingIndices.ToArray();
-      var attributes = info.ProblemData.AllowedInputVariables.Count();
-      var AMatrix = new Matrix(A, A.Length / info.ReduceDimensions, info.ReduceDimensions);
-
-      alglib.sparsematrix probabilities;
-      alglib.sparsecreate(instances.Length, instances.Length, out probabilities);
-      var distances = new double[instances.Length];
-      for (int i = 0; i < instances.Length - 1; i++) {
-        var iVector = new Matrix(GetRow(info.ProblemData, instances[i]));
-        var denom = 0.0;
-        for (int k = 0; k < instances.Length; k++) {
-          if (k == i) continue;
-          var kVector = new Matrix(GetRow(info.ProblemData, instances[k]));
-          distances[k] = iVector.Multiply(AMatrix).Subtract(kVector.Multiply(AMatrix)).Length();
-          denom += Math.Exp(-(distances[k] * distances[k]));
-        }
-        if (denom > 0) {
-          for (int j = i + 1; j < instances.Length; j++) {
-            if (i == j) continue;
-            var v = Math.Exp(-(distances[j] * distances[j])) / denom;
-            alglib.sparseset(probabilities, i, j, v);
-            alglib.sparseset(probabilities, j, i, v);
-          }
-        }
-      }
-      alglib.sparseconverttocrs(probabilities); // needed to enumerate in order (top-down and left-right)
-
-      int t0 = 0, t1 = 0, r, c;
-      double val;
-      var classes = info.ProblemData.Dataset.GetDoubleValues(info.ProblemData.TargetVariable, instances).ToArray();
-      var pi = new double[instances.Length];
-      while (alglib.sparseenumerate(probabilities, ref t0, ref t1, out r, out c, out val)) {
-        if (classes[r].IsAlmost(classes[c]))
-          pi[r] += val;
-      }
-
-      var innerSum = new double[attributes, attributes];
-      while (alglib.sparseenumerate(probabilities, ref t0, ref t1, out r, out c, out val)) {
-        var vector = new Matrix(GetRow(info.ProblemData, instances[r])).Subtract(new Matrix(GetRow(info.ProblemData, instances[c]))).Apply();
-        vector.OuterProduct(vector).Multiply(val * pi[r]).AddTo(innerSum);
-
-        if (classes[r].IsAlmost(classes[c])) {
-          vector.OuterProduct(vector).Multiply(-val).AddTo(innerSum);
-        }
-      }
-
-      func = -pi.Sum();
-
-      grad = AMatrix.Multiply(-2.0).Transpose().Multiply(new Matrix(innerSum)).Transpose().ToArray();
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new NeighborhoodComponentsAnalysis(this, cloner);
     }
 
-    private static IEnumerable<double> GetRow(IClassificationProblemData data, int row) {
-      return data.AllowedInputVariables.Select(v => data.Dataset.GetDoubleValue(v, row));
+    public override void Prepare() {
+      if (Problem != null) base.Prepare();
     }
 
-    public static NCAClassificationSolution CreateNCASolution(IClassificationProblemData problemData, int k, int reduceDimensions, INCAInitializer initializer) {
-      return new NCAClassificationSolution(problemData, Train(problemData, k, reduceDimensions, initializer));
-    }
+    protected override void Run() {
+      var k = K.Value;
+      var dimensions = ReduceDimensions.Value;
+      var initializer = InitializationParameter.Value;
 
-    private class OptimizationInfo {
-      public IClassificationProblemData ProblemData { get; set; }
-      public int ReduceDimensions { get; set; }
-      public OptimizationInfo(IClassificationProblemData problem, int reduceDimensions) {
-        this.ProblemData = problem;
-        this.ReduceDimensions = reduceDimensions;
-      }
+      var clonedProblem = (IClassificationProblemData)Problem.ProblemData.Clone();
+      var classification = new NCAClassificationSolution(clonedProblem, Auxiliary.Train(clonedProblem, k, dimensions, initializer));
+      Results.Add(new Result("ClassificationSolution", "The classification solution.", classification));
+      // TODO: result that shows the LOO performance
     }
   }

branches/NCA/NCA.sln

@@ -3 +3 @@
 # Visual Studio 2010
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.NCA-3.3", "HeuristicLab.Algorithms.NCA\3.3\HeuristicLab.Algorithms.NCA-3.3.csproj", "{FD81A5D6-051D-4BD1-B2D8-668A820FAD6E}"
-EndProject
-Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.NCA.Views-3.3", "HeuristicLab.Algorithms.NCA.Views\3.3\HeuristicLab.Algorithms.NCA.Views-3.3.csproj", "{07654A26-5964-4079-B023-5548B1EB1D1E}"
 EndProject
 Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "Solution Items", "Solution Items", "{30CDFA65-3AD8-42A4-801E-0F785CE9DF16}"
@@ -15 +13 @@
 EndProject
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.NCA.Tests", "HeuristicLab.Algorithms.NCA.Tests\HeuristicLab.Algorithms.NCA.Tests.csproj", "{910C130C-378D-422B-96B7-0484F7CC66B7}"
+EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.NCA.Views-3.3", "HeuristicLab.Algorithms.NCA.Views\3.3\HeuristicLab.Algorithms.NCA.Views-3.3.csproj", "{07654A26-5964-4079-B023-5548B1EB1D1E}"
 EndProject
 Global
@@ -37 +37 @@
     {FD81A5D6-051D-4BD1-B2D8-668A820FAD6E}.Release|x64.ActiveCfg = Release|Any CPU
     {FD81A5D6-051D-4BD1-B2D8-668A820FAD6E}.Release|x86.ActiveCfg = Release|Any CPU
+    {910C130C-378D-422B-96B7-0484F7CC66B7}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+    {910C130C-378D-422B-96B7-0484F7CC66B7}.Debug|Any CPU.Build.0 = Debug|Any CPU
+    {910C130C-378D-422B-96B7-0484F7CC66B7}.Debug|x64.ActiveCfg = Debug|Any CPU
+    {910C130C-378D-422B-96B7-0484F7CC66B7}.Debug|x86.ActiveCfg = Debug|Any CPU
+    {910C130C-378D-422B-96B7-0484F7CC66B7}.Release|Any CPU.ActiveCfg = Release|Any CPU
+    {910C130C-378D-422B-96B7-0484F7CC66B7}.Release|Any CPU.Build.0 = Release|Any CPU
+    {910C130C-378D-422B-96B7-0484F7CC66B7}.Release|x64.ActiveCfg = Release|Any CPU
+    {910C130C-378D-422B-96B7-0484F7CC66B7}.Release|x86.ActiveCfg = Release|Any CPU
     {07654A26-5964-4079-B023-5548B1EB1D1E}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     {07654A26-5964-4079-B023-5548B1EB1D1E}.Debug|Any CPU.Build.0 = Debug|Any CPU
@@ -49 +57 @@
     {07654A26-5964-4079-B023-5548B1EB1D1E}.Release|x86.ActiveCfg = Release|x86
     {07654A26-5964-4079-B023-5548B1EB1D1E}.Release|x86.Build.0 = Release|x86
-    {910C130C-378D-422B-96B7-0484F7CC66B7}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
-    {910C130C-378D-422B-96B7-0484F7CC66B7}.Debug|Any CPU.Build.0 = Debug|Any CPU
-    {910C130C-378D-422B-96B7-0484F7CC66B7}.Debug|x64.ActiveCfg = Debug|Any CPU
-    {910C130C-378D-422B-96B7-0484F7CC66B7}.Debug|x86.ActiveCfg = Debug|Any CPU
-    {910C130C-378D-422B-96B7-0484F7CC66B7}.Release|Any CPU.ActiveCfg = Release|Any CPU
-    {910C130C-378D-422B-96B7-0484F7CC66B7}.Release|Any CPU.Build.0 = Release|Any CPU
-    {910C130C-378D-422B-96B7-0484F7CC66B7}.Release|x64.ActiveCfg = Release|Any CPU
-    {910C130C-378D-422B-96B7-0484F7CC66B7}.Release|x86.ActiveCfg = Release|Any CPU
   EndGlobalSection
   GlobalSection(SolutionProperties) = preSolution