Pengenalan suara: "Ya" atau "Tidak"?

33

Tugas

Menerapkan program dalam byte minimum sumber atau kode biner yang melakukan pengenalan suara dari sampel suara (saya mengatakan "ya", "ya" atau "tidak" dalam suara atau berbisik, polos atau unik) berdasarkan sampel pelatihan dengan akurasi maksimum .

Program harus membaca train/yes0.wav, train/no0.wav, train/yes1.wavdan sebagainya (ada 400 yeses dan 400 noes dalam dataset training), kemudian mulai membaca inputs/0.wav, inputs/1.wavsampai gagal untuk mencari file, menganalisa dan keluaran "ya" atau "tidak" (atau kata lain untuk jawaban menengah).

Jika Anda mau, Anda bisa melakukan pra- train/pelatihan program alih-alih membaca , tetapi tabel data yang dihasilkan diperhitungkan dalam skor (dan berhati-hatilah agar tidak terlalu cocok dengan sampel pelatihan - mereka tidak tumpang tindih dengan yang diperiksa). Lebih baik untuk memasukkan program yang digunakan untuk menghasilkan tabel data sebagai tambahan dalam kasus ini.

Semua file sampel adalah file WAV stereo 16-bit kecil endian, hanya dari mik laptop, tanpa penyaringan / pengurangan noise.

Batas

Fitur terlarang:

  • Menggunakan jaringan;
  • Mencoba menjangkau file jawaban inputs/key;
  • Mengubah runnerprogram yang menghitung akurasi;
  • Menggunakan perpustakaan pengenalan yang ada. Menghubungkan ke implementasi FFT tidak diizinkan: hanya fungsi matematika eksternal yang mengambil jumlah informasi konstan (seperti sinatau atan2) yang diizinkan; Jika Anda ingin FFT, tambahkan saja implementasinya ke kode sumber program Anda (bisa multibahasa jika diperlukan).

Batas sumber daya:

  • Program seharusnya tidak memakan waktu lebih dari 30 menit pada CPU i5 saya. Jika dibutuhkan lebih banyak, hanya output yang dihasilkan dalam 30 menit pertama yang dihitung dan semuanya dianggap setengah-cocok;
  • Batas memori: 1GB (termasuk file sementara);

Alat

The tools/runnerProgram secara otomatis menjalankan solusi Anda dan menghitung akurasi.

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

Itu dapat memeriksa program menggunakan data pelatihan atau menggunakan data ujian yang sebenarnya. Saya akan mencoba jawaban yang dikirim pada dataset pemeriksaan dan menerbitkan hasil (persentase akurasi) sampai saya membuat dataset publik.

Mencetak gol

Ada 5 kelas solusi tergantung pada keakuratan:

  • Semua sampel menebak dengan benar: Kelas 0;
  • Akurasi 950-999: Kelas 1;
  • Akurasi 835-950: Kelas 2;
  • Akurasi 720-834: Kelas 3;
  • Akurasi 615-719: Kelas 4;

Di dalam setiap kelas, skornya adalah jumlah byte yang diambil oleh solusi.

Jawaban yang diterima: solusi terkecil di kelas nonempty terbaik.

Tautan

Semua sampel harus dianggap CC-0 (Domain Publik), skrip dan program harus dianggap MIT.

Contoh solusi

Ini memberikan kualitas pengenalan yang sangat buruk, hanya menunjukkan cara membaca file dan memberikan jawaban

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

}
code-golf classification audio test-battery Vi.
sumber
5
tidak ada perpustakaan fft? Mengapa?
John Dvorak
1
Bagaimana dengan fungsi FFT bawaan? Apa sebenarnya yang dianggap sebagai eksternal? Juga, apa yang dianggap sebagai fungsi perpustakaan matematika? Apakah kita boleh menggunakan sum, atau kita perlu menggunakan foldl (+) 0(foldl tidak khusus matematika, dan +tidak variadic)?
John Dvorak
1
masih ... Anda secara efektif melarang sum. Saya kira itu bukan niat Anda?
John Dvorak
1
Apa definisi yang tepat dari fungsi matematika? Mereka yang khusus beroperasi pada angka? Bagaimana dengan fungsi "penjumlahan" generik yang menggunakan penjumlahan untuk angka, tetapi penggabungan untuk string? Apakah jumlah ini sekarang diperbolehkan?
John Dvorak
1
Bagaimana dengan operasi vektor J? Apakah mereka dilarang?
John Dvorak

