Zadanie

Zaimplementuj program w minimalnej liczbie bajtów kodu źródłowego lub binarnego, który rozpoznaje głosowo próbkę głosu (ja mówię „tak”, „tak” lub „nie” głosem lub szeptem, wyraźnie lub dziwnie) w oparciu o próbki szkoleniowe z maksymalną dokładnością .

Program powinien przeczytać train/yes0.wav, train/no0.wav,train/yes1.wav i tak dalej (są 400 razy tak i 400 sieci doskonałości w szkoleniu zbioru danych), a następnie rozpocząć czytanie inputs/0.wav, inputs/1.wavdopóki nie znajdzie plik, analizuje je i wyprowadzania „tak” lub „nie” (lub inne słowo odpowiedź pośrednia).

Jeśli chcesz, możesz wstępnie trenować program zamiast czytać train/ , ale wynikowa tabela danych liczy się do wyniku (i strzeż się zbytniego dopasowania do próbek treningowych - nie pokrywają się one z wynikami egzaminacyjnymi). W tym przypadku lepiej jest dołączyć program użyty do utworzenia tabeli danych jako dodatek.

Wszystkie przykładowe pliki to małe endianowe 16-bitowe pliki WAV stereo, tylko z mikrofonu laptopa, bez filtrowania / redukcji szumów.

Granice

Zabronione funkcje:

• Korzystanie z sieci;
• Próbuję dotrzeć do pliku odpowiedzi inputs/key ;
• Subverting the runner programu obliczającego dokładność;
• Korzystanie z istniejących bibliotek rozpoznawania. Łączenie z implementacją FFT jest niedozwolone: ​​dozwolone są tylko zewnętrzne funkcje matematyczne przyjmujące stałą ilość informacji (takich jak sinlub atan2); Jeśli chcesz FFT, po prostu dodaj jego implementację do kodu źródłowego programu (w razie potrzeby może być wielojęzyczny).

Limity zasobów:

• Program nie powinien zająć więcej niż 30 minut czasu procesora na moim laptopie i5. Jeśli zajmie to więcej, liczone są tylko wyniki wytworzone w ciągu pierwszych 30 minut i wszystko inne przyjmuje się za pół-mecz;
• Limit pamięci: 1 GB (w tym pliki tymczasowe);

Przybory

tools/runnerProgram automatycznie uruchamia swoje rozwiązanie i oblicza dokładność.

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

Może badać program na podstawie danych treningowych lub rzeczywistych danych egzaminacyjnych. Spróbuję przesłać odpowiedzi na zestaw danych badania i opublikować wyniki (procent dokładności), dopóki nie opublikuję tego zestawu danych.

Punktacja

Istnieje 5 klas rozwiązań w zależności od dokładności:

• Wszystkie próbki zgadły poprawnie: Klasa 0;
• Dokładność 950–999: klasa 1;
• Dokładność 835–950: klasa 2;
• Dokładność 720-834: klasa 3;
• Dokładność 615–719: klasa 4;

W każdej klasie wynikiem jest liczba bajtów potrzebnych na rozwiązanie.

Zaakceptowana odpowiedź: najmniejsze rozwiązanie w najlepszej niepustej klasie.

Spinki do mankietów

• Projekt Github z narzędziami: https://github.com/vi/codegolf-jein
• Zestaw danych szkoleniowych: http://vi-server.org/pub/codegolf-jein-train.tar.xz
• Zestaw danych do badań jest do tej pory prywatny, w repozytorium Github dostępne są sumy kontrolne (HMAC).

Wszystkie próbki należy uznać za CC-0 (domena publiczna), skrypty i programy należy uznać za MIT.

Przykładowe rozwiązanie

Zapewnia bardzo słabą jakość rozpoznawania, pokazuje tylko, jak czytać pliki i generować odpowiedzi

#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 bajtów, klasa 1, wynik = 983, 960)

Zacznijmy to. To prawdopodobnie najdłuższy kod, jaki kiedykolwiek skróciłem ...

#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” (choć trudno nazwać golfem kod źródłowy ponad 1,5 KB):

#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);
}

Nie mam cholernego pomysłu, czy będzie działać poprawnie na prawdziwym zbiorze danych (założę się, że nie, ale muszę spróbować).

Jak to działa:

1. Weź N = 2 ¹⁴ próbek z lewego kanału, każda w równym przedziale czasowym. Znormalizuj je, aby wartość minimalna = 0 i wartość maksymalna = 1.
2. Przetwarzaj je za pomocą FFT. Teraz zmieniliśmy domenę czasu na domenę częstotliwości. Można powiedzieć, że 0 komórka wynikowej macierzy jest odpowiednikiem 0 Hz, a 2 ¹³ -1 komórka odpowiada 22050 Hz (to jest dlatego, że pobrałem co drugą próbkę z kanału L, więc moje próbkowanie wynosi 22050 Hz zamiast częstotliwości WAV, 44100 Hz).
3. Znajdź średnią wszystkich takich sygnałów - nazwij ją „średnim rozkładem częstotliwości”. Znajdź K najwyższych pików w takim rozkładzie (tutaj K = 75), pomijając kilka pierwszych (prawdopodobnie szum) i znajdź ich siłę. użyłemlog(mean distribution)+10 a następnie znormalizowałem, aby suma największych pików wynosiła 1.
4. Mamy dwa „rozkłady pików” - jeden dla Tak, drugi dla Nie. Jeśli mamy do przetestowania WAV, przekształcamy go w taki sam sposób jak poprzednio (kroki 1, 2, 3) i uzyskujemy rozkład D. Następnie musimy sprawdź, który rozkład (T / N) D jest bardziej podobny do. Zastosowałem następujące podejście: dla każdego piku w Y / N spróbuj go znaleźć w D. Jeśli go znajdziemy (w przybliżeniu), wynik dla tego piku jest absolutną różnicą między Y / N a siłą D; w przeciwnym przypadku jest to siła Y / N (zakładamy, że zawsze jest dodatnia). Wygrywa lepszy (mniejszy) wynik. Jeśli wyniki są bardzo bliskie (użyłem różnicy bezwzględnej 0,01), wynik dunno.

Jak powiedziałem, prawdopodobnie w końcowych testach zostanie sklasyfikowany jako „jeszcze gorszy niż losowy”. Oczywiście mam nadzieję, że nie: D

Edycja: naprawiony błąd (zapomniałem zamknąć pliki).