Changeset 17844


Ignore:
Timestamp:
02/24/21 22:22:21 (7 weeks ago)
Author:
bburlacu
Message:

#3087: Implement NativeInterpreter and ParameterOptimizer classes. The ParameterOptimizer offers an interface to Ceres and its options and to the variable projection optimization method. Added unit tests.

Location:
branches/3087_Ceres_Integration
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • branches/3087_Ceres_Integration/HeuristicLab 3.3 Tests.sln

    r16430 r17844  
    11
    22Microsoft Visual Studio Solution File, Format Version 12.00
    3 # Visual Studio 2012
     3# Visual Studio Version 16
     4VisualStudioVersion = 16.0.31005.135
     5MinimumVisualStudioVersion = 10.0.40219.1
    46Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Tests", "HeuristicLab.Tests\HeuristicLab.Tests.csproj", "{B62872C1-6752-4758-9823-751A2D28C388}"
    57EndProject
     
    3234    HideSolutionNode = FALSE
    3335  EndGlobalSection
     36  GlobalSection(ExtensibilityGlobals) = postSolution
     37    SolutionGuid = {447EA927-9940-4813-A766-FC1867C90E6C}
     38  EndGlobalSection
    3439EndGlobal
  • branches/3087_Ceres_Integration/HeuristicLab.ExtLibs/HeuristicLab.NativeInterpreter/0.1/HeuristicLab.NativeInterpreter-0.1/DllImporter.cs

    r16333 r17844  
    11using System;
     2using System.IO;
     3using System.IO.Compression;
    24using System.Runtime.InteropServices;
    35
     
    57  [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Ansi)]
    68  public struct NativeInstruction {
    7     public byte opcode;
    8     public ushort narg;
    9     public int childIndex;
    10     public double value;
    11     public double weight;
    12 
    13     public IntPtr buf;
    14     public IntPtr data;
     9    public byte OpCode;
     10    public ushort Arity;
     11    public ushort Length;
     12    public double Value;
     13    public IntPtr Data;
     14    public bool Optimize;
    1515  }
    1616
     17  // proxy structure to pass information from Ceres back to the caller
     18  [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Ansi)]
     19  public struct OptimizationSummary {
     20    public double InitialCost; // value of the objective function before the optimization
     21    public double FinalCost; // value of the objective function after the optimization
     22    public int SuccessfulSteps; // number of minimizer iterations in which the step was accepted
     23    public int UnsuccessfulSteps; // number of minimizer iterations in which the step was rejected
     24    public int InnerIterationSteps; // number of times inner iterations were performed
     25    public int ResidualEvaluations; // number of residual only evaluations
     26    public int JacobianEvaluations; // number of Jacobian (and residual) evaluations
     27  };
     28
     29  public enum MinimizerType : int {
     30    LINE_SEARCH = 0,
     31    TRUST_REGION = 1
     32  }
     33
     34  public enum LinearSolverType : int {
     35    DENSE_NORMAL_CHOLESKY = 0,
     36    DENSE_QR = 1,
     37    SPARSE_NORMAL_CHOLESKY = 2,
     38    DENSE_SCHUR = 3,
     39    SPARSE_SCHUR = 4,
     40    ITERATIVE_SCHUR = 5,
     41    CGNR = 6
     42  }
     43
     44  public enum TrustRegionStrategyType : int {
     45    LEVENBERG_MARQUARDT = 0,
     46    DOGLEG = 1
     47  }
     48
     49  public enum DoglegType : int {
     50    TRADITIONAL_DOGLEG = 0,
     51    SUBSPACE_DOGLEG = 1
     52  }
     53
     54  public enum LineSearchDirectionType : int {
     55    STEEPEST_DESCENT = 0,
     56    NONLINEAR_CONJUGATE_GRADIENT = 1,
     57    LBFGS = 2,
     58    BFSG = 3
     59  }
     60
     61  [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Ansi)]
     62  public struct SolverOptions {
     63    public int Iterations;
     64    public int UseNonmonotonicSteps;
     65    public int Minimizer; // type of minimizer (trust region or line search)
     66    public int LinearSolver; // type of linear solver
     67    public int TrustRegionStrategy; // levenberg-marquardt or dogleg
     68    public int Dogleg; // type of dogleg (traditional or subspace)
     69    public int LineSearchDirection; // line search direction type (BFGS, LBFGS, etc)
     70    public int Algorithm;
     71  };
     72
    1773  public static class NativeWrapper {
    18     private const string x86dll = "hl-native-interpreter-msvc-x86.dll";
    19     private const string x64dll = "hl-native-interpreter-msvc-x64.dll";
     74    private const string x86zip = "hl-native-interpreter-x86.zip";
     75    private const string x64zip = "hl-native-interpreter-x64.zip";
     76
     77    private const string x86dll = "hl-native-interpreter-x86.dll";
     78    private const string x64dll = "hl-native-interpreter-x64.dll";
    2079
    2180    private readonly static bool is64;
     
    2382    static NativeWrapper() {
    2483      is64 = Environment.Is64BitProcess;
     84
     85      //using (var zip = new FileStream(is64 ? x64zip : x86zip, FileMode.Open)) {
     86      //  using (var archive = new ZipArchive(zip, ZipArchiveMode.Read)) {
     87      //    foreach (var entry in archive.Entries) {
     88      //      if (File.Exists(entry.Name)) {
     89      //        File.Delete(entry.Name);
     90      //      }
     91      //    }
     92      //    ZipFileExtensions.ExtractToDirectory(archive, Environment.CurrentDirectory);
     93      //  }
     94      //}
    2595    }
    2696
    27     public static double GetValue(NativeInstruction[] code, int len, int row) {
    28       return is64 ? GetValue64(code, len, row) : GetValue32(code, len, row);
     97    public static void GetValues(NativeInstruction[] code, int[] rows, double[] result, double[] target, SolverOptions options, ref OptimizationSummary summary) {
     98      if (is64)
     99        GetValues64(code, code.Length, rows, rows.Length, options, result, target, ref summary);
     100      else
     101        GetValues32(code, code.Length, rows, rows.Length, options, result, target, ref summary);
    29102    }
    30103
    31     public static void GetValues(NativeInstruction[] code, int len, int[] rows, int nRows, double[] result) {
     104    public static void GetValuesVarPro(NativeInstruction[] code, int[] termIndices, int[] rows, double[] coefficients,
     105      double[] result, double[] target, SolverOptions options, ref OptimizationSummary summary) {
    32106      if (is64)
    33         GetValues64(code, len, rows, nRows, result);
     107        GetValuesVarPro64(code, code.Length, termIndices, termIndices.Length, rows, rows.Length, coefficients, options, result, target, ref summary);
    34108      else
    35         GetValues32(code, len, rows, nRows, result);
    36     }
    37 
    38     public static void GetValuesVectorized(NativeInstruction[] code, int len, int[] rows, int nRows, double[] result) {
    39       if (is64)
    40         GetValuesVectorized64(code, len, rows, nRows, result);
    41       else
    42         GetValuesVectorized32(code, len, rows, nRows, result);
     109        GetValuesVarPro32(code, code.Length, termIndices, termIndices.Length, rows, rows.Length, coefficients, options, result, target, ref summary);
    43110    }
    44111
    45112    // x86
    46     [DllImport(x86dll, EntryPoint = "GetValue", CallingConvention = CallingConvention.Cdecl)]
    47     internal static extern double GetValue32(NativeInstruction[] code, int len, int row);
    48 
    49113    [DllImport(x86dll, EntryPoint = "GetValues", CallingConvention = CallingConvention.Cdecl)]
    50     internal static extern void GetValues32(NativeInstruction[] code, int len, int[] rows, int nRows, double[] result);
    51 
    52     [DllImport(x86dll, EntryPoint = "GetValuesVectorized", CallingConvention = CallingConvention.Cdecl)]
    53     internal static extern void GetValuesVectorized32(NativeInstruction[] code, int len, int[] rows, int nRows, double[] result);
     114    internal static extern void GetValues32([In, Out] NativeInstruction[] code, int len, int[] rows, int nRows, SolverOptions options, [In, Out] double[] result, double[] target, ref OptimizationSummary summary);
    54115
    55116    // x64
    56     [DllImport(x64dll, EntryPoint = "GetValue", CallingConvention = CallingConvention.Cdecl)]
    57     internal static extern double GetValue64(NativeInstruction[] code, int len, int row);
     117    [DllImport(x64dll, EntryPoint = "GetValues", CallingConvention = CallingConvention.Cdecl)]
     118    internal static extern void GetValues64([In, Out] NativeInstruction[] code, int len, int[] rows, int nRows, SolverOptions options, [In, Out] double[] result, double[] target, ref OptimizationSummary summary);
    58119
    59     [DllImport(x64dll, EntryPoint = "GetValues", CallingConvention = CallingConvention.Cdecl)]
    60     internal static extern void GetValues64(NativeInstruction[] code, int len, int[] rows, int nRows, double[] result);
     120    [DllImport(x86dll, EntryPoint = "GetValuesVarPro", CallingConvention = CallingConvention.Cdecl)]
     121    internal static extern void GetValuesVarPro32([In, Out] NativeInstruction[] code, int len, int[] termIndices, int nTerms, int[] rows, int nRows, [In, Out] double[] coefficients, SolverOptions options, [In, Out] double[] result, double[] target, ref OptimizationSummary summary);
    61122
    62     [DllImport(x64dll, EntryPoint = "GetValuesVectorized", CallingConvention = CallingConvention.Cdecl)]
    63     internal static extern void GetValuesVectorized64(NativeInstruction[] code, int len, int[] rows, int nRows, double[] result);
     123    [DllImport(x64dll, EntryPoint = "GetValuesVarPro", CallingConvention = CallingConvention.Cdecl)]
     124    internal static extern void GetValuesVarPro64([In, Out] NativeInstruction[] code, int len, int[] termIndices, int nTerms, int[] rows, int nRows, [In, Out] double[] coefficients, SolverOptions options, [In, Out] double[] result, double[] target, ref OptimizationSummary summary);
    64125  }
    65126}
  • branches/3087_Ceres_Integration/HeuristicLab.ExtLibs/HeuristicLab.NativeInterpreter/0.1/HeuristicLab.NativeInterpreter-0.1/Plugin.cs

    r17180 r17844  
    2020#endregion
    2121
     22using System;
     23using System.IO;
     24
    2225using HeuristicLab.PluginInfrastructure;
    2326
     
    2528  [Plugin("HeuristicLab.NativeInterpreter", "Provides a native (C++) interpreter for symbolic expression trees", "0.0.0.1")]
    2629  [PluginFile("HeuristicLab.Problems.DataAnalysis.Symbolic.NativeInterpreter-0.1.dll", PluginFileType.Assembly)]
    27   [PluginFile("hl-native-interpreter-msvc-x86.dll", PluginFileType.NativeDll)]
    28   [PluginFile("hl-native-interpreter-msvc-x64.dll", PluginFileType.NativeDll)]
    2930  public class HeuristicLabNativeInterpreterPlugin : PluginBase {
     31    public override void OnLoad() {
     32      base.OnLoad();
     33      // add path for native dlls to PATH env variable
     34
     35      var is64 = Environment.Is64BitProcess;
     36      string nativeDllPath = Path.Combine(Environment.CurrentDirectory, is64 ? "x64" : "x86");
     37      var envPath = Environment.GetEnvironmentVariable("PATH");
     38      if (!envPath.Contains(nativeDllPath))
     39        Environment.SetEnvironmentVariable("PATH", envPath + ";" + nativeDllPath);
     40    }
    3041  }
    3142}
  • branches/3087_Ceres_Integration/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r17413 r17844  
    169169    <Compile Include="Interpreter\BatchOperations.cs" />
    170170    <Compile Include="Interpreter\IntervalInterpreter.cs" />
     171    <Compile Include="Interpreter\ParameterOptimizer.cs" />
    171172    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionCompiledTreeInterpreter.cs" />
    172173    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeBatchInterpreter.cs" />
    173     <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeNativeInterpreter.cs" />
     174    <Compile Include="Interpreter\NativeInterpreter.cs" />
    174175    <Compile Include="Selectors\DiversitySelector.cs" />
    175176    <Compile Include="SymbolicDataAnalysisExpressionTreeAverageSimilarityCalculator.cs" />
  • branches/3087_Ceres_Integration/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeNativeInterpreter.cs

    r17402 r17844  
    127127      if (!rows.Any()) return Enumerable.Empty<double>();
    128128
    129       if (cachedData == null || cachedDataset != dataset) {
     129      if (cachedData == null || cachedDataset != dataset || cachedDataset is ModifiableDataset) {
    130130        InitCache(dataset);
    131131      }
  • branches/3087_Ceres_Integration/HeuristicLab.Tests/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4/SymbolicDataAnalysisExpressionTreeInterpreterTest.cs

    r17180 r17844  
    119119    public void LinearInterpreterTestArithmeticGrammarPerformance() {
    120120      TestArithmeticGrammarPerformance(new SymbolicDataAnalysisExpressionTreeLinearInterpreter(), 12.5e6);
     121    }
     122
     123    [TestMethod]
     124    [TestCategory("Problems.DataAnalysis.Symbolic")]
     125    [TestProperty("Time", "long")]
     126    public void NativeInterpreterTestTypeCoherentGrammarPerformance() {
     127      TestTypeCoherentGrammarPerformance(new NativeInterpreter(), 12.5e6);
     128    }
     129    [TestMethod]
     130    [TestCategory("Problems.DataAnalysis.Symbolic")]
     131    [TestProperty("Time", "long")]
     132    public void NativeInterpreterTestFullGrammarPerformance() {
     133      TestFullGrammarPerformance(new NativeInterpreter(), 12.5e6);
     134    }
     135    [TestMethod]
     136    [TestCategory("Problems.DataAnalysis.Symbolic")]
     137    [TestProperty("Time", "long")]
     138    public void NativeInterpreterTestArithmeticGrammarPerformance() {
     139      TestArithmeticGrammarPerformance(new NativeInterpreter(), 12.5e6);
     140    }
     141
     142    [TestMethod]
     143    [TestCategory("Problems.DataAnalysis.Symbolic")]
     144    [TestProperty("Time", "long")]
     145    public void NativeInterpreterTestCeres() {
     146      var parser = new InfixExpressionParser();
     147      var random = new FastRandom(1234);
     148      const int nRows = 20;
     149
     150      var x1 = Enumerable.Range(0, nRows).Select(_ => UniformDistributedRandom.NextDouble(random, -1, 1)).ToArray();
     151      var x2 = Enumerable.Range(0, nRows).Select(_ => UniformDistributedRandom.NextDouble(random, -1, 1)).ToArray();
     152      var x3 = Enumerable.Range(0, nRows).Select(_ => UniformDistributedRandom.NextDouble(random, -1, 1)).ToArray();
     153
     154      var optimalAlpha = new double[] { -2, -3, -5 };
     155      var y = Enumerable.Range(0, nRows).Select(i =>
     156          Math.Exp(x1[i] * optimalAlpha[0]) +
     157          Math.Exp(x2[i] * optimalAlpha[1]) +
     158          Math.Exp(x3[i] * optimalAlpha[2])).ToArray();
     159
     160      var initialAlpha = Enumerable.Range(0, 3).Select(_ => UniformDistributedRandom.NextDouble(random, -1, 1)).ToArray();
     161      var ds = new Dataset(new[] { "x1", "x2", "x3", "y" }, new[] { x1, x2, x3, y });
     162
     163      var expr = "EXP(x1) + EXP(x2) + EXP(x3)";
     164      var tree = parser.Parse(expr);
     165      var rows = Enumerable.Range(0, nRows).ToArray();
     166      var options = new SolverOptions {
     167        Minimizer = (int)MinimizerType.TRUST_REGION,
     168        Iterations = 20,
     169        TrustRegionStrategy = (int)TrustRegionStrategyType.LEVENBERG_MARQUARDT,
     170        LinearSolver = (int)LinearSolverType.DENSE_QR
     171      };
     172
     173      var nodesToOptimize = new HashSet<ISymbolicExpressionTreeNode>(tree.IterateNodesPrefix().Where(x => x is VariableTreeNode));
     174      int idx = 0;
     175      foreach(var node in nodesToOptimize) {
     176        (node as VariableTreeNode).Weight = initialAlpha[idx++];
     177        Console.WriteLine((node as VariableTreeNode).Weight);
     178
     179      }
     180
     181      var summary = new OptimizationSummary();
     182      var parameters = ParameterOptimizer.OptimizeTree(tree, ds, rows, "y", nodesToOptimize, options, ref summary);
     183
     184      Console.Write("Optimized parameters: ");
     185      foreach (var t in parameters) {
     186        Console.Write(t.Value + " ");
     187      }
     188      Console.WriteLine();
     189
     190      Console.WriteLine("Optimization summary:");
     191      Console.WriteLine("Initial cost:         " + summary.InitialCost);
     192      Console.WriteLine("Final cost:           " + summary.FinalCost);
     193      Console.WriteLine("Successful steps:     " + summary.SuccessfulSteps);
     194      Console.WriteLine("Unsuccessful steps:   " + summary.UnsuccessfulSteps);
     195      Console.WriteLine("Residual evaluations: " + summary.ResidualEvaluations);
     196      Console.WriteLine("Jacobian evaluations: " + summary.JacobianEvaluations);
     197    }
     198
     199    [TestMethod]
     200    [TestCategory("Problems.DataAnalysis.Symbolic")]
     201    [TestProperty("Time", "long")]
     202    public void NativeInterpreterTestCeresVariableProjection() {
     203      var parser = new InfixExpressionParser();
     204      var random = new FastRandom(1234);
     205      const int nRows = 20;
     206
     207      var x1 = Enumerable.Range(0, nRows).Select(_ => UniformDistributedRandom.NextDouble(random, -1, 1)).ToArray();
     208      var x2 = Enumerable.Range(0, nRows).Select(_ => UniformDistributedRandom.NextDouble(random, -1, 1)).ToArray();
     209      var x3 = Enumerable.Range(0, nRows).Select(_ => UniformDistributedRandom.NextDouble(random, -1, 1)).ToArray();
     210
     211      var optimalAlpha = new double[] { -2, -3, -5 };
     212      var y = Enumerable.Range(0, nRows).Select(i =>
     213        Math.Exp(x1[i] * optimalAlpha[0]) +
     214        Math.Exp(x2[i] * optimalAlpha[1]) +
     215        Math.Exp(x3[i] * optimalAlpha[2])).ToArray();
     216
     217      var initialAlpha = Enumerable.Range(0, 3).Select(_ => UniformDistributedRandom.NextDouble(random, -1, 1)).ToArray();
     218      var ds = new Dataset(new[] { "x1", "x2", "x3", "y" }, new[] { x1, x2, x3, y });
     219
     220      var expr = new[] { "EXP(x1)", "EXP(x2)", "EXP(x3)" };
     221      var trees = expr.Select(x => parser.Parse(x)).ToArray();
     222      var rows = Enumerable.Range(0, nRows).ToArray();
     223      var options = new SolverOptions {
     224        Minimizer = (int)MinimizerType.TRUST_REGION,
     225        Iterations = 100,
     226        TrustRegionStrategy = (int)TrustRegionStrategyType.LEVENBERG_MARQUARDT,
     227        LinearSolver = (int)LinearSolverType.DENSE_QR
     228      };
     229
     230      var summary = new OptimizationSummary();
     231
     232      var nodesToOptimize = new HashSet<ISymbolicExpressionTreeNode>(trees.SelectMany(t => t.IterateNodesPrefix().Where(x => x is VariableTreeNode)));
     233      int idx = 0;
     234      Console.Write("Initial parameters: ");
     235      foreach (var node in nodesToOptimize) {
     236        (node as VariableTreeNode).Weight = initialAlpha[idx++];
     237        Console.Write((node as VariableTreeNode).Weight + " ");
     238      }
     239      Console.WriteLine();
     240
     241      var coeff = new double[trees.Length + 1];
     242      var parameters = ParameterOptimizer.OptimizeTree(trees, ds, rows, "y", nodesToOptimize, options, coeff, ref summary);
     243      Console.Write("Optimized parameters: ");
     244      foreach (var t in parameters) {
     245        Console.Write(t.Value + " ");
     246      }
     247      Console.WriteLine();
     248
     249      Console.Write("Coefficients: ");
     250      foreach (var v in coeff) Console.Write(v + " ");
     251      Console.WriteLine();
     252
     253      Console.WriteLine("Optimization summary:");
     254      Console.WriteLine("Initial cost:         " + summary.InitialCost);
     255      Console.WriteLine("Final cost:           " + summary.FinalCost);
     256      Console.WriteLine("Successful steps:     " + summary.SuccessfulSteps);
     257      Console.WriteLine("Unsuccessful steps:   " + summary.UnsuccessfulSteps);
     258      Console.WriteLine("Residual evaluations: " + summary.ResidualEvaluations);
     259      Console.WriteLine("Jacobian evaluations: " + summary.JacobianEvaluations);
    121260    }
    122261
  • branches/3087_Ceres_Integration/HeuristicLab.Tests/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4/Util.cs

    r17180 r17844  
    9898      Console.WriteLine("Random tree evaluation performance of " + interpreter.GetType() + ": " +
    9999        watch.ElapsedMilliseconds + "ms " +
    100         Util.NodesPerSecond(nNodes * repetitions, watch) + " nodes/sec");
     100        Util.NodesPerSecond(nNodes * repetitions, watch).ToString("N") + " nodes/sec");
    101101      return Util.NodesPerSecond(nNodes * repetitions, watch);
    102102    }
  • branches/3087_Ceres_Integration/HeuristicLab.Tests/HeuristicLab.Tests.csproj

    r16908 r17844  
    287287    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Classification-3.4">
    288288      <HintPath>..\bin\HeuristicLab.Problems.DataAnalysis.Symbolic.Classification-3.4.dll</HintPath>
     289      <Private>False</Private>
     290    </Reference>
     291    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.NativeInterpreter-0.1, Version=0.0.0.1, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     292      <SpecificVersion>False</SpecificVersion>
     293      <HintPath>..\bin\HeuristicLab.Problems.DataAnalysis.Symbolic.NativeInterpreter-0.1.dll</HintPath>
    289294      <Private>False</Private>
    290295    </Reference>
Note: See TracChangeset for help on using the changeset viewer.