Markov Sort: an imprecise sorting algorithm

https://github.com/saniv/markov_sort

there's already a thread about this shit http://bbs.progrider.org/prog/read/1398930307

>>2

that is not related to spike sorting and hidden markov models.

saniv

Shalom, Mr. Goldenbergerstein! How's your Hanukkah?

>>4

holidays are for retards and lazy people.

>>2
who cares

praise the muslim prophet sadkov-sama

zhidhub? How have you come to keep your code at zhidhub? You've seriously sold your ass out to the Jews.

>>4
*חנוכה

fixed the sampling bug, greatly improving guess accuracy.

>>7
any better hosting? Preferable Lisp-based.

BTW, now it almost perfectly decides which of two bytes is larger, giving slight errors on 3-byte sequences.


$ gcc markov.c && ./a.out
Training...
Sorting:081,115
Guess: 080,115
Answer: 081,115
$ gcc markov.c && ./a.out
Training...
Sorting:105,030
Guess: 030,104
Answer: 030,105
$ gcc markov.c && ./a.out
Training...
Sorting:036,199
Guess: 036,201
Answer: 036,199
$ gcc markov.c && ./a.out
Training...
Sorting:194,060
Guess: 062,192
Answer: 060,194
$ gcc markov.c && ./a.out
Training...
Sorting:150,103
Guess: 103,147
Answer: 103,150
$ gcc markov.c && ./a.out
Training...
Sorting:210,247
Guess: 209,246
Answer: 210,247
$ gcc markov.c && ./a.out
Training...
Sorting:148,133
Guess: 132,148
Answer: 133,148
$ gcc markov.c && ./a.out
Training...
Sorting:052,110
Guess: 050,108
Answer: 052,110

$ gcc markov.c && ./a.out
Training...
Sorting:193,102,244
Guess: 102,171,244
Answer: 102,193,244
$ gcc markov.c && ./a.out
Training...
Sorting:036,144,175
Guess: 036,141,171
Answer: 036,144,175
$ gcc markov.c && ./a.out
Training...
Sorting:106,185,193
Guess: 101,181,193
Answer: 106,185,193
$ gcc markov.c && ./a.out
Training...
Sorting:101,214,146
Guess: 100,144,211
Answer: 101,146,214
$ gcc markov.c && ./a.out
Training...
Sorting:059,044,201
Guess: 042,068,200
Answer: 044,059,201
$ gcc markov.c && ./a.out
Training...
Sorting:183,254,218
Guess: 182,213,253
Answer: 183,218,254


Next step would be defining "The Markov Programming Language". Think rewrite systems with a fuzzy pattern matching and floating point numbers, instead of symbols or integers. Functions would be definable using natural language, like "to add 123 with 456 write 579", but parser should translate it to floating-point numbers.

And still current version has another sampling bug: addition requires at least 4-byte space, otherwise it won't get enough samples to cover the increment.

>>12
multiplication modulo 256 works perfectly too, if one 0xFF dummy byte is added to input and output spaces.

>>12

Found the bug! It happened because I changed random sampling to chain-indexed one. Statistics bugs are truly hard to comprehend and they don't cause segmentation fault.

this is really interesting

I hope you don't mind me linking to this, but it's good material.

https://github.com/saniv/text/tree/master/criticism

>>2
I hope you kill yourself or die in a horrible dead

>>16
At your own discretion. These notes surely contain a lot of errors, including syntactic ones.

