4 ms·

I tried replacing the distance function in the code with some simpler distance measures: Gzip distance: ~3 minutes, 78% accuracy Euclidean distance: ~0

I tried replacing the distance function in the code with some simpler distance measures: Gzip distance: ~3 minutes, 78% accuracy Euclidean distance: ~0.5 seconds, 93% accuracy Jaccard distance * : ~0.7 seconds, 94% accuracy Dice dissimilarity * : ~0.8 seconds, 94% accuracy * after binarising the images So, as a distance measure for classifying MNIST digits, GZIP has lower accuracy, and is much more computationally demanding than other measures. I'm not that familiar with how the GZIP algorithm works, it's kind of interesting that it's so much lower. I wonder whether image focused compression algorithms might do better? (Edit: Btw, I enjoyed the post; it's a creative idea, the writing and code was great, and it's sparked some good discussion. But after having a closer look, I think the baselines above provide some context to the gzip scores.)

tysam_and 3y ago
Holy cow, I knew that MNIST was simple, but not that simple. Could you post a snippet of the code that you used to achieve this? It would be really, really nice to have a baseline to work from I'm sure, and I feel like this could be really useful to a few other areas (my personal obsession is speed-training on CIFAR10 :')))) ) Holy cow, that's insane. :O
- montebicyclelo 3y ago
  I used the notebook linked in the original post [1]. It evaluates using 100 samples from the test set, (I'm guessing because the gzip method is slow - it would take ~7 hours on the full test set, on my machine). I plugged in the distance measures, for the `compute_ncd` function. (Jaccard/Dice have been negated and the -1 removed.) def euclidean(x1, x2): return np.sum(np.square(x1 - x2)) def jaccard(x1, x2): x1_binary = x1 > 0.5 x2_binary = x2 > 0.5 return np.logical_or(x1_binary, x2_binary).sum() / np.logical_and(x1_binary, x2_binary).sum() def dice(x1, x2): x1_binary = x1 > 0.5 x2_binary = x2 > 0.5 return 2 * np.logical_or(x1_binary, x2_binary).sum() / (x1_binary.sum() + x2_binary.sum()) [1] https://github.com/Jakob-98/mono/blob/73168bc0ea904e7586581573da5907020d88736f/python/gzip_mnist/mnist_gzip.ipynb https://github.com/Jakob-98/mono/blob/73168bc0ea904e75865815...
  - tysam_and 3y ago
    Ohhh, you know what? I think this makes sense, since it's basically like making prototypes from the training set, only it's instead comparing against every training example, then averaging. Cool. Did not know that would be remotely close to 90%, but that makes sense to me. I wonder if something like a weighted max_mean would perform better or something L1. Or maybe L2 is ideal, it is at the center of a lot of things information theory, after all! ;PPPP
- KateLawson 3y ago
  MNIST is what the Post Office solved in the late 1990s. It's basically the "hello world" of visual recognition these days. https://www.govexec.com/federal-news/1999/02/postal-service-tests-handwriting-recognition-system/1746/ https://www.govexec.com/federal-news/1999/02/postal-service-...
jdthedisciple 3y ago
That's pretty amazing. So the whole gzip thing - while fancy - really is extra steps for less bang.
w-m 3y ago
Best one I found is Normalized Mutual Information at 95%. It's a little more complex, but you could still compute it relatively quickly on binarized images. NMI skimage: ~30 seconds, 95% accuracy NMI numba *: ~0.6 seconds, 95% accuracy Here's the code, courtesy of ChatGPT: @njit(cache=True) def compute_joint(img1, img2): stacked = 2 * img1.ravel() + img2.ravel() return np.bincount(stacked, minlength=4).reshape(2, 2) @njit(cache=True) def entropy(counts, total): # Convert counts to probabilities p = counts / total # Only calculate for non-zero entries to avoid log(0) return -np.sum(p[p > 0] * np.log2(p[p > 0])) @njit(cache=True) def normalized_mutual_information(img1, img2): joint_counts = compute_joint(img1, img2) total_pixels = 28*28 # Marginal counts c1 = np.sum(joint_counts, axis=1) c2 = np.sum(joint_counts, axis=0) # Compute entropies directly from counts h1 = entropy(c1, total_pixels) h2 = entropy(c2, total_pixels) joint_entropy = entropy(joint_counts.flatten(), total_pixels) mutual_info = h1 + h2 - joint_entropy return 2 * mutual_info / (h1 + h2)
sr192 3y ago
ben recht's kernel method implementation in 10 lines hits 98% https://github.com/benjamin-recht/mnist_1_pt_2/tree/main https://github.com/benjamin-recht/mnist_1_pt_2/tree/main
- tysam_and 3y ago
  Great link, thank you so much, lol. This line freaking killed me: https://github.com/benjamin-recht/mnist_1_pt_2/blob/c0fe96bc31ba29d4923956d1421354d584c358da/mnist_1_pt_2.py#L18 https://github.com/benjamin-recht/mnist_1_pt_2/blob/c0fe96bc...
cqz 3y ago
Very cool. I tried using PNG compression, it does actually do better, slightly: PNG : ~15.1 seconds, 83% accuracy I also tried dropping in zstandard compression: Zstd (level=3) : ~3.5 seconds, 88% accuracy Much faster than gzip, at least. And iff I use (x1-x2)*2 instead of x1+x2 to calculate Cx1x2 that pushes zstd up to 93% accuracy. I'm somewhat interested in the fact that if I stack the two arrays on top of each other instead of adding them together, I get absolutely garbage performance (<20%), however as far as I can tell that actually works well when classifying strings.
- w-m 3y ago
  Re garbage performance on stacking: I had tried interleaving the values (creating a 56x28 img), it dropped one percentage point of accuracy when using gzip.

tysam_and 3y ago

Holy cow, I knew that MNIST was simple, but not that simple. Could you post a snippet of the code that you used to achieve this? It would be really, really nice to have a baseline to work from I'm sure, and I feel like this could be really useful to a few other areas (my personal obsession is speed-training on CIFAR10 :')))) ) Holy cow, that's insane. :O

