The game of go has such a large board that it swamps traditional approaches to solve it via computer. To get around this, I have a simple hack: initially, the computer moves in exact symmetry to the player. Then, when the board has filled up and the search space has reduced in size, use a more traditional approach to go on the offense. This should work as moving symmetrically maintains a completely neutral board state. I've tested this by hand against computer go programs to verify it works, and I can tie them every time without even looking at the board. The tedium such an approach would create for a human opponent would also give the computer a possible advantage, assuming they don't quit in disgust first.
Showing posts with label computers. Show all posts
Showing posts with label computers. Show all posts
Saturday, April 23, 2011
Go Hack
The game of go has such a large board that it swamps traditional approaches to solve it via computer. To get around this, I have a simple hack: initially, the computer moves in exact symmetry to the player. Then, when the board has filled up and the search space has reduced in size, use a more traditional approach to go on the offense. This should work as moving symmetrically maintains a completely neutral board state. I've tested this by hand against computer go programs to verify it works, and I can tie them every time without even looking at the board. The tedium such an approach would create for a human opponent would also give the computer a possible advantage, assuming they don't quit in disgust first.
Saturday, December 5, 2009
Smart Phone Inspired OS Reform
For a long time the standard for computer applications and operating systems has been "good enough", but mobile device users demand more. More responsiveness, more reliability, more integration, and more ease of use. I am hoping that the emergence of smart phones will result in this demand for increased quality being transferred back to computers in general. Reliability concerns are obvious, so let me give an example of an ease of use issue: change of focus. Frequently when I'm typing in a text field, a program or requester will pop up, changing the focus and resulting in my having to not only hunt for the window I was working in, but also to retype all the text I entered. While arguably a small thing, it occurs frequently and has become a considerable annoyance. This is the sort of easily fixed, idiotic interface glitch that would be unacceptable to mobile device users. Or programs that sit frozen until they have completely loaded. It would be trivial to load enough of the program to allow the user to start working, while the rest of the application loads in the background.
However, I am hoping for more than small improvements. The entire paradigm employed by operating systems is flawed and a legacy of its early days. Right now a file system view model is used, which closely mirrors what's actually going on inside the computer, but is confusing and inefficient for most users. Instead, a greater degree of abstraction needs to be employed. Why is it useful to most users to be able to store their Word documents in strange places anywhere on the drive? The user should neither need to know nor care about such details. Instead of an interface model based on "Here's everything on your entire hard drive, have fun" with some crude tools such as the dock and folders to help organize things, it should be more along the lines of what a smart phone uses: "Here are the top things you do all the time, which would you like?" with a slightly more extended process to access the less common tasks. The user could organize these with an automatic system that tracks their usage habits (although it should never change the interface without user consent). This should be more than a smarter dock, but the primary way one interfaces with their computer, with everything geared towards supporting it. When it comes to using complex systems, less is more. Of course power users will need more advanced features, but they are an extremely small subset and even most of their needs will be met by a simpler, more directed interface. As long as they can step outside of it when required, it should impose no penalty. In general what it comes down to is that comparatively wimpy smart phones have to do more with less, and I am hopeful that the end products of that need will transfer back to general computing.
Thursday, November 5, 2009
The Real World Birthday Problem
Originally posted on my private blog September 19th, 2008.The birthday problem is a well known mathematical illustration. Basically it asks how many people are needed in one room before two of them have a 50% chance of sharing a birthday. The answer is 23, which apparently is lower than what most people's intuition suggests. That result, however, is based on math that assumes that birthdays occur uniformly throughout the year and that also neglects leap days. I was curious what effect this might have, so I went looking for some birth statistics. The closest I found was a list of U.S. births by day for 1978. Series 1 (dark blue) is the raw information, which as you can see has a weekly cycle with much lower birth rates on weekends (especially Sunday). Unfortunately I needed to remove this effect as every date occurs on every day of the week in the long run. Not having other years to work with, I filtered the data, averaging every day with the births for three days before and after so that every weekday would be included. This is shown as series 2 (pink). Series 3 (yellow) is what the assumption of completely uniform birth rates would look like and is included for comparison. You can see that birth rates are significantly higher in the second half of the year. Unfortunately, 1978 wasn't a leap year, so I averaged the values of February 28th and March 1st and then weighted the leap day to be one quarter as likely (not shown).
Next I had to use this data to compute the probability distribution. I went with a simulation approach, which means I just performed the experiment a lot of times and kept track of how many people it took to get a matching pair of birthdays. Not sure of how many trials were needed to be accurate, I did successively larger runs, starting with ten thousand and ending with a billion, each run being an order of magnitude larger. You can see that the results converge, with the last two curves being right on top of each other.
Finally, here are the cumulative probability distributions of both the standard mathematical model (series 1) and my simulated one using real data (series 2). You can see that the two are basically identical and in fact the maximum error is less than two tenths of one percent. This means that all the effects of non-uniform birthday occurrence average out in practice. If the data had been more dramatically clustered this might not have been the case, but now I know for sure. In case you're wondering, a couple professors have written papers on this very topic, but I wanted to do it for myself as a mental exercise.
Saturday, July 11, 2009
Weighted Song Playing Script
Note that this post has superseded by a new, smart playlist based approach. You can check it out here, where it's available for download.I have been working on a music weighting script that performs two functions:
1) Determines a rating based on the song's skip and play count information, using proper statistics to account for the uncertainty from small sample sizes. It will also call attention to songs whose ratings are at odds with their actual play history so they can be reevaluated manually if desired (it will automatically do this, but it will take longer). Generating ratings is quite useful for large libraries where sorting music by hand is time consuming. Existing ratings and play and skip data are all taken into account during this process.
2) Determines a play order that gives preference to a song based on its play and skip history as well as the amount of time it's been since it's been played or skipped. It does so in a properly randomized fashion to prevent similarly rated songs from clumping together and to account for uncertainty in the data. This mode is compatible with custom playlists as it will simply pay attention the weighting for the songs contained in the list. It also adjusts the level of advantage popular songs have over unpopular ones to maintain a user defined level of songs successfully being played.
The program is written in Applescript and runs on Macs via iTunes. It adjusts the last played date of each song which allows iPods and iTunes to sort based on that simple parameter. The script can easily be set up to run automatically every few days. Note that almost all music players do not keep play and skip count information and would therefore be incompatible with my script, so it's pretty much Apple devices only. I've tested this script quite extensively, and if anyone is interested in giving it a try leave a comment and I'll write up documentation for it. Since proper docs are a lot of work I'll hold off until there is a request. If requested, I could make a version that only generated song ratings from the play / skip info. The working assumptions are different for a one time examination than a continuous process, but I've already worked out the algorithmic differences.
Theory:
The script is built around the binomial distribution defined by each song's play and skip count information. The distribution is used as the basis for a non-uniform random number generator to compute a weight, which is then multiplied by the amount of time since the song was last attempted (ie played or skipped). While the math for the cumulative binomial distribution is known, the inverse has not been solved explicitly, so a binary search is used to generate the random values.
To control the global success rate when playing songs, the weight generated by the non-uniform random number generator is raised to a power. Since all the weights are in the range from zero to one, the resulting value is also in that range, and values closer to one will decrease less in size. This gives, on average, and advantage to more popular songs. As an example:
The mean ratio for a one star song is 0.1, and the mean for a five star song is 0.9.
This means that normally a five star song will play .9/.1 = 9 times more frequently.
If the results are raised to a power of 1.5, one gets: (.9^1.5) / (.1^1.5) = 27 times more frequently.
The greater the exponent becomes, the larger the advantage higher rated songs will have. In theory, as a lot of data is collected on how popular each song is such a system shouldn't be required, but it can take quite some time for that to occur. It's important not to raise the exponent too high, or else lower rated songs and those simply lacking any information will very rarely be played. The user can set the desired range. The script waits until at least 50 songs have been played or skipped and then uses the ratio of success to guess what the exponent should be adjusted to. The last several runs are averaged together to prevent sharp changes in the output.
To determine the song's rating the binomial distribution formed by the song's play and skip count history is used to determine a rating that is greater than at least 5% of the distribution's total area (this threshold is user controllable). If a manual rating has been set, the script will slowly move the rating away from that value as the data shows it is unlikely. If no rating is provided, a neutral rating of 0.5 is assumed.
The rating doesn't actually effect the weighting algorithm, since the binomial distribution formed by the play and skip counts is used. To incorporate a user's manual rating, therefore, virtual plays and skips are added to the song's actual ones to change the distribution. The relative weight of the rating can be set, and a separate weight is used for computed ratings (iTunes shows hollow stars if a song's album has been rated but the song itself has no rating). The virtual counts are maintained separately so they can be discarded if the real data shows the user's rating to be flawed. If the user changes the rating to one incompatible with the existing data, the data is cleared and the song tested from scratch. The assumption is that the user has observed the data and disagrees with the conclusion for some reason (perhaps someone else had been using their iPod!).
One idea for improvement I'm considering is having the script generate album ratings based on data collected on that album's (or maybe even just artist's) songs. In theory this could allow songs to converge more quickly. It wouldn't count for as much as a manual user rating, but it doesn't require any extra effort. The best system would be for Genius to generate projected ratings, much as Netflix does, but Apple's lousy Genius paradigm is the subject for another post.
1) Determines a rating based on the song's skip and play count information, using proper statistics to account for the uncertainty from small sample sizes. It will also call attention to songs whose ratings are at odds with their actual play history so they can be reevaluated manually if desired (it will automatically do this, but it will take longer). Generating ratings is quite useful for large libraries where sorting music by hand is time consuming. Existing ratings and play and skip data are all taken into account during this process.
2) Determines a play order that gives preference to a song based on its play and skip history as well as the amount of time it's been since it's been played or skipped. It does so in a properly randomized fashion to prevent similarly rated songs from clumping together and to account for uncertainty in the data. This mode is compatible with custom playlists as it will simply pay attention the weighting for the songs contained in the list. It also adjusts the level of advantage popular songs have over unpopular ones to maintain a user defined level of songs successfully being played.
The program is written in Applescript and runs on Macs via iTunes. It adjusts the last played date of each song which allows iPods and iTunes to sort based on that simple parameter. The script can easily be set up to run automatically every few days. Note that almost all music players do not keep play and skip count information and would therefore be incompatible with my script, so it's pretty much Apple devices only. I've tested this script quite extensively, and if anyone is interested in giving it a try leave a comment and I'll write up documentation for it. Since proper docs are a lot of work I'll hold off until there is a request. If requested, I could make a version that only generated song ratings from the play / skip info. The working assumptions are different for a one time examination than a continuous process, but I've already worked out the algorithmic differences.
Theory:
The script is built around the binomial distribution defined by each song's play and skip count information. The distribution is used as the basis for a non-uniform random number generator to compute a weight, which is then multiplied by the amount of time since the song was last attempted (ie played or skipped). While the math for the cumulative binomial distribution is known, the inverse has not been solved explicitly, so a binary search is used to generate the random values.
To control the global success rate when playing songs, the weight generated by the non-uniform random number generator is raised to a power. Since all the weights are in the range from zero to one, the resulting value is also in that range, and values closer to one will decrease less in size. This gives, on average, and advantage to more popular songs. As an example:
The mean ratio for a one star song is 0.1, and the mean for a five star song is 0.9.
This means that normally a five star song will play .9/.1 = 9 times more frequently.
If the results are raised to a power of 1.5, one gets: (.9^1.5) / (.1^1.5) = 27 times more frequently.
The greater the exponent becomes, the larger the advantage higher rated songs will have. In theory, as a lot of data is collected on how popular each song is such a system shouldn't be required, but it can take quite some time for that to occur. It's important not to raise the exponent too high, or else lower rated songs and those simply lacking any information will very rarely be played. The user can set the desired range. The script waits until at least 50 songs have been played or skipped and then uses the ratio of success to guess what the exponent should be adjusted to. The last several runs are averaged together to prevent sharp changes in the output.
To determine the song's rating the binomial distribution formed by the song's play and skip count history is used to determine a rating that is greater than at least 5% of the distribution's total area (this threshold is user controllable). If a manual rating has been set, the script will slowly move the rating away from that value as the data shows it is unlikely. If no rating is provided, a neutral rating of 0.5 is assumed.
The rating doesn't actually effect the weighting algorithm, since the binomial distribution formed by the play and skip counts is used. To incorporate a user's manual rating, therefore, virtual plays and skips are added to the song's actual ones to change the distribution. The relative weight of the rating can be set, and a separate weight is used for computed ratings (iTunes shows hollow stars if a song's album has been rated but the song itself has no rating). The virtual counts are maintained separately so they can be discarded if the real data shows the user's rating to be flawed. If the user changes the rating to one incompatible with the existing data, the data is cleared and the song tested from scratch. The assumption is that the user has observed the data and disagrees with the conclusion for some reason (perhaps someone else had been using their iPod!).
One idea for improvement I'm considering is having the script generate album ratings based on data collected on that album's (or maybe even just artist's) songs. In theory this could allow songs to converge more quickly. It wouldn't count for as much as a manual user rating, but it doesn't require any extra effort. The best system would be for Genius to generate projected ratings, much as Netflix does, but Apple's lousy Genius paradigm is the subject for another post.
Subscribe to:
Posts (Atom)