>>17
The problem is that neural scientists, writing that paper, used the word "sort" in the sense of "sorting spikes from background noise", while I meant usual sorting, like in merge sort or sleep sort. Markov modeling is a general tool, applicable to a wide range of problems, not just IRC bots. There is even a data compression algorithm based on markov model prediction (http://en.wikipedia.org/wiki/Dynamic_Markov_compression)

Okay. After fixing most of the sampling bugs, I found it to work relatively well for larger sequences: 32 elements (compared to previous 4). I.e. it may be suitable for a game AI in a simple, Mario-like, game, where these numbers encode the terrain and objects around the AI agent.

$ gcc markov.c && ./a.out
Training...
Sorting:007,001,128,077,236,101,119,213,204,224,230,098,078,129,159,193,088,040,153,159,176,253,253,095,039,204,222,201,016,001,221,224
Guess: 004,004,026,031,051,048,057,074,077,091,099,095,098,109,127,135,129,137,155,153,172,182,193,188,191,204,216,222,223,232,243,251
Answer: 001,001,007,016,039,040,077,078,088,095,098,101,119,128,129,153,159,159,176,193,201,204,204,213,221,222,224,224,230,236,253,253
$ gcc markov.c && ./a.out
Training...
Sorting:042,111,083,205,175,020,044,101,054,047,022,093,105,204,230,227,158,130,058,085,137,140,128,014,123,065,216,041,057,140,065,044
Guess: 004,014,025,029,043,037,051,062,057,066,078,089,100,106,120,124,136,130,135,147,157,164,169,171,188,194,215,207,216,226,233,239
Answer: 014,020,022,041,042,044,044,047,054,057,058,065,065,083,085,093,101,105,111,123,128,130,137,140,140,158,175,204,205,216,227,230
$ gcc markov.c && ./a.out
Training...
Sorting:142,018,003,230,202,076,249,252,127,212,017,059,135,092,204,109,068,098,147,246,196,171,235,131,107,003,007,169,099,028,193,120
Guess: 010,012,011,035,045,042,058,069,072,083,077,089,105,104,123,122,124,134,147,163,171,168,183,189,191,194,203,219,222,230,245,248
Answer: 003,003,007,017,018,028,059,068,076,092,098,099,107,109,120,127,131,135,142,147,169,171,193,196,202,204,212,230,235,246,249,252
$ gcc markov.c && ./a.out
Training...
Sorting:087,131,225,174,170,061,139,082,051,035,158,236,039,196,186,012,092,054,074,052,159,124,047,119,127,236,037,093,107,001,102,081
Guess: 006,017,025,032,042,043,053,063,061,072,087,098,091,109,120,112,119,131,137,150,160,165,176,185,188,208,201,209,217,224,235,240
Answer: 001,012,035,037,039,047,051,052,054,061,074,081,082,087,092,093,102,107,119,124,127,131,139,158,159,170,174,186,196,225,236,236
$ gcc markov.c && ./a.out
Training...
Sorting:004,140,241,102,125,174,175,182,098,177,170,077,053,227,244,255,234,052,110,186,063,022,166,214,223,002,235,072,048,125,183,149
Guess: 004,020,036,034,045,051,062,067,077,083,093,093,093,120,134,139,143,139,148,161,161,172,182,193,207,201,222,218,223,234,243,251
Answer: 002,004,022,048,052,053,063,072,077,098,102,110,125,125,140,149,166,170,174,175,177,182,183,186,214,223,227,234,235,241,244,255


>>19

I'm sure it could be future improved by throwing away non-correlated transitions, when statistics shows that one bit doesn't affect the other. It would also improve evaluation speed (less bits to gather).

i love you nikita

completely pointless. even those satirical profanity-full code samples are better than this since at least they provide entertainment.

>>22
wats ur problem dude?

>>22

entertain my anus, dubs-guy.

If instead of sorting, we just rank the numbers (i.e. decide their positions in the sorted list), then the accuracy would be higher.

>>22
At least it is very simple and can do addition out of the box, while neural networks can't (unless one simulates addition, doing a lot of basic logic).


$ gcc markov.c && ./a.out
Training...
Adding:1.825000,0.650000
Guess: 2.575000
Answer: 2.475000
Adding:2.275000,1.275000
Guess: 3.275000
Answer: 3.550000
Adding:2.325000,1.950000
Guess: 3.750000
Answer: 4.275000
Adding:1.050000,1.975000
Guess: 3.025000
Answer: 3.025000
Adding:0.525000,2.075000
Guess: 2.825000
Answer: 2.600000
Adding:1.250000,1.250000
Guess: 2.600000
Answer: 2.500000
Adding:1.075000,0.250000
Guess: 1.800000
Answer: 1.325000
Adding:0.525000,2.875000
Guess: 3.275000
Answer: 3.400000
Adding:0.875000,1.150000
Guess: 2.350000
Answer: 2.025000
Adding:1.375000,1.875000
Guess: 3.125000
Answer: 3.250000
Adding:1.525000,1.725000
Guess: 3.075000
Answer: 3.250000
Adding:2.275000,0.700000
Guess: 2.950000
Answer: 2.975000
Adding:2.350000,2.825000
Guess: 4.300000
Answer: 5.175000
Adding:2.225000,2.750000
Guess: 4.175000
Answer: 4.975000
Adding:0.900000,0.850000
Guess: 2.100000
Answer: 1.750000
Adding:2.925000,0.850000
Guess: 3.525000
Answer: 3.775000
Adding:0.475000,1.775000
Guess: 2.575000
Answer: 2.250000
Adding:0.125000,2.675000
Guess: 2.950000
Answer: 2.800000
Adding:2.400000,2.875000
Guess: 4.350000
Answer: 5.275000
Adding:3.025000,1.425000
Guess: 3.850000
Answer: 4.450000
Adding:2.050000,2.900000
Guess: 4.150000
Answer: 4.950000
Adding:0.175000,2.100000
Guess: 2.650000
Answer: 2.275000
Adding:0.325000,1.850000
Guess: 2.575000
Answer: 2.175000
Adding:2.650000,0.200000
Guess: 3.100000
Answer: 2.850000
Adding:1.650000,2.200000
Guess: 3.500000
Answer: 3.850000
Adding:0.725000,0.350000
Guess: 1.625000
Answer: 1.075000
Adding:2.600000,0.175000
Guess: 3.050000
Answer: 2.775000
Adding:1.950000,2.950000
Guess: 4.100000
Answer: 4.900000
Adding:2.875000,0.150000
Guess: 3.275000
Answer: 3.025000
Adding:2.150000,1.600000
Guess: 3.375000
Answer: 3.750000
Adding:1.950000,0.725000
Guess: 2.700000
Answer: 2.675000
Adding:1.250000,0.875000
Guess: 2.325000
Answer: 2.125000
Adding:0.625000,2.325000
Guess: 3.025000
Answer: 2.950000
Adding:3.000000,0.475000
Guess: 3.450000
Answer: 3.475000
Adding:1.125000,0.300000
Guess: 1.850000
Answer: 1.425000
Adding:1.700000,0.725000
Guess: 2.525000
Answer: 2.425000
Adding:2.625000,0.675000
Guess: 3.225000
Answer: 3.300000
Adding:1.575000,0.700000
Guess: 2.400000
Answer: 2.275000
Adding:0.150000,1.825000
Guess: 2.475000
Answer: 1.975000
Adding:0.275000,2.750000
Guess: 3.050000
Answer: 3.025000



>>26

What is even funnier is that it can loosely follow even 8-bit XOR!

$ gcc markov.c && ./a.out
Training...
XORing:078,05f
Guess: 030
Answer: 027
XORing:051,039
Guess: 044
Answer: 068
XORing:06e,037
Guess: 046
Answer: 059
XORing:032,06d
Guess: 04d
Answer: 05f
XORing:03b,065
Guess: 044
Answer: 05e
XORing:060,057
Guess: 033
Answer: 037
XORing:070,01f
Guess: 054
Answer: 06f
XORing:011,00a
Guess: 022
Answer: 01b
XORing:03f,023
Guess: 03f
Answer: 01c
XORing:038,005
Guess: 037
Answer: 03d
XORing:024,064
Guess: 050
Answer: 040
XORing:011,06d
Guess: 054
Answer: 07c
XORing:00b,055
Guess: 04c
Answer: 05e
XORing:063,019
Guess: 056
Answer: 07a
XORing:073,068
Guess: 02d
Answer: 01b
XORing:06f,05d
Guess: 031
Answer: 032
XORing:056,02f
Guess: 04a
Answer: 079
XORing:018,023
Guess: 02e
Answer: 03b
XORing:02b,063
Guess: 04f
Answer: 048


nikita could you explain the premise of what you are doing here? I find it interesting but I don't want to go through your code and reverse engineer the meaning of your variable names.

>>28

I built a Markov Model to predict the next state based on the previous state. The main idea was to explore if markov could be used to speed-up the AI from http://www.cs.cmu.edu/~tom7/mario/mario.pdf

That is why I'm using byte ordering as a test case.

Have just fixed another sampling mistake. Since initial code, there were about 5 (five!) sampling bugs! That is 1 bug per 30 lines of code. Noting that 150 lines of C code could be rewritten to 50 of Lisp, that gives use whooping 1 bug per 10 lines of code!

Moral: statistics is enormously hard to do correctly, so never believe these statistical surveys.

FUCK OFF WITH YOUR BABIES FIRST IRC BOT BULLSHIT

>>26

http://newsgroups.derkeiler.com/Archive/Comp/comp.ai.philosophy/2008-04/msg00333.html

If I have a problem say I want to input 2 numbers and Result is say

Addition. How will I teach neural network the Addition?

Your best bet would be to teach it addition like you were taught.

First start by teaching it to count from 0 to 9

0 -> 1
1 -> 2
2 -> 3
....
8 -> 9

Then using that neural network, teach it to count from 0 up to the
infinite. Well, instead of the infinite, you may assume a short-term
memory of 9 digits, and teach it to increment a number stored in that
short term memory.

Then add a new NN and teach it the addition table, [0..9]x[0..9].

Then another NN that would be able to add two numbers with the carry.

Trying to build a single neural network to do something like an
addition (over what range of numbers?) would be silly. Neural network
work better with fuzzy data. To implement a Von Neumann computer over
neural network, it's best to do like in the brain, have several
different neural networks interconnected, like units in a processor.

Learning 1-bit XOR requires just a few examples (no complex backpropagation crap and can be done online, during a playthrough). I'm really agreeing with MIT professor, who says that ANNs are not the only way to fit a curve (http://www.youtube.com/watch?v=q0pm3BrIUFo)


$ gcc markov.c && ./a.out
Training...
Input: 255,000
Guess: 255
Answer:255
Input: 000,000
Guess: 004
Answer:000
Input: 000,000
Guess: 004
Answer:000
Input: 000,255
Guess: 253
Answer:255
Input: 000,000
Guess: 004
Answer:000
Input: 255,255
Guess: 006
Answer:000
Input: 255,255
Guess: 006
Answer:000
Input: 000,000
Guess: 004
Answer:000
Input: 255,255
Guess: 006
Answer:000
Input: 255,000
Guess: 255
Answer:255
Input: 255,255
Guess: 006
Answer:000
Input: 255,255
Guess: 006
Answer:000
Input: 000,000
Guess: 004
Answer:000
Input: 255,255
Guess: 006
Answer:000
Input: 255,255
Guess: 006
Answer:000
Input: 255,000
Guess: 255
Answer:255
Input: 000,000
Guess: 004
Answer:000
Input: 255,255
Guess: 006
Answer:000
Input: 255,000
Guess: 255
Answer:255
Input: 255,000
Guess: 255
Answer:255
Input: 255,000
Guess: 255
Answer:255
Input: 000,000
Guess: 004
Answer:000
Input: 000,000
Guess: 004
Answer:000
Input: 255,000
Guess: 255
Answer:255
Input: 000,255
Guess: 253
Answer:255
Input: 000,000
Guess: 004
Answer:000
Input: 255,255
Guess: 006
Answer:000
Input: 000,255
Guess: 253
Answer:255
Input: 255,255
Guess: 006
Answer:000
Input: 000,000
Guess: 004
Answer:000
Input: 000,000
Guess: 004
Answer:000
Input: 000,255
Guess: 253
Answer:255
Input: 000,000
Guess: 004
Answer:000
Input: 000,255
Guess: 253
Answer:255
Input: 255,000
Guess: 255
Answer:255
Input: 255,255
Guess: 006
Answer:000
Input: 000,000
Guess: 004
Answer:000
Input: 000,255
Guess: 253
Answer:255
Input: 000,255
Guess: 253
Answer:255
Input: 000,255
Guess: 253
Answer:255
$


>>33
4-variable 1-bit XOR requires 80 chains (40 chains gave wrong predictions, despite huge training set). In general case this can surely be improved be refraining votes from uncorrelated transitions, but in case of XOR all votes seems to be equally important (everything is correlated to everything). Dunno how to future improve it.

$ gcc markov.c && ./a.out
Training...
Input: 1,1,1,1
Guess: 0
Answer:0
Input: 0,0,1,0
Guess: 1
Answer:1
Input: 1,1,1,0
Guess: 1
Answer:1
Input: 1,1,1,1
Guess: 0
Answer:0
Input: 1,0,1,1
Guess: 1
Answer:1
Input: 0,1,0,1
Guess: 0
Answer:0
Input: 0,1,1,1
Guess: 1
Answer:1
Input: 0,1,0,1
Guess: 0
Answer:0
Input: 1,0,0,0
Guess: 1
Answer:1
Input: 1,1,1,1
Guess: 0
Answer:0
Input: 1,0,1,0
Guess: 0
Answer:0
Input: 0,0,0,1
Guess: 1
Answer:1
Input: 0,1,0,1
Guess: 0
Answer:0
Input: 1,1,1,1
Guess: 0
Answer:0
Input: 1,1,0,0
Guess: 0
Answer:0
Input: 1,1,1,1
Guess: 0
Answer:0
Input: 1,1,1,1
Guess: 0
Answer:0
Input: 1,1,0,0
Guess: 0
Answer:0
Input: 0,0,1,1
Guess: 0
Answer:0
Input: 0,1,0,0
Guess: 1
Answer:1
Input: 1,1,0,1
Guess: 1
Answer:1
Input: 1,1,0,1
Guess: 1
Answer:1
Input: 1,1,1,0
Guess: 1
Answer:1
Input: 0,0,1,0
Guess: 1
Answer:1
Input: 1,1,0,0
Guess: 0
Answer:0
Input: 1,0,1,1
Guess: 1
Answer:1
Input: 0,0,0,0
Guess: 0
Answer:0
Input: 0,1,1,0
Guess: 0
Answer:0
Input: 0,1,1,0
Guess: 0
Answer:0
Input: 1,0,1,0
Guess: 0
Answer:0
Input: 0,1,1,0
Guess: 0
Answer:0
Input: 1,0,0,0
Guess: 1
Answer:1
Input: 0,1,0,1
Guess: 0
Answer:0
Input: 0,1,1,1
Guess: 1
Answer:1
Input: 0,1,1,0
Guess: 0
Answer:0
Input: 1,0,1,1
Guess: 1
Answer:1
Input: 1,0,1,0
Guess: 0
Answer:0
Input: 0,0,0,1
Guess: 1
Answer:1
Input: 1,1,1,0
Guess: 1
Answer:1
Input: 0,0,1,1
Guess: 0
Answer:0