Tâche

Mettre en œuvre un programme en octets minimum de code source ou binaire qui fait la reconnaissance vocale d'un échantillon vocal (moi en disant "oui", "oui" ou "non" en voix ou en chuchotement, clairement ou bizarrement) basé sur des échantillons d'apprentissage avec une précision maximale .

Le programme devrait lire train/yes0.wav, train/no0.wav, train/yes1.wavet ainsi de suite (il y a 400 ouis et 400 NoE dans les données de formation), puis commencer à lire inputs/0.wav, inputs/1.wavjusqu'à ce qu'il ne trouve pas le fichier, l' analyse et la sortie « oui » ou « non » (ou tout autre mot pour réponse intermédiaire).

Si vous le souhaitez, vous pouvez pré-former le programme au lieu de lire train/, mais le tableau de données résultant compte pour le score (et méfiez-vous du surajustement des échantillons de formation - ils ne chevauchent pas ceux de l'examen). Mieux vaut inclure le programme utilisé pour produire le tableau de données comme addendum dans ce cas.

Tous les exemples de fichiers sont de petits fichiers WAV stéréo 16 bits endian, uniquement à partir du micro d'un ordinateur portable, sans filtrage / réduction du bruit.

Limites

Fonctionnalités interdites:

• Utilisation du réseau;
• Essayer d'accéder au fichier de réponses inputs/key;
• Détournement du runnerprogramme qui calcule la précision;
• Utilisation des bibliothèques de reconnaissance existantes. La liaison avec l'implémentation FFT n'est pas autorisée: seules les fonctions mathématiques externes prenant une quantité constante d'informations (comme sinou atan2) sont autorisées; Si vous voulez la FFT, ajoutez simplement son implémentation au code source de votre programme (il peut être multilingue si nécessaire).

Limites des ressources:

• Le programme ne devrait pas prendre plus de 30 minutes de temps processeur sur mon ordinateur portable i5. Si cela prend plus, seule la sortie produite dans les 30 premières minutes est comptée et tout le reste est supposé une demi-correspondance;
• Limite de mémoire: 1 Go (y compris tous les fichiers temporaires);

Outils

Le tools/runnerprogramme exécute automatiquement votre solution et calcule la précision.

$ tools/runner solutions/example train train/key 
Accuracy: 548 ‰

Il peut examiner le programme à l'aide de données de formation ou à l'aide de données d'examen réelles. Je vais essayer de soumettre les réponses sur l'ensemble de données d'examen et publier les résultats (pourcentage de précision) jusqu'à ce que je rende l'ensemble de données public.

Notation

Il existe 5 classes de solutions selon la précision:

• Tous les échantillons ont deviné correctement: Classe 0;
• Précision 950-999: Classe 1;
• Précision 835-950: classe 2;
• Précision 720-834: classe 3;
• Précision 615-719: classe 4;

À l'intérieur de chaque classe, le score est le nombre d'octets que prend la solution.

Réponse acceptée: la plus petite solution dans la meilleure classe non vide.

Liens

• Projet Github avec outils: https://github.com/vi/codegolf-jein
• Ensemble de données de formation: http://vi-server.org/pub/codegolf-jein-train.tar.xz
• Le jeu de données d'examen est maintenu privé jusqu'à présent, il existe des sommes de contrôle (HMAC) disponibles dans le référentiel Github.

Tous les échantillons doivent être considérés comme CC-0 (domaine public), les scripts et les programmes doivent être considérés comme MIT.

Exemple de solution

Il offre une très mauvaise qualité de reconnaissance, montre simplement comment lire les fichiers et afficher les réponses

#define _BSD_SOURCE
#include <stdio.h>
#include <assert.h>
#include <endian.h>


#define Nvols 30

#define BASS_WINDOW 60
#define MID_WINDOW 4

struct training_info {
    double bass_volumes[Nvols];
    double mid_volumes[Nvols];
    double treble_volumes[Nvols];
    int n;
};


struct training_info yes;
struct training_info no;

static int __attribute__((const)) mod(int n, int d) {
    int m = n % d;
    if (m < 0) m+=d;
    return m;
}

// harccoded to 2 channel s16le
int get_file_info(const char* name, struct training_info *inf) {
    FILE* in = fopen(name, "rb");

    if (!in) return -1;

    setvbuf(in, NULL, _IOFBF, 65536);

    inf->n = 1;

    fseek(in, 0, SEEK_END);
    long filesize = ftell(in);
    fseek(in, 128, SEEK_SET);
    filesize -= 128; // exclude header and some initial samples

    int nsamples = filesize / 4; 

    double bass_a=0, mid_a=0;
    const int HISTSIZE  = 101;
    double xhistory[HISTSIZE];
    int histpointer=0;
    int histsize = 0;

    //FILE* out = fopen("debug.raw", "wb");

    int i;
    for (i=0; i<Nvols; ++i) {
        int j;

        double total_vol = 0;
        double bass_vol = 0;
        double mid_vol = 0;
        double treble_vol = 0;

        for (j=0; j<nsamples / Nvols; ++j) {
            signed short int l, r; // a sample
            if(fread(&l, 2, 1, in)!=1) break;
            if(fread(&r, 2, 1, in)!=1) break;
            double x = 1/65536.0 * ( le16toh(l) + le16toh(r) );


            bass_a += x;
            mid_a  += x;


            if (histsize == HISTSIZE-1) bass_a   -= xhistory[mod(histpointer-BASS_WINDOW,HISTSIZE)];
            if (histsize == HISTSIZE-1) mid_a    -= xhistory[mod(histpointer-MID_WINDOW ,HISTSIZE)];

            double bass = bass_a / BASS_WINDOW;
            double mid = mid_a / MID_WINDOW - bass;
            double treble = x - mid_a/MID_WINDOW;

            xhistory[histpointer++] = x;
            if(histpointer>=HISTSIZE) histpointer=0;
            if(histsize < HISTSIZE-1) ++histsize;

            total_vol  += bass*bass + mid*mid + treble*treble;
            bass_vol   += bass*bass;
            mid_vol    += mid*mid;
            treble_vol += treble*treble;


            /*
            signed short int y;
            y = 65536 * bass;

            y = htole16(y);
            fwrite(&y, 2, 1, out);
            fwrite(&y, 2, 1, out);
            */
        }

        inf->bass_volumes[i] = bass_vol / total_vol;
        inf->mid_volumes[i] = mid_vol / total_vol;
        inf->treble_volumes[i] = treble_vol / total_vol;

        //fprintf(stderr, "%lf %lf %lf    %s\n", inf->bass_volumes[i], inf->mid_volumes[i], inf->treble_volumes[i], name);
    }
    fclose(in);

    return 0;
}

static void zerotrdata(struct training_info *inf) {
    int i;
    inf->n = 0;
    for (i=0; i<Nvols; ++i) {
        inf->bass_volumes[i] = 0;
        inf->mid_volumes[i] = 0;
        inf->treble_volumes[i] = 0;
    }
}

static void train1(const char* prefix, struct training_info *inf) 
{
    char buf[50];

    int i;

    for(i=0;; ++i) {
        sprintf(buf, "%s%d.wav", prefix, i);
        struct training_info ti;
        if(get_file_info(buf, &ti)) break;

        ++inf->n;

        int j;
        for (j=0; j<Nvols; ++j) {
            inf->bass_volumes[j]   += ti.bass_volumes[j];
            inf->mid_volumes[j]    += ti.mid_volumes[j];
            inf->treble_volumes[j] += ti.treble_volumes[j];
        }
    }

    int j;
    for (j=0; j<Nvols; ++j) {
        inf->bass_volumes[j]   /= inf->n;
        inf->mid_volumes[j]    /= inf->n;
        inf->treble_volumes[j] /= inf->n;
    }
}

static void print_part(struct training_info *inf, FILE* f) {
    fprintf(f, "%d\n", inf->n);
    int j;
    for (j=0; j<Nvols; ++j) {
        fprintf(f, "%lf %lf %lf\n", inf->bass_volumes[j], inf->mid_volumes[j], inf->treble_volumes[j]);
    }
}

static void train() {
    zerotrdata(&yes);
    zerotrdata(&no);

    fprintf(stderr, "Training...\n");

    train1("train/yes", &yes);
    train1("train/no", &no);

    fprintf(stderr, "Training completed.\n");

    //print_part(&yes, stderr);
    //print_part(&no, stderr);

    int j;
    for (j=0; j<Nvols; ++j) {
        if (yes.bass_volumes[j]   > no.bass_volumes[j]) {   yes.bass_volumes[j] = 1;   no.bass_volumes[j] = 0; }
        if (yes.mid_volumes[j]    > no.mid_volumes[j]) {    yes.mid_volumes[j] = 1;    no.mid_volumes[j] = 0; }
        if (yes.treble_volumes[j] > no.treble_volumes[j]) { yes.treble_volumes[j] = 1; no.treble_volumes[j] = 0; }
    }
}


double delta(struct training_info *t1, struct training_info *t2) {
    int j;
    double d = 0;
    for (j=0; j<Nvols; ++j) {
        double rb = t1->bass_volumes[j] - t2->bass_volumes[j];
        double rm = t1->mid_volumes[j] - t2->mid_volumes[j];
        double rt = t1->treble_volumes[j] - t2->treble_volumes[j];
        d += rb*rb + rm*rm + rt*rt;
    }
    return d;
}

int main(int argc, char* argv[])
{
    (void)argc; (void)argv;

    train();


    int i;

    int yes_count = 0;
    int no_count = 0;

    for (i=0;; ++i) {
        char buf[60];
        sprintf(buf, "inputs/%d.wav", i);

        struct training_info ti;

        if(get_file_info(buf, &ti)) break;

        double dyes = delta(&yes, &ti);
        double dno = delta(&no, &ti);

        //printf("%lf %lf %s ", dyes, dno, buf);

        if (dyes > dno) {
            printf("no\n");
            ++no_count;
        } else  {
            printf("yes\n");
            ++yes_count;
        }
    }

    fprintf(stderr, "yeses: %d noes: %d\n", yes_count, no_count);

}

C ++ 11 (gcc; 1639 1625 1635 octets, classe 1, score = 983, 960)

Commençons. C'est probablement le code le plus long que j'aie jamais raccourci ...

#include <bits/stdc++.h>
#define $ complex<double>
#define C vector<$>
#define I int
#define D double
#define P pair<D,I>
#define Q pair<D,D>
#define E vector<D>
#define V vector<P>
#define W vector<Q>
#define S char*
#define Z(x)if(fread(&x,2,1,y)!=1)break;
#define B push_back
#define F(i,f,t)for(I i=f;i<t;i++)
#define _ return
#define J first
#define L second
const I K=75,O=16384;using namespace std;C R(C&i,I s,I o=0,I d=1){if(!s)_ C(1,i[o]);C l=R(i,s/2,o,d*2),h=R(i,s/2,o+d,d*2);C r(s*2);$ b=exp($(0,-M_PI/s)),f=1;F(k,0,s){r[k]=l[k]+f*h[k];r[k+s]=l[k]-f*h[k];f*=b;}_ r;}C T(C&i){_ R(i,i.size()/2);}char b[O];E U(S m){FILE*y;if(!(y=fopen(m,"r")))_ E();setvbuf(y,b,0,O);fseek(y,0,2);I z=ftell(y)/4-32;fseek(y,128,0);C p;F(i,0,z){short l,r;Z(l);Z(r);if(i&1)p.B($(0.5/O*le16toh(l),0));}p.resize(O);E h(O),n(O);p=T(p);F(j,0,O)h[j]=norm(p[j])/O;F(i,1,O-1)n[i]=(h[i-1]+h[i+1]+h[i]*8)/10;fclose(y);_ n;}W G(E&d){V p;F(i,3,O/2-3)if(d[i]==*max_element(d.begin()+i-3,d.begin()+i+4))p.B({d[i],i});sort(p.begin(),p.end(),greater<P>());W r;F(i,3,K+3)r.B({D(p[i].L)/O*22050,log(p[i].J)+10});D s=0;F(i,0,K)s+=r[i].L;F(i,0,K)r[i].L/=s;_ r;}char m[O];I X(S p,W&r){E t(O),h(t);I f=0;while(1){sprintf(m,"%s%d.wav",p,f++);h=U(m);if(!h.size())break;F(j,0,O)t[j]+=h[j];}F(j,0,O)t[j]/=f;r=G(t);}D Y(W&a,W&b){D r=0;F(i,0,K){D d=b[i].L;F(j,0,K)if(abs((b[i].J-a[j].J)/b[i].J)<0.015)d=min(d,abs(b[i].L-a[j].L));r+=d;}_ r;}I H(S p,W&y,W&n){I f=0;while(1){sprintf(m,"%s%d.wav",p,f++);E h=U(m);if(!h.size())break;W p=G(h);D q=Y(p,y),r=Y(p,n);printf(abs(q-r)<=0.01?"?\n":q<r?"yes\n":"no\n");}}I main(){W y,n;X("train/yes",y);X("train/no",n);H("inputs/",y,n);}

"Ungolfed" (bien qu'il soit difficile d'appeler un code source de plus de 1,5K golfé):

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <complex>
#include <endian.h>
#include <functional>

using namespace std;

typedef complex<double> CD;

vector<CD> run_fft(vector<CD>& input, int offset, int size, int dist){
    if(size == 1){
        return vector<CD>(1, input[offset]);
    }
    vector<CD> partLow = run_fft(input, offset, size/2, dist*2),
               partHi  = run_fft(input, offset+dist, size/2, dist*2);

    vector<CD> result(size);
    CD factorBase = exp(CD(0, (inv?2:-2)*M_PI/size)), factor = 1;

    for(int k = 0; k < size/2; k++){
        result[k] = partLow[k] + factor*partHi[k];
        result[k+size/2] = partLow[k] - factor*partHi[k];
        factor *= factorBase;
    }
    return result;
}

vector<CD> fft(vector<CD>& input){
    int N = input.size();
    return run_fft(input, 0, N, 1);
}



const int MAX_BUF = 65536;
const int PWR_TWO = 16384;
const int NUM_CHECK = 75;
int sampling;

char buf[MAX_BUF];
vector<double> read_data(char* filenam){
    FILE* fp = fopen(filenam, "r");
    if(!fp)
        return vector<double>();
    setvbuf(fp, buf, _IOFBF, MAX_BUF);

    fseek(fp, 0, SEEK_END);
    int filesiz = ftell(fp);
    fseek(fp, 128, SEEK_SET);
    filesiz -= 128;

    int insamp = filesiz / 4;
    int freqsamp = 2,
        act_mod = 0;
    sampling = 44100 / freqsamp;
    int inputSize;

    vector<CD> input;

    for(int i = 0; i < insamp; i++){
        signed short int l, r;
        if(fread(&l, 2, 1, fp) != 1) break;
        if(fread(&r, 2, 1, fp) != 1) break;

        double act = 1/32768.0 * (le16toh(l));

        if((++act_mod) == freqsamp){
            inputSize++;
            input.push_back(CD(act,0));
            act_mod = 0;
        }
    }
    inputSize = input.size();

    //printf("%s\n", filenam);
    int numParts = (inputSize+PWR_TWO-1)/PWR_TWO;
    double partDelta = (double)inputSize / numParts, actDelta = 0;
    vector<CD> ndata(PWR_TWO);
    for(int i = 0; i < numParts; i++){
        vector<CD> partInput(PWR_TWO);
        int from = floor(actDelta),
            to = floor(actDelta)+PWR_TWO;

        for(int j = from; j < to; j++)
            partInput[j-from] = input[j];

        vector<CD> partData = fft(partInput);
        for(int j = 0; j < PWR_TWO; j++)
            ndata[j] += partData[j]*(1.0/numParts);
    }


    vector<double> height(PWR_TWO);
    for(int i = 0; i < PWR_TWO; i++)
        height[i] = norm(ndata[i])/PWR_TWO;

    vector<double> nheight(height);
    nheight[0] = (height[0]*0.8 + height[1]*0.1)/0.9;
    nheight[PWR_TWO-1] = (height[PWR_TWO]*0.8 + height[PWR_TWO-1]*0.1)/0.9;
    for(int i = 1; i < PWR_TWO-1; i++)
        nheight[i] = height[i-1]*0.1 + height[i]*0.8 + height[i+1]*0.1;

    fclose(fp);

    return nheight;
}


vector< pair<double,double> > get_highest_peaks(vector<double>& freqData){
    vector< pair<double,int> > peaks;

    for(int i = 3; i < PWR_TWO/2-3; i++){
        if(freqData[i] == *max_element(freqData.begin()+i-3, freqData.begin()+i+4)){
            peaks.push_back(make_pair(freqData[i], i));
        }
    }

    sort(peaks.begin(), peaks.end(), greater< pair<double,int> >());

    vector< pair<double,double> > res;
    for(int i = 3; i < NUM_CHECK+3; i++){
        res.push_back(make_pair((double)(peaks[i].second)/PWR_TWO*sampling, log(peaks[i].first)+10));
    }

    double sum_res = 0;
    for(int i = 0; i < NUM_CHECK; i++)
        sum_res += res[i].second;
    for(int i = 0; i < NUM_CHECK; i++)
        res[i].second /= sum_res;

    /*for(int i = 0; i < NUM_CHECK; i++)
        printf("%12lf %12lf\n", res[i].first, res[i].second);
    printf("\n");*/

    return res;
}


void train(char* dir, const char* type, vector< pair<double,double> >& res){
    vector<double> result(PWR_TWO), height(PWR_TWO);

    int numFile = 0;
    while(true){
        char filenam[256];
        snprintf(filenam, 255, "%s/%s%d.wav", dir, type, numFile);
        height = read_data(filenam);

        if(height.size() == 0)
            break;

        for(int j = 0; j < PWR_TWO; j++)
            result[j] += height[j];

        numFile++;
    }
    fprintf(stderr, "trained %s on %d files\n", type, numFile);

    for(int j = 0; j < PWR_TWO; j++)
        result[j] /= numFile;

    res = get_highest_peaks(result);
}


double dist_ab(vector< pair<double,double> >& A, vector< pair<double,double> >& B){
    double result = 0;
    for(int i = 0; i < NUM_CHECK; i++){
        double add = B[i].second;

        for(int j = 0; j < NUM_CHECK; j++){
            double dist = (B[i].first-A[j].first)/B[i].first;
            if(abs(dist) < 0.015)
                add = min(add, abs(B[i].second - A[j].second));
        }
        result += add;
    }
    return result;
}


void trial(char* dir, const char* pref, vector< pair<double,double> >& yes,
                                        vector< pair<double,double> >& no){
    int numFile = 0;
    int numYes = 0, numDunno = 0, numNo = 0;
    while(true){
        char filenam[256];
        snprintf(filenam, 255, "%s/%s%d.wav", dir, pref, numFile);

        vector<double> height = read_data(filenam);
        if(height.size() == 0)
            break;

        vector< pair<double,double> > peaks = get_highest_peaks(height);


        double distYes = dist_ab(peaks, yes),
               distNo = dist_ab(peaks, no);

        if(abs(distYes-distNo) <= 0.01){
            printf("dunno\n");
            numDunno++;
        } else if(distYes < distNo){
            printf("yes\n");
            numYes++;
        } else {
            printf("no\n");
            numNo++;
        }
        //printf(" (%lf %lf)\n", distYes, distNo);

        numFile++;
    }
}


int main(int argc, char** argv){
    vector< pair<double,double> > yes, no;


    train("train", "yes", yes);
    train("train", "no", no);

    trial("inputs", "", yes, no);
}

Je n'ai aucune idée de paniquer si cela fonctionnera correctement sur un ensemble de données réel (je parie que non, mais je dois essayer).

Comment ça marche:

1. Prélevez N = 2 ¹⁴ échantillons du canal gauche, chacun dans un intervalle de temps égal. Normalisez-les de sorte que la valeur min = 0 et la valeur max = 1.
2. Traitez-les à l'aide de FFT. Nous sommes maintenant passés du domaine temporel au domaine fréquentiel. Nous pourrions dire que la 0e cellule du tableau résultant est équivalente à 0 Hz et 2 ¹³ -1e cellule est équivalente à 22050 Hz (c'est parce que j'ai pris tous les autres échantillons du canal L, donc mon échantillonnage est de 22050 Hz au lieu de la fréquence de WAV, 44100 Hz).
3. Trouvez la moyenne de tous ces signaux - appelez-la "distribution de fréquence moyenne". Trouvez K pics les plus élevés dans une telle distribution (ici K = 75), en omettant les premiers (probablement du bruit) et trouvez leur force. j'ai utilisélog(mean distribution)+10 puis normalisé pour que la somme des plus grands pics soit de 1.
4. Nous avons deux "distributions de crête" - une pour Oui, une seconde pour Non. Si nous avons un WAV à tester, nous le transformons de la même manière que précédemment (étapes 1, 2, 3) et obtenons la distribution D. Ensuite, nous devons vérifier à quelle distribution (O / N) D est plus similaire. J'ai utilisé l'approche suivante: pour chaque pic en Y / N, essayez de le trouver en D. Si nous le trouvons (approximativement), le score de ce pic est la différence absolue entre Y / N et la force de D; dans le cas contraire, c'est la force de Y / N (on suppose que c'est toujours positif). Un meilleur score (plus petit) gagne. Si les résultats sont très proches (j'ai utilisé une différence absolue de 0,01), sortez dunno.

Comme je l'ai dit, probablement lors des tests finaux, il sera classé comme "encore pire que aléatoire". Bien sûr, j'espère que ce ne sera pas le cas: D

Edit: bug corrigé (oublié de fermer les fichiers).