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

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab 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.
 *
 * HeuristicLab 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 HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
using HeuristicLab.Analysis;
using HeuristicLab.Common.Resources;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.MainForm;
using HeuristicLab.Optimization;
using HeuristicLab.OptimizationExpertSystem.Common;
using HeuristicLab.PluginInfrastructure;

namespace HeuristicLab.OptimizationExpertSystem {
  [View("Performance Modeling View")]
  [Content(typeof(KnowledgeCenter), IsDefaultView = false)]
  public partial class PerformanceModelingView : KnowledgeCenterViewBase {
    private readonly CheckedItemList<StringValue> characteristics;

    public PerformanceModelingView() {
      InitializeComponent();
      characteristics = new CheckedItemList<StringValue>();
      characteristics.CheckedItemsChanged += CharacteristicsOnCheckedItemsChanged;
      characteristicsViewHost.Content = characteristics;
      recommendStartButton.Text = string.Empty;
      recommendStartButton.Image = VSImageLibrary.Play;
      refreshCharacteristicsButton.Text = string.Empty;
      refreshCharacteristicsButton.Image = VSImageLibrary.Refresh;
      UpdateRecommenderCombobox();
    }

    protected override void OnContentChanged() {
      base.OnContentChanged();
      if (Content == null) {
        minTargetView.Content = null;
      } else {
        minTargetView.Content = Content.MinimumTarget;
      }
      UpdateCharacteristics();
      UpdateTopNCombobox();
    }

    protected override void SetEnabledStateOfControls() {
      base.SetEnabledStateOfControls();
      // TODO: up/download state
      recommendStartButton.Enabled = Content != null && recommenderComboBox.SelectedIndex >= 0 && characteristics.CheckedItems.Any();
      characteristicsViewHost.Enabled = Content != null;
      xValidateButton.Enabled = Content != null && recommenderComboBox.SelectedIndex >= 0 && characteristics.CheckedItems.Any() && topNComboBox.SelectedIndex >= 0;
    }

    #region Update Controls
    private void UpdateRecommenderCombobox() {
      if (InvokeRequired) { Invoke((Action)UpdateRecommenderCombobox); return; }
      var prevSelection = (IAlgorithmInstanceRecommender)recommenderComboBox.SelectedItem;
      var prevNewIndex = -1;
      recommenderComboBox.Items.Clear();

      var i = 0;
      foreach (var rcmd in ApplicationManager.Manager.GetInstances<IAlgorithmInstanceRecommender>()) {
        recommenderComboBox.Items.Add(rcmd);
        if (prevSelection == null || rcmd.GetType() == prevSelection.GetType())
          prevNewIndex = prevSelection == null ? 0 : i;
        i++;
      }
      
      recommenderComboBox.SelectedIndex = prevNewIndex;
    }

    private void UpdateCharacteristics() {
      if (InvokeRequired) { Invoke((Action)UpdateCharacteristics); return; }

      var @checked = new HashSet<string>(characteristics.CheckedItems.Select(x => x.Value.Value));
      if (@checked.Count == 0 && Content.ProblemInstances.ResultNames.Any(x => x.StartsWith("Characteristic.")))
        @checked = new HashSet<string>(Content.ProblemInstances.ResultNames.Where(x => x.StartsWith("Characteristic.")));

      characteristics.Clear();
      if (Content == null || Content.ProblemInstances.Count == 0) return;

      foreach (var c in Content.ProblemInstances.ResultNames) {
        characteristics.Add(new StringValue(c), @checked.Contains(c));
      }
    }

    private void UpdateTopNCombobox() {
      if (InvokeRequired) { Invoke((Action)UpdateTopNCombobox); return; }

      int selected = 3;
      if (topNComboBox.SelectedIndex >= 0) selected = (int)topNComboBox.SelectedItem;
      topNComboBox.Items.Clear();
      if (Content == null) return;

      var algInstances = Content.AlgorithmInstances.Count;
      for (var i = 1; i <= algInstances; i++) {
        topNComboBox.Items.Add(i);
      }
      topNComboBox.SelectedIndex = Math.Min(selected, topNComboBox.Items.Count) - 1;
    }
    #endregion

    #region Content Event Handlers
    protected override void OnProblemInstancesChanged() {
      base.OnProblemInstancesChanged();
      UpdateCharacteristics();
      SetEnabledStateOfControls();
    }

    protected override void OnAlgorithmInstancesChanged() {
      base.OnAlgorithmInstancesChanged();
      UpdateTopNCombobox();
    }
    #endregion

    #region Control Event Handlers
    private void RecommenderComboBoxOnSelectedIndexChanged(object sender, EventArgs e) {
      if (InvokeRequired) { Invoke((Action<object, EventArgs>)RecommenderComboBoxOnSelectedIndexChanged, sender, e); return; }
      var rcmd = (IAlgorithmInstanceRecommender)recommenderComboBox.SelectedItem;
      parameterCollectionView.Content = rcmd != null ? rcmd.Parameters : null;
      SetEnabledStateOfControls();
    }