Jawaban:

27

C ++ 11 (gcc; 1639 1625 1635 byte, Kelas 1, skor = 983, 960)

Mari kita memulainya. Itu mungkin kode terpanjang yang pernah saya persingkat ...

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

"Tidak digabung" (meskipun sulit untuk memanggil kode sumber lebih dari 1,5 ribu 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);
}

Saya tidak punya ide aneh jika itu akan bekerja dengan benar pada set data nyata (saya yakin tidak, tapi saya harus mencoba).

Bagaimana itu bekerja:

  1. Ambil N = 2 14 sampel dari saluran kiri, masing-masing dalam rentang waktu yang sama. Normalisasi mereka sehingga nilai min = 0 dan nilai maks = 1.
  2. Memprosesnya menggunakan FFT. Sekarang kami beralih dari domain waktu ke domain frekuensi. Kita mungkin mengatakan bahwa sel ke-0 array yang dihasilkan adalah setara 0Hz dan 2 sel 13 -1 adalah setara 22050Hz (itu karena saya mengambil setiap sampel lain dari saluran L, jadi pengambilan sampel saya adalah 22050Hz bukan frekuensi WAV, 44100Hz).
  3. Temukan rata-rata dari semua sinyal seperti itu - sebut saja "distribusi frekuensi rata-rata". Temukan K puncak tertinggi dalam distribusi tersebut (di sini K = 75), hilangkan beberapa pertama (mungkin kebisingan) dan temukan kekuatannya. Saya menggunakanlog(mean distribution)+10 dan kemudian dinormalisasi sehingga jumlah puncak terbesar adalah 1.
  4. Kami memiliki dua "distribusi puncak" - satu untuk Ya, kedua untuk Tidak. Jika kami memiliki WAV untuk diuji, kami mentransformasikannya dengan cara yang sama seperti sebelumnya (langkah 1, 2, 3) dan mendapatkan distribusi D. Kemudian kita harus periksa distribusi (Y / N) D yang lebih mirip dengan. Saya menggunakan pendekatan berikut: untuk setiap puncak di Y / N, cobalah untuk menemukannya di D. Jika kita menemukannya (kurang-lebih), skor untuk puncak ini adalah perbedaan mutlak antara kekuatan Y / N dan D; dalam kasus yang berlawanan, itu kekuatan Y / N (kami menganggap itu selalu positif). Skor yang lebih baik (lebih kecil) menang. Jika hasilnya sangat dekat (saya menggunakan 0,01 perbedaan mutlak), outputdunno .

Seperti yang saya katakan, mungkin pada tes akhir itu akan diklasifikasikan sebagai "lebih buruk daripada acak". Tentu saja, saya harap tidak akan: D

Sunting: memperbaiki bug (lupa menutup file).

mnbvmar
sumber
1
Anda beruntung jika berkinerja worse than random. Anda benar-benar hanya perlu mengubah satu byte - distYes > distNo, dan itu akan dilakukan better than random. Atau dengan kata lain, akan sangat mencengangkan jika Anda dapat menebak hasil koin yang salah 100 kali berturut-turut! Dan bukan hal yang aneh dari algoritma sederhana yang lebih baik daripada yang lebih kompleks, jadi +1 dan saya ucapkan semoga sukses.
blutorange
Pengujian ... Itu berakhir sebelum waktunya karena EMFILE (Too many open files)... Mencoba untuk memperbaiki ...
Vi.
Penghitung file terbuka maksimum, sekarang berfungsi. Hasil: pelatihan dataset: Accuracy: 983 ‰; Time: 0m27.570s;; Pemeriksaan dataset: Accuracy: 960 ‰; Time: 0m32.957s. Kerja bagus.
Vi.
Oke, saya perbaiki ini. 10 byte lebih banyak. :)
mnbvmar
Penggunaan luar biasa dari #defines: P
qwr