Le laboratoire de science des données
Exécute les tests à l’aide de la simulation C#
Dr. James McCaffrey de Microsoft Research utilise un programme de code complet pour une explication étape par étape de cette technique d’apprentissage automatique qui indique si les modèles sont aléatoires.
Supposons que vous observiez une séquence de personnes entrant dans un magasin et que vous notiez la couleur de la chemise portée par chaque personne. Vous voyez cette séquence de 24 chemises :
0, 0, 3, 3, 2, 1, 1, 2, 0, 0, 3, 3, 2, 0, 0, 1, 1, 2, 2, 2, 2, 0, 1, 1
où 0 = chemise blanche, 1 = jaune, 2 = rouge, 3 = noir. Vous souhaitez savoir si le motif est aléatoire ou non. Le modèle ne semble pas très aléatoire, mais comment pouvez-vous quantifier cette observation ? Ceci est un exemple de test d’exécution.
Il est peu probable que vous vouliez examiner les couleurs des chemises des acheteurs, mais il existe de nombreux exemples où l’analyse des informations sur les tirages est significative. Par exemple, si vous disposez de quatre serveurs Web configurés de sorte que la charge soit conçue pour être partagée de manière égale, un modèle tel que celui ci-dessus peut indiquer un problème avec l’équilibreur de charge.
Une bonne façon de voir où va cet article est de jeter un coup d’œil à la capture d’écran d’un programme de démonstration dans Figure 1. La démo met en place la séquence de 24 valeurs présentées ci-dessus. La séquence comporte 13 passages :
(0 0), (3 3), (2), (1 1), (2), (0 0), (3 3), (2), (0 0), (1 1), (2 2 2 2), (0), (1 1)
Une analyse est un ensemble de points de données consécutifs identiques. La démo brouille ensuite la séquence 1 000 000 fois et calcule le nombre observé d’exécutions pour chaque séquence aléatoire. Sur les 1 000 000 d’itérations, le nombre moyen d’exécutions d’une séquence aléatoire (avec la même composition de points de données) est de 18,75, ce qui est un peu plus que les 13 exécutions observées dans les données. Il semble donc que la séquence ait en fait trop peu d’exécutions si la séquence était vraiment générée de manière aléatoire.
La démo estime la probabilité de voir moins de 13 courses dans une séquence aléatoire de deux manières différentes. La première technique utilise le fait que sur de nombreuses itérations, le nombre d’exécutions est approximativement distribué normalement (courbe en forme de cloche). L’estimation de la probabilité statistique est de 0,0019 – seulement environ 2 sur 1 000 – possible, mais très peu probable.
La deuxième technique utilise une technique de comptage brut. Dans les 1 000 000 d’itérations, il y avait 13 exécutions ou moins dans une séquence aléatoire seulement 4 888 + 1 370 313 + 59 + 13 + 1 = 6 644 fois, ce qui représente une probabilité estimée de 0,0066 — seulement environ 7 sur 1 000. Encore une fois, possible, mais très peu probable.
La conclusion est que le modèle original pourrait être aléatoire, mais c’est très peu probable. Un processus impliqué qui n’est pas aléatoire est probablement responsable de la séquence observée.
Cet article suppose que vous avez des compétences de programmation intermédiaires ou supérieures avec le langage C #, mais ne suppose pas que vous savez quoi que ce soit sur les tests d’exécution. Le code de démonstration complet et les données associées sont présentés dans cet article. Le code source et les données sont également disponibles dans le téléchargement qui l’accompagne. Toutes les vérifications d’erreur normales ont été supprimées pour garder les idées principales aussi claires que possible.
Le programme de démonstration
Le programme de démonstration complet, avec quelques modifications mineures pour gagner de la place, est présenté dans Liste 1. Pour créer le programme, j’ai lancé Visual Studio et créé une nouvelle application console C# .NET Core nommée RunsTestSim. J’ai utilisé Visual Studio 2022 (édition communautaire gratuite) avec .NET Core 6.0, mais la démo n’a pas de dépendances significatives, donc n’importe quelle version de Visual Studio et de la bibliothèque .NET fonctionnera correctement. Vous pouvez également utiliser le programme Visual Studio Code.
Une fois le code du modèle chargé, dans la fenêtre de l’éditeur, j’ai supprimé toutes les références d’espace de noms inutiles, ne laissant que la référence à l’espace de noms système de niveau supérieur. Dans la fenêtre de l’Explorateur de solutions, j’ai cliqué avec le bouton droit sur le fichier Program.cs, je l’ai renommé en RunsTestSimProgram.cs, plus descriptif, et j’ai autorisé Visual Studio à renommer automatiquement la classe Program en RunsTestSimProgram.
Liste 1 :
Exécute le code de démonstration de simulation de test
using System; // .NET 6.0
namespace RunsTestSim
{
internal class RunsTestSimProgram
{
static void Main(string[] args)
{
Console.WriteLine("nBegin test sequence runs using" +
" simulation ");
Random rnd = new Random(0);
int[] seq = new int[24] { 0, 0, 3, 3, 2, 1, 1, 2, 0, 0,
3, 3, 2, 0, 0, 1, 1, 2, 2, 2, 2, 0, 1, 1 }; // too few runs
Console.WriteLine("nObserved sequence: ");
ShowSeq(seq, 40); // 40 vals per line
int obsRuns = NumRuns(seq); // 13 observed
Console.WriteLine("nObserved number runs: " + obsRuns);
int[] counts = new int[25]; // count of runs
int[] scratch = new int[24];
Array.Copy(seq, scratch, seq.Length);
int nTrials = 1_000_000; // C# 7.0 syntax
Console.WriteLine("nStart simulation with nTrials = " +
nTrials);
for (int i = 0; i < nTrials; ++i)
{
Shuffle(scratch, rnd);
int r = NumRuns(scratch);
++counts[r];
}
Console.WriteLine("Done ");
Console.WriteLine("nCounts of runs from simulation: ");
ShowCounts(counts, 40);
double mean = Mean(counts);
Console.WriteLine("nMean number runs for simulation: " +
mean.ToString("F2"));
double v = Variance(counts, mean);
Console.WriteLine("nVariance for simulation: " +
v.ToString("F2"));
// no continutiy correction
double z = (obsRuns - mean) / Math.Sqrt(v);
Console.WriteLine("nComputed z (no continuity correction): " +
z.ToString("F4"));
// with continuity correction
// double z = 0.0;
// if (obsRuns > mean) // right tail
// z = ((obsRuns - mean) - 0.5) / Math.Sqrt(v);
// else // obsRuns < mean : left-tail
// z = ((obsRuns - mean) + 0.5) / Math.Sqrt(v);
// Console.WriteLine("nComputed z (with continuity correction): " +
// z.ToString("F4"));
double p = OneTail(z); //
Console.WriteLine("nApproximate one-tail probability if random: " +
p.ToString("F4"));
double likely = 0.0;
if (obsRuns > mean)
likely = Likelihood(counts, obsRuns, "right");
else
likely = Likelihood(counts, obsRuns, "left");
Console.WriteLine("nEmpirical one-tail likelihood if random: " +
likely.ToString("F4"));
Console.WriteLine("nEnd sequence runs example ");
Console.ReadLine();
} // Main()
static double OneTail(double z)
{
// raw z could be pos or neg
if (z < 0.0) z = -z; // make it positive is usual
double p = 1.0 - Phi(z); // from z to +infinity
return p;
}
//static double TwoTail(double z)
//{
// // likehood of z, z is positive
// double rightTail = 1.0 - Phi(z); // z to +infinity
// return 2.0 * rightTail;
//}
static double Phi(double z)
{
// cumulative density of Standard Normal
// erf is Abramowitz and Stegun 7.1.26
if (z < -6.0)
return 0.0;
else if (z > 6.0)
return 1.0;
double a0 = 0.3275911;
double a1 = 0.254829592;
double a2 = -0.284496736;
double a3 = 1.421413741;
double a4 = -1.453152027;
double a5 = 1.061405429;
int sign = 0;
if (z < 0.0)
sign = -1;
else
sign = 1;
double x = Math.Abs(z) / Math.Sqrt(2.0);
double t = 1.0 / (1.0 + a0 * x);
double erf = 1.0 - (((((a5 * t + a4) * t) + a3) *
t + a2) * t + a1) * t * Math.Exp(-x * x);
return 0.5 * (1.0 + (sign * erf));
}
static int NumRuns(int[] seq)
{
int runs = 0;
int last = -1;
for (int i = 0; i < seq.Length; i++)
{
if (seq[i] != last)
{
++runs;
last = seq[i];
}
}
return runs;
}
static double Likelihood(int[] counts, int obsRuns, string leftOrRight)
{
int countOutsideObsRuns = 0;
int totalCount = 0;
for (int i = 0; i < counts.Length; ++i)
{
// i is a runs count, [i] is a freq
totalCount += counts[i];
if (leftOrRight == "left")
{
if (i <= obsRuns) countOutsideObsRuns += counts[i];
}
else if (leftOrRight == "right")
{
if (i >= obsRuns) countOutsideObsRuns += counts[i];
}
}
return (countOutsideObsRuns * 1.0) / totalCount;
}
static double Mean(int[] counts)
{
int sum = 0;
int n = 0; // number of values
for (int i = 0; i < counts.Length; ++i)
{
sum += i * counts[i]; // i is number runs, [i] is freq
n += counts[i];
}
double mean = (sum * 1.0) / n;
return mean;
}
static double Variance(int[] counts, double mean)
{
double sumSquares = 0.0;
int n = 0;
for (int i = 0; i < counts.Length; ++i)
{
sumSquares += counts[i] * ((i - mean) * (i - mean));
n += counts[i];
}
return sumSquares / n;
}
static void Shuffle(int[] seq, Random rnd)
{
int n = seq.Length;
for (int i = 0; i < n; ++i)
{
int ri = rnd.Next(i, n); // be careful
int tmp = seq[ri];
seq[ri] = seq[i];
seq[i] = tmp;
}
}
static void ShowSeq(int[] seq, int n)
{
for (int i = 0; i < seq.Length; i++)
{
Console.Write(seq[i] + " ");
if ((i + 1) % n == 0)
Console.WriteLine("");
}
Console.WriteLine("");
}
static void ShowCounts(int[] counts, int n)
{
// n is number values per line
for (int i = 0; i < counts.Length; i++)
{
Console.Write(counts[i] + " ");
if ((i + 1) % n == 0)
Console.WriteLine("");
}
Console.WriteLine("");
}
} // Program
} // ns
Le programme de démonstration commence par configurer une séquence à analyser et un objet Random pour brouiller la séquence :
Random rnd = new Random(0);
int[] seq = new int[24] { 0, 0, 3, 3, 2, 1, 1, 2, 0, 0,
3, 3, 2, 0, 0, 1, 1, 2, 2, 2, 2, 0, 1, 1 }; // too few runs
La valeur de départ aléatoire de 0 est arbitraire. Ensuite, le nombre d'exécutions observées dans la séquence est calculé à l'aide d'une fonction d'assistance définie par le programme NumRuns() :
int obsRuns = NumRuns(seq); // 13 observed
Console.WriteLine("nObserved number runs: " + obsRuns);
Par rapport à certaines techniques statistiques classiques alternatives telles que Wald-Wolfowitz, l'un des avantages de l'approche par simulation est qu'elle peut gérer de très longues séquences. Ainsi, bien que vous puissiez compter manuellement le nombre d'exécutions dans la séquence examinée, l'utilisation d'une fonction d'assistance pour compter les exécutions est une meilleure approche.
Ensuite, la démo configure un tableau pour contenir le nombre d'exécutions vues dans la simulation et fait une copie de la séquence source :
int[] counts = new int[25]; // count of runs int[] scratch = new int[24]; Array.Copy(seq, scratch, seq.Length);
Notez que, comme la séquence source comporte 24 éléments, le nombre maximal d'exécutions est de 24. Mais pour stocker le nombre de fois où 24 exécutions sont apparues, vous devez déclarer une taille de tableau de 25 en raison de l'indexation à partir de zéro.
Le cœur de la simulation est :
int nTrials = 1_000_000; // C# 7.0 syntax
Console.WriteLine("nStart simulation with nTrials = " +
nTrials);
for (int i = 0; i < nTrials; ++i)
{
Shuffle(scratch, rnd);
int r = NumRuns(scratch);
++counts[r];
}
Console.WriteLine("Done ");
Dans chacun des 1 000 000 d'essais, la copie de la séquence source est brouillée dans un ordre aléatoire à l'aide d'une fonction Shuffle() définie par le programme. Après le brouillage, le nombre d'exécutions dans la séquence brouillée est calculé et stocké.
Après la simulation, la démo calcule le nombre moyen (moyen) d'exécutions vues et la variance des exécutions vues :
double mean = Mean(counts);
Console.WriteLine("nMean number runs for simulation: " +
mean.ToString("F2"));
double v = Variance(counts, mean);
Console.WriteLine("nVariance for simulation: " +
v.ToString("F2"));
La moyenne est nécessaire à la fois pour l'estimation statistique et pour l'estimation empirique de la probabilité de voir le nombre observé d'essais. La variance n'est nécessaire que pour l'estimation statistique.
L'estimation statistique est calculée comme suit :
double z = (obsRuns - mean) / Math.Sqrt(v);
Console.WriteLine("nComputed z (no continuity correction): " +
z.ToString("F4"));
double p = OneTail(z); //
Console.WriteLine("nApproximate one-tail probability if random: " +
p.ToString("F4"));
La fonction OneTail() définie par le programme estime la probabilité de voir moins que le nombre observé d'exécutions (13) si la séquence est aléatoire (18,75 exécutions).
Les conclusions de la démonstration en calculant une estimation de probabilité basée sur le nombre d'exécutions de la simulation :
double likely = 0.0;
if (obsRuns > mean)
likely = Likelihood(counts, obsRuns, "right");
else
likely = Likelihood(counts, obsRuns, "left");
Console.WriteLine("nEmpirical one-tail likelihood if random: " +
likely.ToString("F4"));
La fonction Likelihood() définie par le programme parcourt les comptages[] tableau et ajoute le nombre de fois qu'il y a eu 13 exécutions ou moins.
Comprendre l'approche d'estimation statistique
L'idée clé derrière l'estimation de la probabilité de voir un nombre observé d'exécutions dans une séquence est que pour un grand nombre d'itérations de simulation, le nombre d'exécutions vues sera approximativement normal (également appelé gaussien ou en forme de cloche). Le graphique dans Figure 2 montre la distribution du nombre d'exécutions observées sur 1 000 000 d'itérations.
Le graphique montre que le nombre moyen d'exécutions est d'environ 19 et que l'écart type (mesure de la propagation) est d'environ (24 - 12)/6 = 2,0. La variance des données est l'écart type au carré, soit environ 2,0^2 = 4,0. Si vous vous référez à la démo exécutée dans Figure 1la moyenne calculée réelle est de 18,75 et la variance calculée réelle est de 3,94.
.