montebicyclelo 3y ago
I used the notebook linked in the original post [1]. It evaluates using 100 samples from the test set, (I'm guessing because the gzip method is slow - it would take ~7 hours on the full test set, on my machine). I plugged in the distance measures, for the `compute_ncd` function. (Jaccard/Dice have been negated and the -1 removed.) def euclidean(x1, x2): return np.sum(np.square(x1 - x2)) def jaccard(x1, x2): x1_binary = x1 > 0.5 x2_binary = x2 > 0.5 return np.logical_or(x1_binary, x2_binary).sum() / np.logical_and(x1_binary, x2_binary).sum() def dice(x1, x2): x1_binary = x1 > 0.5 x2_binary = x2 > 0.5 return 2 * np.logical_or(x1_binary, x2_binary).sum() / (x1_binary.sum() + x2_binary.sum()) [1] https://github.com/Jakob-98/mono/blob/73168bc0ea904e7586581573da5907020d88736f/python/gzip_mnist/mnist_gzip.ipynb https://github.com/Jakob-98/mono/blob/73168bc0ea904e75865815...
- tysam_and 3y ago
  Ohhh, you know what? I think this makes sense, since it's basically like making prototypes from the training set, only it's instead comparing against every training example, then averaging. Cool. Did not know that would be remotely close to 90%, but that makes sense to me. I wonder if something like a weighted max_mean would perform better or something L1. Or maybe L2 is ideal, it is at the center of a lot of things information theory, after all! ;PPPP
KateLawson 3y ago
MNIST is what the Post Office solved in the late 1990s. It's basically the "hello world" of visual recognition these days. https://www.govexec.com/federal-news/1999/02/postal-service-tests-handwriting-recognition-system/1746/ https://www.govexec.com/federal-news/1999/02/postal-service-...

jdthedisciple 3y ago

That's pretty amazing. So the whole gzip thing - while fancy - really is extra steps for less bang.

w-m 3y ago

Best one I found is Normalized Mutual Information at 95%. It's a little more complex, but you could still compute it relatively quickly on binarized images. NMI skimage: ~30 seconds, 95% accuracy NMI numba *: ~0.6 seconds, 95% accuracy Here's the code, courtesy of ChatGPT: @njit(cache=True) def compute_joint(img1, img2): stacked = 2 * img1.ravel() + img2.ravel() return np.bincount(stacked, minlength=4).reshape(2, 2) @njit(cache=True) def entropy(counts, total): # Convert counts to probabilities p = counts / total # Only calculate for non-zero entries to avoid log(0) return -np.sum(p[p > 0] * np.log2(p[p > 0])) @njit(cache=True) def normalized_mutual_information(img1, img2): joint_counts = compute_joint(img1, img2) total_pixels = 28*28 # Marginal counts c1 = np.sum(joint_counts, axis=1) c2 = np.sum(joint_counts, axis=0) # Compute entropies directly from counts h1 = entropy(c1, total_pixels) h2 = entropy(c2, total_pixels) joint_entropy = entropy(joint_counts.flatten(), total_pixels) mutual_info = h1 + h2 - joint_entropy return 2 * mutual_info / (h1 + h2)

sr192 3y ago

ben recht's kernel method implementation in 10 lines hits 98% https://github.com/benjamin-recht/mnist_1_pt_2/tree/main https://github.com/benjamin-recht/mnist_1_pt_2/tree/main

tysam_and 3y ago
Great link, thank you so much, lol. This line freaking killed me: https://github.com/benjamin-recht/mnist_1_pt_2/blob/c0fe96bc31ba29d4923956d1421354d584c358da/mnist_1_pt_2.py#L18 https://github.com/benjamin-recht/mnist_1_pt_2/blob/c0fe96bc...

cqz 3y ago

Very cool. I tried using PNG compression, it does actually do better, slightly: PNG : ~15.1 seconds, 83% accuracy I also tried dropping in zstandard compression: Zstd (level=3) : ~3.5 seconds, 88% accuracy Much faster than gzip, at least. And iff I use (x1-x2)*2 instead of x1+x2 to calculate Cx1x2 that pushes zstd up to 93% accuracy. I'm somewhat interested in the fact that if I stack the two arrays on top of each other instead of adding them together, I get absolutely garbage performance (<20%), however as far as I can tell that actually works well when classifying strings.

w-m 3y ago
Re garbage performance on stacking: I had tried interleaving the values (creating a 56x28 img), it dropped one percentage point of accuracy when using gzip.