////////////////////////////////////////////////////////////////////////////////////// // // // This code implements LogicNet, a novel LUT-based machine learning algorithm // // Developed during 2018-2019 by Alan Mishchenko, UC Berkeley // // in collaboration with Satrajit Chatterjee, Google AI // // // ////////////////////////////////////////////////////////////////////////////////////// // This code expects the following MNIST files to be in the working directory: // // train-labels.idx1-ubyte // t10k-labels.idx1-ubyte // train-images.idx3-ubyte // t10k-images.idx3-ubyte #include #include #include #include #include #define ABC_SWAP(Type, a, b) { Type t = a; a = b; b = t; } // random number generator (http://www.codeproject.com/KB/recipes/SimpleRNG.aspx) #define NUMBER1 3716960521u #define NUMBER2 2174103536u unsigned Gia_ManRandom( int fReset ) { static unsigned int m_z = NUMBER1; static unsigned int m_w = NUMBER2; if ( fReset ) { m_z = NUMBER1; m_w = NUMBER2; } m_z = 36969 * (m_z & 65535) + (m_z >> 16); m_w = 18000 * (m_w & 65535) + (m_w >> 16); return (m_z << 16) + m_w; } void ** Extra_ArrayAlloc( int nCols, int nRows, int Size ) { void ** pRes; char * pBuffer; int i; assert( nCols > 0 && nRows > 0 && Size > 0 ); pBuffer = malloc( nCols * (sizeof(void *) + nRows * Size) ); pRes = (void **)pBuffer; pRes[0] = pBuffer + nCols * sizeof(void *); for ( i = 1; i < nCols; i++ ) pRes[i] = (void *)((char *)pRes[0] + i * nRows * Size); return pRes; } void Mnist_PrintImageOne( unsigned char * p ) { int i, k; for ( i = 0; i < 28; i++ ) { for ( k = 0; k < 28; k++ ) printf( "%d", p[i*28+k] >= 128 ); printf( "\n" ); } printf( "\n" ); } void Mnist_PrintImages( unsigned char * pL, unsigned char * pI, int nItems ) { int n; for ( n = 0; n < nItems; n++ ) { printf( "%d\n", pL[8+n] >= 5 ); Mnist_PrintImageOne( pI + 16 + n * 28 * 28 ); printf( "\n" ); } } unsigned char * Mnist_ReadLabels1() { int Size = 60000 + 8; unsigned char * pData = malloc( Size ); FILE * pFile = fopen( "train-labels.idx1-ubyte", "rb" ); int RetValue = fread( pData, 1, Size, pFile ); assert( RetValue == Size ); fclose( pFile ); return pData; } unsigned char * Mnist_ReadLabels2() { int Size = 10000 + 8; unsigned char * pData = malloc( Size ); FILE * pFile = fopen( "t10k-labels.idx1-ubyte", "rb" ); int RetValue = fread( pData, 1, Size, pFile ); assert( RetValue == Size ); fclose( pFile ); return pData; } unsigned char * Mnist_ReadLabels() { unsigned char * pL1 = Mnist_ReadLabels1(); unsigned char * pL2 = Mnist_ReadLabels2(); unsigned char * pL = malloc( 60000 + 10000 ); memmove( pL, pL1 + 8, 60000 ); memmove( pL+60000, pL2 + 8, 10000 ); free( pL1 ); free( pL2 ); return pL; } unsigned char * Mnist_ReadImages1() { int Size = 60000 * 28 * 28 + 16; unsigned char * pData = malloc( Size ); FILE * pFile = fopen( "train-images.idx3-ubyte", "rb" ); int RetValue = fread( pData, 1, Size, pFile ); assert( RetValue == Size ); fclose( pFile ); return pData; } unsigned char * Mnist_ReadImages2() { int Size = 10000 * 28 * 28 + 16; unsigned char * pData = malloc( Size ); FILE * pFile = fopen( "t10k-images.idx3-ubyte", "rb" ); int RetValue = fread( pData, 1, Size, pFile ); assert( RetValue == Size ); fclose( pFile ); return pData; } unsigned char ** Mnist_ReadImages() { int fUseMaxPooling = 1; unsigned char * pL1 = Mnist_ReadImages1(); unsigned char * pL2 = Mnist_ReadImages2(); unsigned char ** pImgs = (unsigned char **)Extra_ArrayAlloc( 28*28, 60000+10000, 1 ); int i, x, y; for ( i = 0; i < 60000+10000; i++ ) { for ( x = 0; x < 784; x++ ) if ( i < 60000 ) pImgs[x][i] = pL1[16 + i * 784 + x] >= 128; else pImgs[x][i] = pL2[16 + (i-60000) * 784 + x] >= 128; } // perform max-pooling if ( fUseMaxPooling ) { for ( i = 0; i < 60000+10000; i++ ) { for ( x = 0; x < 14; x++ ) for ( y = 0; y < 14; y++ ) { int Value00 = pImgs[(2*x+0) * 28 + (2*y+0)][i]; int Value01 = pImgs[(2*x+0) * 28 + (2*y+1)][i]; int Value10 = pImgs[(2*x+1) * 28 + (2*y+0)][i]; int Value11 = pImgs[(2*x+1) * 28 + (2*y+1)][i]; int Max0 = Value00 > Value01 ? Value00 : Value01; int Max1 = Value10 > Value11 ? Value10 : Value11; int Max = Max0 > Max1 ? Max0 : Max1; pImgs[(2*x+0) * 28 + (2*y+0)][i] = Max; pImgs[(2*x+0) * 28 + (2*y+1)][i] = Max; pImgs[(2*x+1) * 28 + (2*y+0)][i] = Max; pImgs[(2*x+1) * 28 + (2*y+1)][i] = Max; } } } free( pL1 ); free( pL2 ); return pImgs; } typedef struct Img_Man_t_ Img_Man_t; struct Img_Man_t_ { int nLevs; int nLuts; int LutSize; int nImgs[2]; unsigned char * pLbls; unsigned char ** pImgs; unsigned char ** pLuts[256]; unsigned short ** pFans[256]; unsigned char ** pOuts[2]; unsigned short * pMints; int * pCounts[2]; // temp counters }; void Img_ManFree( Img_Man_t * p ) { int i; free( p->pLbls ); free( p->pImgs ); free( p->pMints ); for ( i = 1; i < p->nLevs; i++ ) free( p->pLuts[i] ); for ( i = 1; i < p->nLevs; i++ ) free( p->pFans[i] ); for ( i = 0; i < 2; i++ ) free( p->pOuts[i] ); for ( i = 0; i < 2; i++ ) free( p->pCounts[i] ); free( p ); } Img_Man_t * Img_ManAlloc( int LutSize, int nLuts, int nLevs ) { int n, i, k; Img_Man_t * p = calloc( sizeof(Img_Man_t), 1 ); p->pLbls = Mnist_ReadLabels(); p->pImgs = Mnist_ReadImages(); //Mnist_PrintImages( pLabels[0], pImages[0], 10 ); // p->LutSize = 6; // p->nLuts = 1 << 8; // p->nLevs = 16; p->LutSize = LutSize; p->nLuts = nLuts; p->nLevs = nLevs; p->nImgs[0] = 60000; p->nImgs[1] = 10000; assert( p->nLevs <= 256 ); assert( p->nLuts <= (1 << 16) ); assert( p->LutSize <= 16 ); Gia_ManRandom(1); //printf( "Running with %d levels, %d luts of size %d.\n", p->nLevs, p->nLuts, p->LutSize ); //printf( "Finished reading...\n" ); for ( n = 1; n < p->nLevs; n++ ) { p->pLuts[n] = (unsigned char **)Extra_ArrayAlloc( p->nLuts, 1 << p->LutSize, 1 ); //for ( i = 0; i < p->nLuts; i++ ) // for ( k = 0; k < (1 << p->LutSize); k++ ) // p->pLuts[n][i][k] = Gia_ManRandom(0) & 1; p->pFans[n] = (unsigned short **)Extra_ArrayAlloc( p->nLuts, p->LutSize, 2 ); for ( i = 0; i < p->nLuts; i++ ) for ( k = 0; k < p->LutSize; k++ ) p->pFans[n][i][k] = Gia_ManRandom(0) % (n == 1 ? 784 : p->nLuts); } // temp storage for ( i = 0; i < 2; i++ ) p->pOuts[i] = (unsigned char **)Extra_ArrayAlloc( p->nLuts, p->nImgs[0]+p->nImgs[1], 1 ); for ( i = 0; i < 2; i++ ) p->pCounts[i] = malloc( sizeof(int) * (1 << p->LutSize) ); p->pMints = (unsigned short *)malloc( sizeof(unsigned short) * (p->nImgs[0]+p->nImgs[1]) ); //printf( "Finished allocating...\n" ); return p; } int Img_ManEvalFanins( Img_Man_t * p, int n, int * pFanins, int Digit, int Digit2 ) { int i, f, Diff = 0; unsigned char ** ppArray = n == 1 ? p->pImgs : p->pOuts[0]; unsigned char * pArray[32]; for ( f = 0; f < p->LutSize; f++ ) pArray[f] = ppArray[pFanins[f]]; for ( i = 0; i < 2; i++ ) memset( p->pCounts[i], 0, sizeof(int) * (1 << p->LutSize) ); for ( i = 0; i < p->nImgs[0]; i++ ) { int iMint = 0; for ( f = 0; f < p->LutSize; f++ ) if ( pArray[f][i] ) iMint |= (1 << f); if ( Digit2 == -1 ) { // p->pCounts[p->pLbls[i] >= 5][iMint]++; if ( p->pLbls[i] == Digit ) p->pCounts[1][iMint] += 9; else p->pCounts[0][iMint] += 1; } else { if ( p->pLbls[i] == Digit ) p->pCounts[1][iMint]++; else if ( p->pLbls[i] == Digit2 ) p->pCounts[0][iMint]++; } } //printf( "Fanins = %d %d\n", pFanins[0], pFanins[1] ); for ( i = 0; i < (1 << p->LutSize); i++ ) { //printf( "0=%5d 1=%5d\n", p->pCounts[0][i], p->pCounts[1][i] ); if ( p->pCounts[0][i] > p->pCounts[1][i] ) Diff += p->pCounts[0][i] - p->pCounts[1][i]; else Diff += p->pCounts[1][i] - p->pCounts[0][i]; } //printf( "Diff = %d.\n\n", Diff ); return Diff; } void Img_ManFindFanins( Img_Man_t * p, int n, unsigned short * pFaninsBest, int Digit, int Digit2, int nTries ) { int i, f, Diff, DiffBest = -1, pFanins[32]; for ( i = 0; i < nTries; i++ ) { for ( f = 0; f < p->LutSize; f++ ) pFanins[f] = Gia_ManRandom(0) % (n == 1 ? 784 : p->nLuts); Diff = Img_ManEvalFanins( p, n, pFanins, Digit, Digit2 ); if ( DiffBest == -1 || DiffBest < Diff ) { DiffBest = Diff; for ( f = 0; f < p->LutSize; f++ ) pFaninsBest[f] = (unsigned short)pFanins[f]; } } } float Img_ManTrain( Img_Man_t * p, int Digit, int Digit2 ) { int n, u, i, f, b, Count, Count2[2], CountAll = 0; int CountXors[256] = {0}; //assert( Digit < Digit2 ); //printf( "Handling digit %d.\n", Digit ); for ( n = 1; n < p->nLevs; n++ ) { //long clk = clock(); for ( u = 0; u < p->nLuts; u++ ) { unsigned char ** ppArray = n == 1 ? p->pImgs : p->pOuts[0]; unsigned char * pArray[32]; // create best fanins //if ( n == 1 ) // Img_ManFindFanins( p, n, p->pFans[n][u], Digit, Digit2, 8 ); for ( f = 0; f < p->LutSize; f++ ) pArray[f] = ppArray[p->pFans[n][u][f]]; for ( i = 0; i < 2; i++ ) memset( p->pCounts[i], 0, sizeof(int) * (1 << p->LutSize) ); Count2[0] = Count2[1] = 0; for ( i = 0; i < p->nImgs[0]; i++ ) { p->pMints[i] = 0; for ( f = 0; f < p->LutSize; f++ ) if ( pArray[f][i] ) p->pMints[i] |= (1 << f); // p->pCounts[p->pLbls[i] >= 5][p->pMints[i]]++; if ( Digit2 == -1 ) { /* if ( p->pLbls[i] == Digit ) p->pCounts[1][p->pMints[i]] += 9; else p->pCounts[0][p->pMints[i]] += 1; */ if ( p->pLbls[i] == Digit ) // p->pCounts[1][p->pMints[i]]++, Count2[1]+=9; p->pCounts[1][p->pMints[i]]+=9; else // p->pCounts[0][p->pMints[i]]++, Count2[0]++; p->pCounts[0][p->pMints[i]]++; } else { if ( p->pLbls[i] == Digit2 ) p->pCounts[1][p->pMints[i]]++, Count2[1]++; else if ( p->pLbls[i] == Digit ) p->pCounts[0][p->pMints[i]]++, Count2[0]++; } } for ( b = 0; b < (1 << p->LutSize); b++ ) if ( p->pCounts[0][b] < p->pCounts[1][b] ) // if ( (float)p->pCounts[0][b]/Count2[0] < (float)p->pCounts[1][b]/Count2[1] ) p->pLuts[n][u][b] = 1; else if ( p->pCounts[0][b] > p->pCounts[1][b] ) // else if ( (float)p->pCounts[0][b]/Count2[0] > (float)p->pCounts[1][b]/Count2[1] ) p->pLuts[n][u][b] = 0; else p->pLuts[n][u][b] = Gia_ManRandom(0) & 1; // set the output for ( i = 0; i < p->nImgs[0]; i++ ) p->pOuts[1][u][i] = p->pLuts[n][u][p->pMints[i]]; if ( p->LutSize != 2 ) continue; if ( (p->pLuts[n][u][0] == 0 && p->pLuts[n][u][1] == 1 && p->pLuts[n][u][2] == 1 && p->pLuts[n][u][3] == 0) || (p->pLuts[n][u][0] == 1 && p->pLuts[n][u][1] == 0 && p->pLuts[n][u][2] == 0 && p->pLuts[n][u][3] == 1) ) CountXors[n]++; } ABC_SWAP( unsigned char **, p->pOuts[0], p->pOuts[1] ); //printf( "Finished training level %2d... ", n ); Count = CountAll = 0; for ( i = 0; i < p->nImgs[0]; i++ ) { if ( Digit2 == -1 ) { // if ( p->pOuts[0][0][i] == (p->pLbls[i] >= 5) ) if ( p->pOuts[0][0][i] == (p->pLbls[i] == Digit) ) Count++; } else if ( p->pLbls[i] == Digit || p->pLbls[i] == Digit2 ) { CountAll++; if ( p->pOuts[0][0][i] == (p->pLbls[i] == Digit2) ) Count++; } } //printf( "Result = %5.3f ", 100.0*Count/p->nImgs[0], CountXors[n] ); //printf( "Time = %8.2f sec\n", 1.0*(clock() - clk)/CLOCKS_PER_SEC ); } if ( Digit2 == -1 ) return (float)100.0*(p->nImgs[0]-Count)/p->nImgs[0]; else return (float)100.0*(CountAll-Count)/CountAll; } float Img_ManEval( Img_Man_t * p, int Digit, int Digit2, unsigned char Res[10000], float * pLevels ) { int n, u, i, f, Count = 0, CountAll = 0; assert( 10000 == p->nImgs[1] ); for ( n = 1; n < p->nLevs; n++ ) { for ( u = 0; u < p->nLuts; u++ ) { unsigned char ** ppArray = n == 1 ? p->pImgs : p->pOuts[0]; unsigned char * pArray[32]; for ( f = 0; f < p->LutSize; f++ ) pArray[f] = ppArray[p->pFans[n][u][f]]; for ( i = 0; i < p->nImgs[1]; i++ ) { int Mint = 0; for ( f = 0; f < p->LutSize; f++ ) if ( pArray[f][p->nImgs[0]+i] ) Mint |= (1 << f); p->pOuts[1][u][p->nImgs[0]+i] = p->pLuts[n][u][Mint]; } } ABC_SWAP( unsigned char **, p->pOuts[0], p->pOuts[1] ); //printf( "Finished evaluating level %2d... ", n ); Count = CountAll = 0; for ( i = 0; i < p->nImgs[1]; i++ ) { if ( Digit2 == -1 ) { // if ( p->pOuts[0][0][p->nImgs[0]+i] == (p->pLbls[p->nImgs[0]+i] >= 5) ) if ( p->pOuts[0][0][p->nImgs[0]+i] == (p->pLbls[p->nImgs[0]+i] == Digit) ) Count++; // remember status Res[i] = p->pOuts[0][0][p->nImgs[0]+i] == (p->pLbls[p->nImgs[0]+i] == Digit); } else { if ( p->pLbls[p->nImgs[0]+i] == Digit || p->pLbls[p->nImgs[0]+i] == Digit2 ) { CountAll++; if ( p->pOuts[0][0][p->nImgs[0]+i] == (p->pLbls[p->nImgs[0]+i] == Digit2) ) Count++; } // remember status Res[i] = p->pOuts[0][0][p->nImgs[0]+i]; } } //printf( "Result = %5.3f\n", 100.0*Count/p->nImgs[1] ); if ( Digit2 == -1 ) pLevels[n] = (float)100.0*(p->nImgs[1]-Count)/p->nImgs[1]; else pLevels[n] = (float)100.0*(CountAll-Count)/CountAll; } if ( Digit2 == -1 ) return (float)100.0*(p->nImgs[1]-Count)/p->nImgs[1]; else return (float)100.0*(CountAll-Count)/CountAll; } // use this main() for two-way classification on MNIST // (distinguishing each digit against all other digits) int main( int argc, char * argv[] ) { Img_Man_t * p; long clk = clock(); int d, nImages = 10000; int LutSize = 6, nLuts = 256, nLevels = 8; unsigned char Status[10][10000]; float AveT = 0, AveE = 0, Levels[100] = {0}; unsigned char * pLabels = Mnist_ReadLabels2(); if ( argc != 1 && argc != 4 ) { free( pLabels ); printf( "usage: %s \n", argv[0] ); return 1; } else if ( argc == 4 ) { LutSize = atoi(argv[1]); nLuts = atoi(argv[2]); nLevels = atoi(argv[3]); } printf( "Using parameters: LUT size = %2d LUT count = %3d LUT level = %2d\n", LutSize, nLuts, nLevels ); for ( d = 0; d < 10; d++ ) { long clkT = clock(), clkE; float ResT, ResE; p = Img_ManAlloc( LutSize, nLuts, nLevels ); ResT = Img_ManTrain( p, d, -1 ); clkT = clock() - clkT; clkE = clock(); ResE = Img_ManEval( p, d, -1, Status[d], Levels ); clkE = clock() - clkE; Img_ManFree( p ); AveT += ResT; AveE += ResE; printf( "Finished digit %d: Train = %6.2f %% Eval = %6.2f %% ", d, ResT, ResE ); printf( "Train =%8.2f sec Eval =%8.2f sec\n", 1.0*clkT/CLOCKS_PER_SEC, 1.0*clkE/CLOCKS_PER_SEC ); } AveT /= 10; AveE /= 10; /* for ( i = 0; i < nImages; i++ ) { if ( Status[pLabels[8+i]][i] ) Count++; if ( i > 20 ) continue; printf( "Image %3d : Digit %c ", i, '0'+pLabels[8+i] ); for ( d = 0; d < 10; d++ ) printf( "%d=%d ", d, Status[d][i] ); printf( "\n" ); } printf( "Average result: Correct = %6.2f %% Error = %6.2f %% ", 100.0*Count/nImages, 100.0*(nImages-Count)/nImages ); */ printf( "Average result: Train = %6.2f %% Eval = %6.2f %% ", AveT, AveE ); printf( "Time = %8.2f sec\n", 1.0*(clock() - clk)/CLOCKS_PER_SEC ); free( pLabels ); return 0; } int Img_PerformVoting( unsigned char Status[10][10][10000], int i, int Votes[10] ) { int d, d2, dBest, VotesBest; for ( d = 0; d < 10; d++ ) for ( d2 = 0; d2 < 10; d2++ ) if ( d < d2 ) { if ( Status[d][d2][i] ) Votes[d2]++; else Votes[d]++; } else if ( d > d2 ) { if ( Status[d2][d][i] ) Votes[d]++; else Votes[d2]++; } // choose the best one dBest = 0; VotesBest = Votes[0]; for ( d = 1; d < 10; d++ ) if ( VotesBest < Votes[d] ) { VotesBest = Votes[d]; dBest = d; } return dBest; } float Img_UsePriority( unsigned char Status[10][10][10000], unsigned char * pLabels, unsigned char * pImages, int FailCount[10][10] ) { int nTotal = 10000; int i, d, d2, Count = 0, Stop = 0; for ( i = 0; i < nTotal; i++ ) { int Votes[10] = {0}; int Res = Img_PerformVoting(Status, i, Votes); Count += Res == (int)pLabels[i]; if ( Res != (int)pLabels[i] ) FailCount[(int)pLabels[i]][Res]++; if ( Res == (int)pLabels[i] || Stop > -1 ) continue; printf( "Image %4d. Label %d. Result = %d.\n", i, (int)pLabels[i], Res ); for ( d = 0; d < 10; d++, printf("\n") ) for ( d2 = 0, printf("%d=", d); d2 < 10; d2++ ) { if ( d == d2 ) printf( " " ); else if ( d < d2 ) printf( "%d", Status[d][d2][i] ); else if ( d > d2 ) printf( "%d", Status[d2][d][i] ); } printf( "Votes: " ); for ( d = 0; d < 10; d++ ) printf( "%d=%d ", d, Votes[d] ); printf( "\n" ); Mnist_PrintImageOne( pImages + i * 28 * 28 ); printf("\n"); Stop++; } return (float)100.0*(nTotal-Count)/nTotal; } // use this main() for multi-way classification on MNIST int main_( int argc, char * argv[] ) { Img_Man_t * p; long clk = clock(); int d, d2, Count = 0, nImages = 10000; int LutSize = 6, nLuts = 256, nLevels = 8; unsigned char Status[10][10][10000]; float AveT = 0, AveE = 0, Res, Levels[100] = {0}; unsigned char * pLabels = Mnist_ReadLabels2(); unsigned char * pImages = Mnist_ReadImages2(); int FailCount[10][10] = {{0}}; if ( argc != 1 && argc != 4 ) { free( pLabels ); printf( "usage: %s \n", argv[0] ); return 1; } else if ( argc == 4 ) { LutSize = atoi(argv[1]); nLuts = atoi(argv[2]); nLevels = atoi(argv[3]); } printf( "Using parameters: LUT size = %2d LUT count = %3d LUT level = %2d\n", LutSize, nLuts, nLevels ); for ( d = 0; d < 10; d++ ) for ( d2 = d+1; d2 < 10; d2++ ) { long clkT = clock(), clkE; float ResT, ResE; p = Img_ManAlloc( LutSize, nLuts, nLevels ); ResT = Img_ManTrain( p, d, d2 ); clkT = clock() - clkT; clkE = clock(); ResE = Img_ManEval( p, d, d2, Status[d][d2], Levels ); clkE = clock() - clkE; Img_ManFree( p ); AveT += ResT; AveE += ResE; // for ( n = 1; n < nLevels; n++ ) // printf( "Level %2d : Eval = %6.2f %%\n", n, Levels[n] ); printf( "Finished digits %d and %d: Train = %6.2f %% Eval = %6.2f %% ", d, d2, ResT, ResE ); printf( "Train =%8.2f sec Eval =%8.2f sec\n", 1.0*clkT/CLOCKS_PER_SEC, 1.0*clkE/CLOCKS_PER_SEC ); } AveT /= 45; AveE /= 45; Res = Img_UsePriority(Status, pLabels + 8, pImages + 16, FailCount); printf( "Average result: Train = %6.2f %% Eval = %6.2f %%\n", AveT, AveE ); printf( "Honest result: Eval = %6.2f %% ", Res ); printf( "Time = %8.2f sec\n", 1.0*(clock() - clk)/CLOCKS_PER_SEC ); printf( "Fail statistics (label / result):\n " ); for ( d = 0; d < 10; d++ ) printf( "%5d=", d ); printf( "\n" ); for ( d = 0; d < 10; d++, printf( "\n" ) ) for ( d2 = 0, printf( "%d=", d); d2 < 10; d2++ ) printf( "%6d", FailCount[d][d2] ); printf( "\n" ); free( pLabels ); free( pImages ); return 0; }