source: branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/PerformanceModelingView.cs @ 13803

Last change on this file since 13803 was 13803, checked in by abeham, 3 years ago

#2457:

  • changed expected runtime calculation
    • now outputs positive infinity instead of nan when no run was successful
    • now filters outliers in successful and unsuccessful runs by using two standard deviations of the mean of successful runs as lower bound
      • this change allows having unsuccessful runs in the database with low evaluations / runtime (e.g. due to being aborted early or from an experiment where the max budget was lower)
  • worked on recommendation algorithms
    • implemented several performance measures (absolute error, absolute log error, ndcp, kendall's tau) to evaluate the ranking
File size: 13.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using HeuristicLab.Analysis;
23using HeuristicLab.Common.Resources;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.MainForm;
27using HeuristicLab.Optimization;
28using HeuristicLab.OptimizationExpertSystem.Common;
29using HeuristicLab.PluginInfrastructure;
30using System;
31using System.Collections.Generic;
32using System.Linq;
33using System.Threading.Tasks;
34
35namespace HeuristicLab.OptimizationExpertSystem {
36  [View("Performance Modeling View")]
37  [Content(typeof(KnowledgeCenter), IsDefaultView = false)]
38  public partial class PerformanceModelingView : KnowledgeCenterViewBase {
39    private readonly CheckedItemList<StringValue> characteristics;
40
41    public PerformanceModelingView() {
42      InitializeComponent();
43      characteristics = new CheckedItemList<StringValue>();
44      characteristics.CheckedItemsChanged += CharacteristicsOnCheckedItemsChanged;
45      characteristicsViewHost.Content = characteristics;
46      recommendStartButton.Text = string.Empty;
47      recommendStartButton.Image = VSImageLibrary.Play;
48      refreshCharacteristicsButton.Text = string.Empty;
49      refreshCharacteristicsButton.Image = VSImageLibrary.Refresh;
50      UpdateRecommenderCombobox();
51    }
52
53    protected override void OnContentChanged() {
54      base.OnContentChanged();
55      if (Content == null) {
56        minTargetView.Content = null;
57      } else {
58        minTargetView.Content = Content.MinimumTarget;
59      }
60      UpdateCharacteristics();
61      UpdateTopNCombobox();
62    }
63
64    protected override void SetEnabledStateOfControls() {
65      base.SetEnabledStateOfControls();
66      // TODO: up/download state
67      recommendStartButton.Enabled = Content != null && recommenderComboBox.SelectedIndex >= 0 && characteristics.CheckedItems.Any();
68      characteristicsViewHost.Enabled = Content != null;
69      xValidateButton.Enabled = Content != null && recommenderComboBox.SelectedIndex >= 0 && characteristics.CheckedItems.Any() && topNComboBox.SelectedIndex >= 0;
70    }
71
72    #region Update Controls
73    private void UpdateRecommenderCombobox() {
74      if (InvokeRequired) { Invoke((Action)UpdateRecommenderCombobox); return; }
75      var prevSelection = (IAlgorithmInstanceRecommender)recommenderComboBox.SelectedItem;
76      var prevNewIndex = -1;
77      recommenderComboBox.Items.Clear();
78
79      var i = 0;
80      foreach (var rcmd in ApplicationManager.Manager.GetInstances<IAlgorithmInstanceRecommender>()) {
81        recommenderComboBox.Items.Add(rcmd);
82        if (prevSelection == null || rcmd.GetType() == prevSelection.GetType())
83          prevNewIndex = prevSelection == null ? 0 : i;
84        i++;
85      }
86     
87      recommenderComboBox.SelectedIndex = prevNewIndex;
88    }
89
90    private void UpdateCharacteristics() {
91      if (InvokeRequired) { Invoke((Action)UpdateCharacteristics); return; }
92
93      var @checked = new HashSet<string>(characteristics.CheckedItems.Select(x => x.Value.Value));
94      if (@checked.Count == 0 && Content.ProblemInstances.ResultNames.Any(x => x.StartsWith("Characteristic.")))
95        @checked = new HashSet<string>(Content.ProblemInstances.ResultNames.Where(x => x.StartsWith("Characteristic.")));
96
97      characteristics.Clear();
98      if (Content == null || Content.ProblemInstances.Count == 0) return;
99
100      foreach (var c in Content.ProblemInstances.ResultNames) {
101        characteristics.Add(new StringValue(c), @checked.Contains(c));
102      }
103    }
104
105    private void UpdateTopNCombobox() {
106      if (InvokeRequired) { Invoke((Action)UpdateTopNCombobox); return; }
107
108      int selected = 3;
109      if (topNComboBox.SelectedIndex >= 0) selected = (int)topNComboBox.SelectedItem;
110      topNComboBox.Items.Clear();
111      if (Content == null) return;
112
113      var algInstances = Content.AlgorithmInstances.Count;
114      for (var i = 1; i <= algInstances; i++) {
115        topNComboBox.Items.Add(i);
116      }
117      topNComboBox.SelectedIndex = Math.Min(selected, topNComboBox.Items.Count) - 1;
118    }
119    #endregion
120
121    #region Content Event Handlers
122    protected override void OnProblemInstancesChanged() {
123      base.OnProblemInstancesChanged();
124      UpdateCharacteristics();
125      SetEnabledStateOfControls();
126    }
127
128    protected override void OnAlgorithmInstancesChanged() {
129      base.OnAlgorithmInstancesChanged();
130      UpdateTopNCombobox();
131    }
132    #endregion
133
134    #region Control Event Handlers
135    private void RecommenderComboBoxOnSelectedIndexChanged(object sender, EventArgs e) {
136      if (InvokeRequired) { Invoke((Action<object, EventArgs>)RecommenderComboBoxOnSelectedIndexChanged, sender, e); return; }
137      var rcmd = (IAlgorithmInstanceRecommender)recommenderComboBox.SelectedItem;
138      parameterCollectionView.Content = rcmd != null ? rcmd.Parameters : null;
139      SetEnabledStateOfControls();
140    }
141
142    private void RecommendStartButtonOnClick(object sender, EventArgs e) {
143      var rcmd = (IAlgorithmInstanceRecommender)recommenderComboBox.SelectedItem;
144      var trainingSet = Content.ProblemInstances.Where(x => !Content.IsCurrentInstance(x)).ToArray();
145      Content.RecommendationModel = rcmd.TrainModel(trainingSet, Content, characteristics.CheckedItems.Select(x => x.Value.Value).ToArray());
146    }
147
148    private void RefreshCharacteristicsButtonOnClick(object sender, EventArgs e) {
149      UpdateCharacteristics();
150      SetEnabledStateOfControls();
151    }
152
153    private void xValidateButton_Click(object sender, EventArgs e) {
154      var recommender = (IAlgorithmInstanceRecommender)recommenderComboBox.SelectedItem;
155      var progress = MainForm.AddOperationProgressToView(this, "Performing Leave-one-out Crossvalidation");
156      var topN = (int)topNComboBox.SelectedItem;
157      Task.Factory.StartNew(() => { DoCrossvalidate(recommender, topN, progress); }, TaskCreationOptions.LongRunning);
158    }
159
160    private void topNComboBox_SelectedIndexChanged(object sender, EventArgs e) {
161      SetEnabledStateOfControls();
162    }
163    #endregion
164
165    #region Other Event Handlers
166    private void CharacteristicsOnCheckedItemsChanged(object sender, EventArgs e) {
167      SetEnabledStateOfControls();
168    }
169    #endregion
170   
171    private void DoCrossvalidate(IAlgorithmInstanceRecommender recommender, int topN, IProgress progress) {
172      try {
173        var features = characteristics.CheckedItems.Select(x => x.Value.Value).ToArray();
174        var trainingSet = Content.ProblemInstances.Where(x => !Content.IsCurrentInstance(x)).ToArray();
175
176        var absErr = 0.0;
177        var absErrCnt = 0;
178        var absLogErr = 0.0;
179        var absLogErrCnt = 0;
180        var confMatrix = new int[1, 6];
181        var tau = 0.0;
182        var tauCnt = 0;
183        var ndcg = 0.0;
184        var ndcgCnt = 0;
185        // leave one out crossvalidation
186        var count = 0;
187        foreach (var pi in trainingSet) {
188          var observed = Content.GetAlgorithmPerformance(pi);
189          if (observed.Count == 0) continue;
190          progress.Status = pi.Name + "...";
191          var model = recommender.TrainModel(trainingSet.Where(x => x != pi).ToArray(), Content, features);
192          var predictedTopN = model.GetRanking(pi).Take(topN).ToDictionary(x => x.Key, x => x.Value);
193          var predicted = model.GetRanking(pi).ToDictionary(x => x.Key, x => x.Value);
194          var ae = AbsoluteError(observed, predictedTopN);
195          if (!double.IsNaN(ae)) {
196            absErr += ae; // in case we only predicted instances that have not been observed
197            absErrCnt++;
198          }
199          var ale = AbsoluteLogError(observed, predictedTopN);
200          if (!double.IsNaN(ale)) {
201            absLogErr += ale; // in case we only predicted instances that have not been observed
202            absLogErrCnt++;
203          }
204          var confMat = ConfusionMatrix(observed, predictedTopN);
205          for (var i = 0; i < confMat.Length; i++) {
206            confMatrix[0, i] += confMat[i];
207          }
208          var kt = KendallsTau(observed, predicted);
209          if (!double.IsNaN(kt)) {
210            tau += kt;
211            tauCnt++;
212          }
213          var gain = NDCG(observed, model.GetRanking(pi).Take(topN).Select(x => x.Key).ToList());
214          if (!double.IsNaN(gain)) {
215            ndcg += gain;
216            ndcgCnt++;
217          }
218          // mean reciprocal rank
219          // optional: expected reciprocal rank
220          progress.ProgressValue = ++count / (double)trainingSet.Length;
221        }
222        absErr /= absErrCnt;
223        absLogErr /= absLogErrCnt;
224        tau /= tauCnt;
225        ndcg /= ndcgCnt;
226
227        absoluteErrorView.Content = new DoubleValue(absErr);
228        absoluteLogErrorView.Content = new DoubleValue(absLogErr);
229        var description = new[] {"A", "B", "C", "D", "E", "F"};
230        confusionMatrixView.Content = new IntMatrix(confMatrix) {ColumnNames = description};
231        kendallsTauView.Content = new DoubleValue(tau);
232        ncdgView.Content = new DoubleValue(ndcg);
233      } finally { progress.Finish(); }
234    }
235
236    private static double AbsoluteError(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
237      var error = 0.0;
238      var count = 0;
239      foreach (var tuple in ranking) {
240        double actual;
241        if (!performance.TryGetValue(tuple.Key, out actual)) continue;
242        if (double.IsInfinity(actual)) actual = int.MaxValue;
243        error += Math.Abs(actual - tuple.Value);
244        count++;
245      }
246      return error / count;
247    }
248
249    private static double AbsoluteLogError(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
250      var error = 0.0;
251      var count = 0;
252      foreach (var tuple in ranking) {
253        double actual;
254        if (!performance.TryGetValue(tuple.Key, out actual)) continue;
255        if (double.IsInfinity(actual)) actual = int.MaxValue;
256        error += Math.Abs(Math.Log10(actual) - Math.Log10(tuple.Value));
257        count++;
258      }
259      return error / count;
260    }
261
262    private static int[] ConfusionMatrix(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
263      var confMatrix = new int[6];
264      var clusteredPerformance = ClusteringHelper<IAlgorithm>.Cluster(5, performance, a => double.IsInfinity(a.Value)).GetByInstance().ToDictionary(x => x.Key, x => x.Value.Item2);
265     
266      foreach (var cr in ranking) {
267        int realRank;
268        if (!clusteredPerformance.TryGetValue(cr.Key, out realRank)) continue;
269        confMatrix[realRank]++;
270      }
271      return confMatrix;
272    }
273
274    private static double KendallsTau(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
275      var commonKeys = performance.Keys.Intersect(ranking.Keys).ToList();
276      var n = commonKeys.Count;
277      if (n == 0) return double.NaN;
278
279      var actualRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = performance[x] })
280                                  .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = i })
281                                  .OrderBy(x => x.Index).Select(x => x.Rank).ToList();
282      var predictedRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = ranking[x] })
283                                     .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = i })
284                                     .OrderBy(x => x.Index).Select(x => x.Rank).ToList();
285
286      var paired = actualRanks.Zip(predictedRanks, (a, p) => new { Actual = a, Predicted = p }).ToList();
287      var concordant = 0;
288      var discordant = 0;
289      for (var i = 0; i < paired.Count - 1; i++)
290        for (var j = i + 1; j < paired.Count; j++) {
291          if (paired[i].Actual > paired[j].Actual && paired[i].Predicted > paired[j].Predicted
292            || paired[i].Actual < paired[j].Actual && paired[i].Predicted < paired[j].Predicted)
293            concordant++;
294          else discordant++;
295        }
296      return (2.0 * (concordant - discordant)) / (n * (n - 1));
297    }
298
299    private static double NDCG(Dictionary<IAlgorithm, double> performance, List<IAlgorithm> ranking) {
300      var k = 5;
301      var relevance = ClusteringHelper<IAlgorithm>.Cluster(k, performance, a => double.IsInfinity(a.Value)).GetByInstance().ToDictionary(x => x.Key, x => k - x.Value.Item2);
302     
303      var i = 0;
304      var dcgp = 0.0;
305      for (; i < ranking.Count; i++) {
306        int rel;
307        if (!relevance.TryGetValue(ranking[i], out rel))
308          continue;
309        dcgp = rel;
310        i++;
311        break;
312      }
313      for (; i < ranking.Count; i++) {
314        int rel;
315        if (!relevance.TryGetValue(ranking[i], out rel))
316          continue;
317        dcgp += rel / Math.Log(i + 1, 2);
318      }
319      var ideal = relevance.Select(x => x.Value).OrderByDescending(x => x).Take(ranking.Count).ToArray();
320      double idcgp = ideal[0];
321      for (i = 1; i < ideal.Length; i++)
322        idcgp += ideal[i] / Math.Log(i + 1, 2);
323
324      return dcgp / idcgp;
325    }
326  }
327}
Note: See TracBrowser for help on using the repository browser.