    private void RecommendStartButtonOnClick(object sender, EventArgs e) {
      var rcmd = (IAlgorithmInstanceRecommender)recommenderComboBox.SelectedItem;
      var trainingSet = Content.ProblemInstances.Where(x => !Content.IsCurrentInstance(x)).ToArray();
      Content.RecommendationModel = rcmd.TrainModel(trainingSet, Content, characteristics.CheckedItems.Select(x => x.Value.Value).ToArray());
    }

    private void RefreshCharacteristicsButtonOnClick(object sender, EventArgs e) {
      UpdateCharacteristics();
      SetEnabledStateOfControls();
    }

    private void xValidateButton_Click(object sender, EventArgs e) {
      var recommender = (IAlgorithmInstanceRecommender)recommenderComboBox.SelectedItem;
      var progress = MainForm.AddOperationProgressToView(this, "Performing Leave-one-out Crossvalidation");
      var topN = (int)topNComboBox.SelectedItem;
      Task.Factory.StartNew(() => { DoCrossvalidate(recommender, topN, progress); }, TaskCreationOptions.LongRunning);
    }

    private void topNComboBox_SelectedIndexChanged(object sender, EventArgs e) {
      SetEnabledStateOfControls();
    }
    #endregion

    #region Other Event Handlers
    private void CharacteristicsOnCheckedItemsChanged(object sender, EventArgs e) {
      SetEnabledStateOfControls();
    }
    #endregion
    
    private void DoCrossvalidate(IAlgorithmInstanceRecommender recommender, int topN, IProgress progress) {
      try {
        var features = characteristics.CheckedItems.Select(x => x.Value.Value).ToArray();
        var trainingSet = Content.ProblemInstances.Where(x => !Content.IsCurrentInstance(x)).ToArray();

        var absErr = 0.0;
        var absErrCnt = 0;
        var absLogErr = 0.0;
        var absLogErrCnt = 0;
        var confMatrix = new int[1, 6];
        var tau = 0.0;
        var tauCnt = 0;
        var rho = 0.0;
        var rhoCnt = 0;
        var ndcg = 0.0;
        var ndcgCnt = 0;
        // leave one out crossvalidation
        var count = 0;
        foreach (var pi in trainingSet) {
          var observed = Content.GetAlgorithmPerformanceLog10(pi);
          if (observed.Count == 0) continue;
          progress.Status = pi.Name + "...";
          var model = recommender.TrainModel(trainingSet.Where(x => x != pi).ToArray(), Content, features);
          var predictedTopN = model.GetRanking(pi).Take(topN).ToDictionary(x => x.Key, x => Math.Log10(x.Value));
          var predicted = model.GetRanking(pi).ToDictionary(x => x.Key, x => Math.Log10(x.Value));
          var ae = AbsoluteError(observed, predictedTopN);
          if (!double.IsNaN(ae)) {
            absErr += ae; // in case we only predicted instances that have not been observed
            absErrCnt++;
          }
          var ale = AbsoluteLogError(observed, predictedTopN);
          if (!double.IsNaN(ale)) {
            absLogErr += ale; // in case we only predicted instances that have not been observed
            absLogErrCnt++;
          }
          var confMat = ConfusionMatrix(observed, predictedTopN);
          for (var i = 0; i < confMat.Length; i++) {
            confMatrix[0, i] += confMat[i];
          }
          var kt = KendallsTau(observed, predicted);
          if (!double.IsNaN(kt) && !double.IsInfinity(kt)) {
            tau += kt;
            tauCnt++;
          }
          var sr = SpearmansRho(observed, predicted);
          if (!double.IsNaN(sr)) {
            rho += sr;
            rhoCnt++;
          }
          var gain = NDCG(observed, model.GetRanking(pi).Take(topN).Select(x => x.Key).ToList());
          if (!double.IsNaN(gain)) {
            ndcg += gain;
            ndcgCnt++;
          }
          progress.ProgressValue = ++count / (double)trainingSet.Length;
        }
        absErr /= absErrCnt;
        absLogErr /= absLogErrCnt;
        tau /= tauCnt;
        rho /= rhoCnt;
        ndcg /= ndcgCnt;

        absoluteErrorView.Content = new DoubleValue(absErr);
        absoluteLogErrorView.Content = new DoubleValue(absLogErr);
        var description = new[] {"A", "B", "C", "D", "E", "F"};
        confusionMatrixView.Content = new IntMatrix(confMatrix) {ColumnNames = description};
        kendallsTauView.Content = new DoubleValue(tau);
        spearmansRhoView.Content = new DoubleValue(rho);
        ncdgView.Content = new DoubleValue(ndcg);
      } finally { progress.Finish(); }
    }

