Structured Compromise System

If one or more parties in a negotiation is unwilling to compromise, many decision making processes can grind to a halt; the current state of American politics being a prime example. What's needed is a framework that forces uncooperative sides to come to an agreement, while according each their appropriate level of influence. Rather than a series of small votes with an implied give and take linking them, all points should be considered explicitly together. Each party could propose actions to be taken, and would receive points based on their degree of representation which could spend to support or oppose each of these proposals. This process could undergo many iterations as each side determines where best to spend their influence. There would be no partial implementations, instead new, toned down versions of previous suggestions would be added to achieve this effect. For directly contradictory items only the highest scoring of them would go into effect, so the parties would have to split unrelated items up, rather than presenting them as a single action item. A limit to the number of proposals may be required, however, to prevent either side for complicating things intentionally.

By eliminating a series of small gated decisions, the ability to impede action is greatly reduced. Even if closely matched in point totals, differing priorities will make deadlock unlikely in most instances. The final point allocations would provide clear record of the weight each party places on various areas and help voters more easily see if they are being properly represented. This technique could equally be applied to compromises other than in politics and theoretically to any number of participants. Which chores each family member should do around the house, for example.

To prevent attempts to game the system by endlessly changing their point allocations, a tax on changes could be employed. In its most basic form, all changes would be penalized, but a more sophisticated one would allow all parties to alter their positions if they all agreed to do so. If only some wished to change, then the tax could be applied only to those parties. To clarify, in that case everyone would get to reallocate but those not asking for another round wouldn't be penalized. This would discourage huge changes but still allows the participants to come to an accommodation of each others priorities.

This system grew out of one I came up with to help with a software maker's survey problems. They would ask users on their website what new features they would like to see in future versions so they could gauge where to focus their development effort. Somewhat predictably, the users all voted for all the good features, providing little useful direction. I suggested each user get points they could allocate to various features, with the amount received varying by things such as forum participation, useful bug reporting, or number of copies of the software purchased. For reasons I've never quite understood, they weren't interested in the notion.

Attractiveness Components

I was pondering the different ways people can be viewed as attractive, and decided to systematize it. I am considering only static images of a neutral appearance, so no personality cues are incoporated. Using evolutionary pressures as a guide, I came up with the following four:

• desire to protect children
• desire for general health
• desire for the gender we are sexually attracted to
• desire for peak fecundity

The first component evinces itself in what I refer to as "cuteness". It can sometimes be at odds with the last measure, depending on the one making the judgement, giving rise to the "cute but not sexy" phenomena. The second is the typical beauty measures that we hear so much about: symmetry, proportion, height, clear skin, etc. The third is simply how much your appearance contains gender cues. Note that how this is interpreted by the viewer is what matters, so it says nothing of your absolute attractiveness in its own right. A good example of someone who varies from their stereotypical gender appearance but is still very attractive would be Katharine Hepburn, who has often been referred to as a "handsome" woman. The last is straightforward, mostly being about not being too old or too young, although it can overlap the second to some extent depending on how you frame the two.

The way this could be used in practice would be to have users rate many images whose components have been determined for overall attractiveness. Standard recommendation system techniques could then be used to infer the value each user places on each component, and should then allow estimating the rating of new photos once they've had their components rated. You could omit the requirement that images have their components directly determined, inferring them as well, but that would result in far slower convergence for newly added images.

Traveling Salesman Problem Algorithm

I'd suggest fullscreen.

A genetic algorithm based traveling salesman problem project I implemented recently inspired me to explore an idea I had in the 90s to solve a particular version of the problem: where travel cost is proportional to distance. In the real world, this is often not the case, but in some applications it is, such as PC board drilling. It works like this: create an initial tour with only just enough cities to form a convex hull around the remaining ones, then use a greedy algorithm to add interior cities one at a time. Since this can lead to loops, I then run a de-looping routine on it. Correcting the loops turns out to be faster and better than preventing loops during the greedy process itself as well as being simpler. The video of the process has been slowed down about a thousand times.

It performs about 2% worse than my genetic algorithm based solution, but also about 2% better than a standard greedy algorithm followed by a de-looping routine, and could be made considerably faster than a GA based one for larger problems. The test version I did was written quickly with little attention to performance, but could be improved fairly easily. Doubt I would need such a thing, but it feels good to have finally tried it.

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.