source: branches/1614_GeneralizedQAP/HeuristicLab.OptimizationExpertSystem/3.3/Views/PerformanceModelingView.cs @ 15736

Last change on this file since 15736 was 15736, checked in by abeham, 20 months ago

#1614: updates from last night ...

File size: 15.5 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 System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Threading.Tasks;
26using HeuristicLab.Analysis;
27using HeuristicLab.Common.Resources;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.MainForm;
31using HeuristicLab.Optimization;
32using HeuristicLab.OptimizationExpertSystem.Common;
33using HeuristicLab.PluginInfrastructure;
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 rho = 0.0;
184        var rhoCnt = 0;
185        var ndcg = 0.0;
186        var ndcgCnt = 0;
187        // leave one out crossvalidation
188        var count = 0;
189        foreach (var pi in trainingSet) {
190          var observed = Content.GetAlgorithmPerformanceLog10(pi);
191          if (observed.Count == 0) continue;
192          progress.Status = pi.Name + "...";
193          var model = recommender.TrainModel(trainingSet.Where(x => x != pi).ToArray(), Content, features);
194          var predictedTopN = model.GetRanking(pi).Take(topN).ToDictionary(x => x.Key, x => Math.Log10(x.Value));
195          var predicted = model.GetRanking(pi).ToDictionary(x => x.Key, x => Math.Log10(x.Value));
196          var ae = AbsoluteError(observed, predictedTopN);
197          if (!double.IsNaN(ae)) {
198            absErr += ae; // in case we only predicted instances that have not been observed
199            absErrCnt++;
200          }
201          var ale = AbsoluteLogError(observed, predictedTopN);
202          if (!double.IsNaN(ale)) {
203            absLogErr += ale; // in case we only predicted instances that have not been observed
204            absLogErrCnt++;
205          }
206          var confMat = ConfusionMatrix(observed, predictedTopN);
207          for (var i = 0; i < confMat.Length; i++) {
208            confMatrix[0, i] += confMat[i];
209          }
210          var kt = KendallsTau(observed, predicted);
211          if (!double.IsNaN(kt) && !double.IsInfinity(kt)) {
212            tau += kt;
213            tauCnt++;
214          }
215          var sr = SpearmansRho(observed, predicted);
216          if (!double.IsNaN(sr)) {
217            rho += sr;
218            rhoCnt++;
219          }
220          var gain = NDCG(observed, model.GetRanking(pi).Take(topN).Select(x => x.Key).ToList());
221          if (!double.IsNaN(gain)) {
222            ndcg += gain;
223            ndcgCnt++;
224          }
225          progress.ProgressValue = ++count / (double)trainingSet.Length;
226        }
227        absErr /= absErrCnt;
228        absLogErr /= absLogErrCnt;
229        tau /= tauCnt;
230        rho /= rhoCnt;
231        ndcg /= ndcgCnt;
232
233        absoluteErrorView.Content = new DoubleValue(absErr);
234        absoluteLogErrorView.Content = new DoubleValue(absLogErr);
235        var description = new[] {"A", "B", "C", "D", "E", "F"};
236        confusionMatrixView.Content = new IntMatrix(confMatrix) {ColumnNames = description};
237        kendallsTauView.Content = new DoubleValue(tau);
238        spearmansRhoView.Content = new DoubleValue(rho);
239        ncdgView.Content = new DoubleValue(ndcg);
240      } finally { progress.Finish(); }
241    }
242
243    private static double AbsoluteError(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
244      var error = 0.0;
245      var count = 0;
246      foreach (var tuple in ranking) {
247        double actual;
248        if (!performance.TryGetValue(tuple.Key, out actual)) continue;
249        if (double.IsInfinity(actual)) actual = Math.Log10(int.MaxValue);
250        error += Math.Abs(Math.Pow(10, actual) - Math.Pow(10, tuple.Value));
251        count++;
252      }
253      return error / count;
254    }
255
256    private static double AbsoluteLogError(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
257      var error = 0.0;
258      var count = 0;
259      foreach (var tuple in ranking) {
260        double actual;
261        if (!performance.TryGetValue(tuple.Key, out actual)) continue;
262        if (double.IsInfinity(actual)) actual = Math.Log10(int.MaxValue);
263        error += Math.Abs(actual - tuple.Value);
264        count++;
265      }
266      return error / count;
267    }
268
269    private static int[] ConfusionMatrix(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
270      var confMatrix = new int[6];
271      var clusteredPerformance = ClusteringHelper<IAlgorithm>.Cluster(5, performance, a => double.IsInfinity(a.Value)).GetByInstance().ToDictionary(x => x.Key, x => x.Value.Item2);
272     
273      foreach (var cr in ranking) {
274        int realRank;
275        if (!clusteredPerformance.TryGetValue(cr.Key, out realRank)) continue;
276        confMatrix[realRank]++;
277      }
278      return confMatrix;
279    }
280
281    private static double SpearmansRho(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
282      var commonKeys = performance.Keys.Intersect(ranking.Keys).ToList();
283      var n = commonKeys.Count;
284      if (n == 0) return double.NaN;
285
286      var actualRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = performance[x] })
287                                  .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = double.IsPositiveInfinity(x.Perf) ? int.MaxValue : i })
288                                  .OrderBy(x => x.Index).Select(x => (double)x.Rank).ToArray();
289      var predictedRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = ranking[x] })
290                                     .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = double.IsPositiveInfinity(x.Perf) ? int.MaxValue : i })
291                                     .OrderBy(x => x.Index).Select(x => (double)x.Rank).ToArray();
292
293      return alglib.spearmancorr2(actualRanks, predictedRanks);
294    }
295
296    private static double KendallsTau(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
297      var commonKeys = performance.Keys.Intersect(ranking.Keys).ToList();
298      var n = commonKeys.Count;
299      if (n == 0) return double.NaN;
300
301      var actualRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = performance[x] })
302                                  .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = double.IsPositiveInfinity(x.Perf) ? int.MaxValue : i })
303                                  .OrderBy(x => x.Index).Select(x => x.Rank).ToList();
304      var predictedRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = ranking[x] })
305                                     .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = double.IsPositiveInfinity(x.Perf) ? int.MaxValue : i })
306                                     .OrderBy(x => x.Index).Select(x => x.Rank).ToList();
307
308      var paired = actualRanks.Zip(predictedRanks, (a, p) => new { Actual = a, Predicted = p }).ToList();
309      var concordant = 0;
310      var discordant = 0;
311      for (var i = 0; i < paired.Count - 1; i++)
312        for (var j = i + 1; j < paired.Count; j++) {
313          if (paired[i].Actual > paired[j].Actual && paired[i].Predicted > paired[j].Predicted
314            || paired[i].Actual < paired[j].Actual && paired[i].Predicted < paired[j].Predicted)
315            concordant++;
316          else if (paired[i].Actual > paired[j].Actual && paired[i].Predicted < paired[j].Predicted
317            || paired[i].Actual < paired[j].Actual && paired[i].Predicted > paired[j].Predicted)
318            discordant++;
319        }
320
321      var ti = performance.GroupBy(x => x.Value).Sum(x => x.Count() * (x.Count() - 1));
322      var uj = ranking.GroupBy(x => x.Value).Sum(x => x.Count() * (x.Count() - 1));
323      return (2.0 * (concordant - discordant)) / Math.Sqrt( (n * (n - 1) - ti * (ti - 1)) * (n * (n - 1) - uj * (uj - 1)) );
324    }
325
326    private static double NDCG(Dictionary<IAlgorithm, double> performance, List<IAlgorithm> ranking) {
327      var k = 5;
328      var relevance = ClusteringHelper<IAlgorithm>.Cluster(k, performance, a => double.IsInfinity(a.Value)).GetByInstance().ToDictionary(x => x.Key, x => k - x.Value.Item2);
329     
330      var i = 0;
331      var dcgp = 0.0;
332      for (; i < ranking.Count; i++) {
333        int rel;
334        if (!relevance.TryGetValue(ranking[i], out rel))
335          continue;
336        dcgp = rel;
337        i++;
338        break;
339      }
340      for (; i < ranking.Count; i++) {
341        int rel;
342        if (!relevance.TryGetValue(ranking[i], out rel))
343          continue;
344        dcgp += rel / Math.Log(i + 1, 2);
345      }
346      var ideal = relevance.Select(x => x.Value).OrderByDescending(x => x).Take(ranking.Count).ToArray();
347      double idcgp = ideal[0];
348      for (i = 1; i < ideal.Length; i++)
349        idcgp += ideal[i] / Math.Log(i + 1, 2);
350
351      return dcgp / idcgp;
352    }
353  }
354}
Note: See TracBrowser for help on using the repository browser.