    private static double AbsoluteError(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
      var error = 0.0;
      var count = 0;
      foreach (var tuple in ranking) {
        double actual;
        if (!performance.TryGetValue(tuple.Key, out actual)) continue;
        if (double.IsInfinity(actual)) actual = Math.Log10(int.MaxValue);
        error += Math.Abs(Math.Pow(10, actual) - Math.Pow(10, tuple.Value));
        count++;
      }
      return error / count;
    }

    private static double AbsoluteLogError(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
      var error = 0.0;
      var count = 0;
      foreach (var tuple in ranking) {
        double actual;
        if (!performance.TryGetValue(tuple.Key, out actual)) continue;
        if (double.IsInfinity(actual)) actual = Math.Log10(int.MaxValue);
        error += Math.Abs(actual - tuple.Value);
        count++;
      }
      return error / count;
    }

    private static int[] ConfusionMatrix(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
      var confMatrix = new int[6];
      var clusteredPerformance = ClusteringHelper<IAlgorithm>.Cluster(5, performance, a => double.IsInfinity(a.Value)).GetByInstance().ToDictionary(x => x.Key, x => x.Value.Item2);
      
      foreach (var cr in ranking) {
        int realRank;
        if (!clusteredPerformance.TryGetValue(cr.Key, out realRank)) continue;
        confMatrix[realRank]++;
      }
      return confMatrix;
    }

    private static double SpearmansRho(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
      var commonKeys = performance.Keys.Intersect(ranking.Keys).ToList();
      var n = commonKeys.Count;
      if (n == 0) return double.NaN;

      var actualRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = performance[x] })
                                  .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = double.IsPositiveInfinity(x.Perf) ? int.MaxValue : i })
                                  .OrderBy(x => x.Index).Select(x => (double)x.Rank).ToArray();
      var predictedRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = ranking[x] })
                                     .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = double.IsPositiveInfinity(x.Perf) ? int.MaxValue : i })
                                     .OrderBy(x => x.Index).Select(x => (double)x.Rank).ToArray();

      return alglib.spearmancorr2(actualRanks, predictedRanks);
    }

    private static double KendallsTau(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
      var commonKeys = performance.Keys.Intersect(ranking.Keys).ToList();
      var n = commonKeys.Count;
      if (n == 0) return double.NaN;

      var actualRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = performance[x] })
                                  .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = double.IsPositiveInfinity(x.Perf) ? int.MaxValue : i })
                                  .OrderBy(x => x.Index).Select(x => x.Rank).ToList();
      var predictedRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = ranking[x] })
                                     .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = double.IsPositiveInfinity(x.Perf) ? int.MaxValue : i })
                                     .OrderBy(x => x.Index).Select(x => x.Rank).ToList();

      var paired = actualRanks.Zip(predictedRanks, (a, p) => new { Actual = a, Predicted = p }).ToList();
      var concordant = 0;
      var discordant = 0;
      for (var i = 0; i < paired.Count - 1; i++)
        for (var j = i + 1; j < paired.Count; j++) {
          if (paired[i].Actual > paired[j].Actual && paired[i].Predicted > paired[j].Predicted
            || paired[i].Actual < paired[j].Actual && paired[i].Predicted < paired[j].Predicted)
            concordant++;
          else if (paired[i].Actual > paired[j].Actual && paired[i].Predicted < paired[j].Predicted
            || paired[i].Actual < paired[j].Actual && paired[i].Predicted > paired[j].Predicted)
            discordant++;
        }

      var ti = performance.GroupBy(x => x.Value).Sum(x => x.Count() * (x.Count() - 1));
      var uj = ranking.GroupBy(x => x.Value).Sum(x => x.Count() * (x.Count() - 1));
      return (2.0 * (concordant - discordant)) / Math.Sqrt( (n * (n - 1) - ti * (ti - 1)) * (n * (n - 1) - uj * (uj - 1)) );
    }

    private static double NDCG(Dictionary<IAlgorithm, double> performance, List<IAlgorithm> ranking) {
      var k = 5;
      var relevance = ClusteringHelper<IAlgorithm>.Cluster(k, performance, a => double.IsInfinity(a.Value)).GetByInstance().ToDictionary(x => x.Key, x => k - x.Value.Item2);
      
      var i = 0;
      var dcgp = 0.0;
      for (; i < ranking.Count; i++) {
        int rel;
        if (!relevance.TryGetValue(ranking[i], out rel))
          continue;
        dcgp = rel;
        i++;
        break;
      }
      for (; i < ranking.Count; i++) {
        int rel;
        if (!relevance.TryGetValue(ranking[i], out rel))
          continue;
        dcgp += rel / Math.Log(i + 1, 2);
      }
      var ideal = relevance.Select(x => x.Value).OrderByDescending(x => x).Take(ranking.Count).ToArray();
      double idcgp = ideal[0];
      for (i = 1; i < ideal.Length; i++)
        idcgp += ideal[i] / Math.Log(i + 1, 2);

      return dcgp / idcgp;
    }
  }
}