These pages are my simple attempt at a blog. I suspect I wont be posting that often...

Blog comments powered by Disqus. Go to the individual blog posts to read or leave comments.

Posted mid-morning Sunday, January 13th, 2013

A Rating Based Proportional Representation Voting System

The aim of this post is to dicuss the design of a rating based proportional representation voting system. Most well-known voting systems today are ranking based. Unfortunately, ranking based voting systems are subject to impossibility results such as Arrows theorem. However, rating based voting systems, such as Range Voting are not subject to Arrow's Theorem (although they are subject to other impossibility theorems), and appear to perform well as voting systems. However, I am currently unaware of any rating based proportional representation voting systems. This proposal aims to fill that gap.

A major part of designing a proportional representation voting system is in defining exactly what is meant by 'proportinal representation'. Imagine we have three voters, many candidates and three positions to be filled.  Two voters think the same way, the third differently.  Should each voter get to assign their best choice for one position, or should the two voters who agree outvote the other and choose all three positions.

The outvoting option leads to a voting system such as the simple extension of Range voting discussed in the companion blog post.  We might achieve the 'everyone gets to assign one rep' result using some form of maximisation; the voting system tries to maximise over all selections of groups of winners the minimum over all electors of the maximum over candidates in the winning group of the score given by the elector to the candidate. This leads to ties, but there are worse problems.

Imagine we have 500 electors selecting from 5 candidates for 4 positions.  Imagine 250 of them like two candidates, 249 of them like another two, and one lone elector likes the final candidate.  Should the lone elector's candidate be selected?  I would suggest not: the lone elector is too small a percentage of the electorate.  Yet the minimax selection criteria gives lone voices a strong say.

Proposed meaning of Proportional Representation

Idea: We want the rating of ideas by the members of the elected body to match the rating of ideas by the electors.

(There is a secondary point here that the discussion in the deliberative body should have a similar range of ideas to the electors. It is also likely that the final preferences of the elected body might not match the initial preferences of the elected body, they'll change their mind as they research and debate a particular topic, but those final preferences should match the 'educated preferences' of the general population. I will not discuss this digression further.)

Imagine there was some large space of ideas.  Each elector could rate each idea in the real range from zero to one giving a function, f: Idea -> [0,1].  This function represents the elector's preferences.  We could then perform range-voting over the space of ideas by averaging the electors' preference functions.  I'll call this average the electorate preference function.  If we want to select one idea amongst a set of ideas then we simply choose the idea from that set with the highest electorate preference value.  (I'm being a bit loose with terminology here - how do we deal with sets of ideas, etc.  But it is close enough.)

If we wanted to insert representatives in here, we could imagine that each representative also has a preference function.  We could then choose the set of representatives whose average preference function most closely matches the electorate preference function.  (If we were considering the secondary point above of having the 'debate' match, then we might also want the dsitribution of functions making up the average to be similar in each case.)

For this to work, we would need some distance measure for preference functions.  Note that this means that in general the decisions of the elected body would be similar to the decisions of the electorate voting as a whole (modulo the distance measure).  (Note: Should the distance measure be trying to preserve orderings rather than absolute values?)

With this approach we would get neither of the issues above (assuming a reasonable distance measure).  In the first example with three voters, you'd get each elector/voter specifying a representative because that would give the best match.  In the later example where there is one lone elector, they would probably be ignored because they would be a small part of the average preference function.

A major issue in terms of implementing this system is that we don't have any preference functions, either the electors' or candidates'.  (Even with this limitation, the approach could still be used to benchmark electoral systems by generating synthetic preferences.) We will now try to design a voting system anyway.

Proportional Representation Through Utility Matching

Even though we do not have any preference functions, I will assume that each elector can rate how similar each candidate's expressed preferences are to their own.  We will ask each elector to give their perceived distance to each candidate (a vector that is vaguely reminiscent of the ratings vector in range voting).

Unfortunately these ratings will not, in general, be a valid distance metric - everyone is going to rate in their own, inconsistent, way.  However, those ratings do indicate your preference in some way.

Imagine we have a matrix of electors (one per row) by candidates (one per column) with the rating of each candidate by that elector in each cell.  Call this the vote matrix, v.

We want to find a selection matrix, s.  This is a |c| by |c| matrix such that v is close to v x s.  s being the identity would work so far - everyone is elected, but now we need to introduce constraints: s has only as many non-zero rows as there are positions in the body to be elected.  Additionally, each non-zero row has the same sum.  Finally, each entry in s is >= 0.

The s that makes v.s closest to v is the one to select.  Each non-zero row corresponds to a candidate being elected.

Note that the general problem, when we rely upon votes to indicate preferences, is not always able to be solved well. If everyone votes for themselves then v is the identity matrix. There is no low-rank representation of the identity matrix.

There are issues here: how do you define closest when comparing v and v.s?  L_2?  L_1?  Furthermore, once you have selected a norm, how do you do the constrained optimisation.  The constraints appear highly non-convex.

The problem of finding such an s matrix is a variant of the problem known in the literature as the Column Subset Selection Problem. Usually it is phrased like this; given a matrix A (our v), find a pair of matrices C and X such that:

  • C is composed of k distinct columns of A (k is the number of positions to be filled in our version)
  • || A - C X || is minimised (for some norm ||||)

The non-negative column subset selection problem adds the constraint that X is non-negative. We have the additional constraint that all X's rows sum to the same value.

The original column subset selection problem finds a set of columns of A that span the column space of A. In voting terms this means that every voter has their preferences represented by someone, similar to the minimax solution mentioned briefly above.

However, this solution allows 'negative representation' - a candidate is elected because they hold the exact opposite views of the voter they represent. This is not good from a voting perspective. It is to remove this that we add the non-negativity constraint to X. With this constraint, people can only be represented by people they agree with.

A second difference from the normal CSSP is that we don't just want everyone's views represented - we want them represented proportionally. Adding the constraint that the rows of X sum to the same value means that columns with larger 'singular values' need to be replicated (or have other, similar, columns included as well), rather than just having a larger multiplier in X. It is this constraint that gives us 'proportionality'.

Implementation Issues

Unfortuntely, the column subset selecton problem is difficult to solve optimally. Efficient randomised approximation algorithms are known, but it is not known if there are extensions to the varient of the CSSP we use here.

Use of a randomised approximation algorithm for an election raises interesting political issues. One could imagine the following setup:

1 After the election, the voting matrix V is published (but rows never identified with individual voters). 2 A lottery is then held to determine a random seed for the randomised algorithm. 3 The randomised algorithm is used to determine a proposed set of candidates, and an associated X matrix and error. 4 There is then a 1 month period during which anyone can propose a different set of candidates, X matrix and error. It is efficient to check that the error is correct given the candidates and X matrix. If the error is better than the best error known then the new set of candidated is kept as the current best. 5 At the end of the 1 month period since the end of the election the result is certified as the best set of candidates known. Any further improvements after the 1 month period are too late and are ignored.

This would seem to be fair, in that candidates are able to use their own optimisation procedures to propose sets of candidates and there is a deterministic procedure to decide if the new proposal is better than the previous one. The initial randomised algorithms are quite good.

Another possible solution is to use a deterministic approximation algorithm, and to accept its result even if it is sub-optimal.

An simple greedy algorithm inspired by the forward/backward algorithm for machine learning feature selection and the Single Transferrable Vote proportional representation voting system is the following:

1 Start with all columns of A in C. 2 As long as their are more than k columns in C, repeat: 1 Initialise the best error to infinity 2 For each column remaining in C: 1 Remove the column from C 2 Find the optimal X for the current C 3 If the error is less than the best error then remember which column was removed 4 Return the column to C 3 For each column already removed from C: 1 Add the column to C 2 Find the optimal X for the current C 3 If the error is less than the best error then remember which column was added 4 Remove the column from C again 4 Add or remove the column that gave the best error for this iteration

The Single Transferable Vote algorithm repeatedly removes the candidate with the fewest votes until only k candidates remain. In the algorithm given above we perform local search, both removing candidates and adding back candidates that had previously been removed.

This algorithm assumes that we can find the optimal X for a given set of columns. I haven't verified that this is practical. If it isn't then you could choose a deterministic optimisation algorithm and use it, or you could revert to the randomised procedure above.

Being a greedy search, we have no guarantee that this algorithm will produce an optimal column selection. It is deterministic however, which politically useful in a voting system.

Which Norm?

In the column subset selection problem above, we have a norm applied to the error matrix to get an error value. In most CSSP literature the L2 or Frobenius norms are used. It is not clear if the L1 norm might be more appropriate.

Norms that seem to make sense:

  • L-infinity: Maximum absolute row sum of the error matrix
  • L-1: Maximum absolute column sum of the error matrix
  • L-2: This spectral norm is the largest singular value of the error matrix
  • Frobenius: Entrywise sum-squared error
  • Entrywise L-1: Sum of entrywise absolute error matrix

and their 'political' interpretation:

  • L-infinity: Optimise for the least fairly treated voter (and ignore other voters)
  • L-1: Optimise the candidate who is treated least fairly (and ignore other candidates)
  • L-2: If we could add one new candidate to the set to please voters, what would their sum-squared vote be? This will have an effect somewhere between the L-1 and L-infinity norms. Note that because we'd be minimising their sum-squared vote, we'd be trying to make sure that every voter is slightly unhappy rather than just making one voter unhappy and the others content.
  • Frobenius and L-1: These entrywise norms try to fit every preference by every voter about every candidate equally. The L-2 norm puts more weight on fitting the preferences that are far from correct, choosing many small errors over one large error. The L-1 norm puts equal weight on all preferences, tending to reduce small errors to zero rather than prioritising large errors.

I tend towards the L-2/spectral norm.

Posted mid-morning Sunday, January 13th, 2013

Multiple Winner Voting Systems

I've been thinking a bit about multiple winner voting systems lately. In particular I'm a fan of Range Voting and its simplified form Approval Voting. But those forms of voting are designed for single-winner eletions. I've been thinking about way to extent these 'rating based' voting systems to multiple-winner elections.

There are two types of multple-winner elections that I've considered, each in its own sub-post. The first is a simple multiple winner election where you have to elect a committee, there are n posts on the committee, and you need to choose them. I discuss this type in SimpleMultipleWinner. The second type is a proportional representation system. In a simple multiple-winner election you're willing to accept 'tyranny of the majority', whereas in a proportial representation system the winners should represent the range of views of the electors. I discuss this type of election in ProportionalRepresentation.

Posted mid-morning Sunday, January 13th, 2013

A Simple Multiple-Winner Rating Based Voting System

Range Voting is a single winner, rating based voting system that manages to avoid the issues presented by Arrows Theorem. Rather than ranking candidates, Range Voting requires each elector to rate the candidates on some fixed numerical scale. The candidate with the highest average rating wins the election. This system has been well studied, and works very well for single winner elections - better than other voting systems. Unfortunately, the original paper that introduced range voting only discussed single-winner elections. I'd like to consider multiple-winner elections.

Unfortunatly, there isn't a single type of multiple-winner election. In this post I discuss multiple-winner elections where 'tyranny of the majority' is acceptable.

The basic approach I use is to convert the multiple-winner election back into a single-winner election. Consider a multiple winner election with a set of candidates M = {C1, C2, ..., Cn}, where k winners are to be selected. We will consider a set S of n choose k 'candidate committees'. e.g. S = {{C1, C2, ..., Ck}, {C2, C3, ... Ck+1}, ... }. We can now conduct a single-winner election over S to choose the winning set of committee.

This approach inherits all the nice properties of the underlying single-winner voting system.

While this approach is theoretically sound, it has some practical issues. The most pressing issue is the size of S, which grows dramatically as M and k increase. This makes rating all the elements of S practically difficult. So for this voting system to work, we need a way to represent a 'vote' over S (i.e. a rating for each of the elements of S, or equivalently a function V: S -> Re) that has the following properties:

  • The vote must be compact in the common case
  • The vote language must be symmetrical in elements of M - there must be no bias towards any individual candidate in M (Note that the simple fact that we're looking to compress some votes means that other votes must be longer - we will be penalising certain types of votes by making them harder to represent. This means that the voting system will introduce a bias over the elements of S. This is considered acceptable as long as there is no bias over the elements of M.)
  • It must be trivial to check that a vote is valid (that it rates all elements of S, and that each rating is in the valid range)
  • It must be possible to represent any valid vote

Note that I propose to allow votes that rate invalid committees, e.g. a committee with only one member. These are OK - they can be excluded during the tallying of the votes. When checking if a vote is valid it is only neccessary to check that it rates each element of S, and that every rating is in the valid range.

The insight I propose to use to compress votes is to note that the average of a set of valid voting functions (functions S -> Re) is also a valid voting function. We'll then borrow from the Graphical model community and 'factorise' our vote. In particular, we can imagine a 'simple vote' is a vote that only considers some elements of the committee; e.g. if C1 is in s then 0.1 else 0.2. A valid 'simple vote' is also a valid vote - it rates all elements of S, it just gives many of them the same rating.

Each 'simple vote' could then be represented in a number of ways. The simplest would be to make each simple vote a table. The table would be exponential in size with the number of elements of M considered, but we expect that to be small in most cases. It is easy to check if a simple vote is valid - simply check that all entries in the table are in the valid range.

Another approach to represent simple votes compactly borrows from Edge-Valued Decision Diagrams (EVDDs). To satisfy the desiderata above, I would use unordered EVDDs, which lose some of standard EVDDs nice computational properties, but would be unbiased. An EVDD is a directed acyclic graph with one root and one leaf. The internal nodes are labelled with elements of M, and each has two outgoing edges. The edges each have a real valued label and a categorical label, included or excluded. Each internal node has one 'included' outgoing edge and one 'excluded' outgoing edge. To find the rating for a given element s of S, start at the root and follow the diagram to the leaf making choices about which outgoing edge to follow based upon whether the element m of M that labels a given node is included or excluded in s.

Checking whether such an EVDD is valid is efficient. Simply recurse over the EVDD considering nodes in topoligical order from the leaf to the root. At each node the minimum and maximum values of the function reachable from that node are calculated, using the min and max values of the children. (Note, this procedure is pessimistic if there are paths that can reach nodes labelled with the same element of M. Such paths are not allowed in standard, ordered, EVDDs, but I have allowed them here to make sure there is no bias among the elements of M.)

We can now check if the desiderata above are satisfied. I expect that in the common case there are few interactions between elements of M. This makes each 'simple vote' simple. For example, a set of simple votes that individually rated the elements of M would, I expect, be a common voting strategy. This is an extremely compact vote - it is essentially identical to a vote for a single-winner election with the same set of candidates.

The language is obviously symmetrical in the elements of M. Standard EVDDs were modified to make this even more obvious. We have discussed above the validity of votes. Finally, in the general case, a tree is an instance of an EVDD, so an arbirary vote could be represented by a single 'simple vote' - any vote is possible.

There is one more practicality to consider; we need to discuss counting the vote. The first step would be to make all the simple votes absolute. Each simple vote has its value divided by the number of simple votes in that elector's vote. We now tally the corrected simple votes directly.

Consider a vote consisting of j simple votes. For table based simple votes we make the simple vote absolute by dividing each entry in the table by j. For EVDD simple votes, we make the vote absolute by dividing each edge label by j.

The next thing I'd do is convert all the absolute simple votes into ordered EVDDs. An ordered EVDD is an EVDD with the additional constraint that along any path from the root to the labels of the nodes on the path are always in the same order. Converting a table into an ordered EVDD is a standard EVDD operation - go read the literature. Similarly, it is possible to re-order the nodes in an EVDD using standard operations to turn an un-ordered EVDD into an ordered EVDD.

Once all the absolute simple votes are represented as ordered EVDDs, their summation is a standard operation on ordered EVDDs. An important property of this summation (related to the summation, not the representation as ordered EVDDs) is that it is commutative. This means that the summation can occur in any order, and that partial sums can themselves be added. Each voting station can sum their votes separately. These sums should be compactly represented as ordered EVDDs and so can be efficiently transmitted to a central site for the final tally.

Once a final ordered EVDD representing the total vote has been collected, a maximisation still needs to occur to determine the winner. The first part of this would be make sure that the maximum point of the function is a valid committee. This can be achieved by building an ordered EVDD which is 0 for valid committees and negative infinity elsewhere. (note that using a modified form of EVDD that can handle infinities might be useful here - see the literature for details.) This EVDD is then added to the tally. Finally the argmax of the EVDD is taken, pulling out the winners of the final vote.

Note that, as with range voting itself, ties are possible. They don't appear to me to be any more likely than with ordinary range voting however.

Other Ideas

Other representations could also be used for the simple votes. For example, the Affine Algebraic Decision Diagram might be effective. It is unclear if the extra expressive power is worth the complexity, and whether the numerical stability issues of that representation will arise with this application.

Addionally, one could implement 'above the line' voting schemes by allowing political parties to suggest 'simple votes'. Any convex combination of valid votes will also be a valid vote, so more complex combinations than just average could be allowed.

Posted mid-morning Sunday, January 13th, 2013

MythTV Update

I just updated my MythTV box from Karmic to Lucid. There were a few things that needed updating, and it became a little like pulling on a piece of thread - one thing lead to another until it became quite the saga. I thought I'd document things so that others don't have quite the same pain.

There were two big things that changed: I updated my data store filesystem from zfs to btrfs. I updated my lirc configuration to use the new devinput driver.

zfs to btrfs

My machine has one 64Gb SSD with the root filesystem (ext4), and two 1Tb HDDs. Under Karmic I was using zfs-fuse on the HDDs in a raid1 (mirrored) configuration. They were one big pool, but I then had a number of filesystems on that pool that I could mount in different places - e.g. /var/lib, /home, /srv, etc. I had to do this because zfs-fuse gets harder to use the earlier you try to load it. By just using it for sections of the directory structure that load relatively late it was possible to use it for large data stores, but still have it be relatively easy to use.

Under lucid, zfs-fuse is now in the ubuntu repository, rather than an extra ppa. This made me think that the setup was likely to keep working... unfortunately that wasn't the case. After the dist-upgrade I ended up with a problem whereby certain of my zfs filesystems didn't show up in a zfs list and didn't mount with a mount -a. Given that I knew the names of some of the filesystems, I could mount them, but I didn't remember the names of some of the snapshots, and I couldn't figure out how to list them... so I decided to move to btrfs.

I've been thinking about switching to btrfs for a while. Having something natively supported in the kernel is likely to be faster, and I suspect the support on linux will be better. The question is then how to move from a raid1 zfs setup to a raid1 btrfs setup. Given that they're both raid1, you'd think it would be easy. Unfortunately, btrfs cannot currently add a second disk in a raid1 configuration after the filesystem creation - you have to have two disks at creation time. So I used a loopback device backed by a sparse file as my second device...

btrfs raid1 array creation

The two drives we're talking about are /dev/sdb and /dev/sdc. I initially removed /dev/sdb from the zfs pool leaving the pool in degraded mode. Then I did the following to turn /dev/sdb into the start of the btrfs pool: (I was basing this on the btrfs information here: http://btrfs.wiki.kernel.org/index.php/Using_Btrfs_with_Multiple_Devices)

# get the size of the disk you want to move from (in 1k blocks)
cat /proc/partitions # look for /dev/sdb1
# create the large, sparse data file
dd if=/dev/zero of=large.img bs=1k count=1 seek=<size of disk in blocks>
# mount it on a loopback device
losetup /dev/loop0 large.img
# make the raid1 btrfs filesystem
mkfs.btrfs -m raid1 -d raid1 /dev/sdb1 /dev/loop0
# mount the filesystem once
mount -t btrfs /dev/sdb1 btrfs-mnt
# if that didn't work, try mounting it using /dev/loop0
# then unmount it again
umount btrfs-mnt
# undo the loopback setup
losetup -d /dev/loop0
# remove the sparse file
rm large.img
# mount the drive again in degraded mode
mount -t btrfs -odegraded /dev/sdb1 btrfs-mnt

# make btrfs subvolumes and copy stuff onto the drive
cp -rp stuff btrfs-mnt/

# unmount zfs
# use gparted to re-partition /dev/sdc into one big partition

then I tried the following, which didn't work:

btrfs-vol -a /dev/sdc1 btrfs-mnt
btrfs-vol -r missing btrfs-mnt
# remount btrfs volumes in the right places and not in degraded mode

This began a saga trying to make btrfs to work as a raid1 system. Luckily, all my data was there and accessible on /dev/sdb1 in degraded mode (although I had a few heart-stopping moments - this procedure is for the brave at the moment).

The solution ended up being to update to a newer version of btrfs :). Lucid runs kernel 2.6.32 which was just as btrfs became at all usable, and it still appears to have some issues. I wanted to update to at least 2.6.34 and preferably newer.

There are two parts to btrfs - the kernel and the tools. I updated the tools by downloading the latest source package (for Natty) for btrfs-tools from https://launchpad.net/ubuntu/+source/btrfs-tools and building it locally on Lucid. It built just fine.

I also updated to a backported natty kernel. I added the ubuntu kernel ppa from https://launchpad.net/~kernel-ppa/+archive/ppa and then installed the linux-image-generic-lts-backport-natty package and associated headers.

Once these updates were done I was able, with only a little bit of playing, to get /dev/sdc1 added to the btrfs pool using the new style btrfs commands.

Remember to re-balance after adding the new drive to copy all the data across both.

There is still a weird issue removing the 'missing' devices - I don't get an error, but the 'missing' devices are still flagged as 'missing':

root@willvo:~# btrfs filesystem show
failed to read /dev/sr0
Label: none  uuid: f929c413-01c8-443f-b4f2-86f36702f519
    Total devices 3 FS bytes used 578.39GB
    devid    1 size 931.51GB used 604.00GB path /dev/sdb1
    devid    2 size 931.51GB used 604.00GB path /dev/sdc1
    *** Some devices missing

Btrfs Btrfs v0.19
root@willvo:~# btrfs device delete missing /data
root@willvo:~# btrfs filesystem show
failed to read /dev/sr0
Label: none  uuid: f929c413-01c8-443f-b4f2-86f36702f519
    Total devices 3 FS bytes used 578.39GB
    devid    1 size 931.51GB used 604.00GB path /dev/sdb1
    devid    2 size 931.51GB used 604.00GB path /dev/sdc1
    *** Some devices missing

Btrfs Btrfs v0.19

But it seems to be working anyway, so we'll leave that for the moment and move to the other issue. The new kernel doesn't just change the way btrfs works - it also changes the IR drivers. That means an update to the lirc configuration.

Updating lirc

The backstory for this update is covered here, http://wilsonet.com/?page_id=95, but the short story is that the drivers have changed and you need to switch to using devinput.

I have an Antec Veris system with a imon IR receiver and an Antec_Veris_RM200 remote. I don't actually use that remote though - it has too many keys and that just invites people to either a) complain it is too complex, b) press the keys and complain they don't do anything or c) both of the previous. Rather I use a LogiTech Harmony 525 programmable remote.

When I first set up my system, Logitech's auto-setup system didn't know about the RM200 remote - I had to use their learning system to program the Harmony. This worked ok, but I was never quite satisfied with it. When I set things up this time I figured out that with the new drivers I can switch the receiver into 'rc-6' mode which allows it to understand Microsoft Media Centre remotes. This is great as Logitech certainly does know about them. I followed this guide to set up my remote to act as a media-centre remote. I found there were a few buttons that my system couldn't interpret, so I had to switch some around - that wasn't a problem as there are plenty of options to choose from and most work just fine (but see below). One other caveat is that I couldn't get any of the 'Microsoft Keyboard' buttons to work reliably, just the remote buttons.

The setup on the linux side is a little more tricky. I found this thread useful, but did not follow it exactly.

Firstly, you need the ir-keytable tool, which I had to build from source.

git clone http://linuxtv.org/git/v4l-utils.git
cd v4l-utils
make
cd utils/keytable
cp ir-keytable /usr/local/bin/
cp rc_keymaps /etc/

Then when you run it, it will tell you the device to use for your remote:

# ir-keytable
Found /sys/class/rc/rc0/ (/dev/input/event4) with:
    Driver imon, table rc-imon-pad
    Supported protocols: RC-6   Enabled protocols: 

But we don't want to use /dev/input/event4 directly as that may change when you connect or disconnect another input device. Rather, use ls -l /dev/input/by-id/ to see which device there points to the right device. In my case I want to use /dev/input/by-id/usb-15c2_0038-event-mouse because that points to /dev/input/event4, but will keep pointing to the right device even if it changes.

Now, switch your lirc configuration to using devinput:

sudo dpkg-reconfigure lirc

and then select

Linux input layer (/dev/input/eventX)

I selected None for the IR Transmitter, and then /dev/input/by-id/usb-15c2_0038-event-mouse for the device.

Next, we need to tell HAL not to grab the device. Following the advice here I looked in /usr/share/hal/fdi/preprobe/20thirdparty/ and noticed there was already a lirc.fdi file. I edited it to add the following:

 <match key="info.product" contains_ncase="iMON Remote">
    <merge key="info.ignore" type="bool">true</merge>
 </match>

Next, we need to switch the remote into rc-6 mode and update its keymap. This can be done using the ir-keytable command we built earlier. For example:

ir-keytable -c -w /etc/rc_keymaps/imon_mce

should do both. I had some problems with that however and played around with a few things. I'm not exactly sure which of these fixed the problems.

  • At the top of the keymap, you'll notice it has a type: RC6. If you feed that to ir-keytable -p, then you sometimes seem to get an error. I think this should be RC-6.
  • Secondly, a bunch of keys didn't work. In the end I made my own keymap file, imon_will, with the type changed to RC-6, all the keycodes from imon_mce and all the keycodes from rc6_mce
  • Then you need to make sure the new keymap is loaded. I did this with brute force: I added the line /usr/local/bin/ir-keytable -c -w /etc/rc_keymaps/imon_will to /etc/init.d/lirc

And even that isn't enough to make the whole system work. I still found that lirc wasn't getting some keys. So I copied /usr/share/lirc/remotes/devinput/lircd.conf.devinput to /etc/lirc/lircd.conf.devinput and edited it as follows (basically adding 0x200 to some of the event codes - not sure why they need this):

--- /usr/share/lirc/remotes/devinput/lircd.conf.devinput    2009-02-08 05:00:41.000000000 +1100
+++ /etc/lirc/lircd.conf.devinput   2010-10-30 00:45:19.529971238 +1100
@@ -11,20 +11,21 @@
   pre_data_bits   16
   pre_data       0x8001
   gap          132799
+#  gap          39995
   toggle_bit_mask 0x0

       begin codes
-          KEY_0                    0x000B
           KEY_102ND                0x0056
-          KEY_1                    0x0002
-          KEY_2                    0x0003
-          KEY_3                    0x0004
-          KEY_4                    0x0005
-          KEY_5                    0x0006
-          KEY_6                    0x0007
-          KEY_7                    0x0008
-          KEY_8                    0x0009
-          KEY_9                    0x000A
+          KEY_0                    0x0200
+          KEY_1                    0x0201
+          KEY_2                    0x0202
+          KEY_3                    0x0203
+          KEY_4                    0x0204
+          KEY_5                    0x0205
+          KEY_6                    0x0206
+          KEY_7                    0x0207
+          KEY_8                    0x0208
+          KEY_9                    0x0209
           KEY_A                    0x001E
           KEY_AB                   0x0196
           KEY_AGAIN                0x0081
@@ -191,7 +192,8 @@
           KEY_KP7                  0x0047
           KEY_KP8                  0x0048
           KEY_KP9                  0x0049
-          KEY_KPASTERISK           0x0037
+#          KEY_KPASTERISK           0x0037
+          KEY_KPASTERISK           0x020A
           KEY_KPCOMMA              0x0079
           KEY_KPDOT                0x0053
           KEY_KPENTER              0x0060
@@ -200,7 +202,8 @@
           KEY_KPLEFTPAREN          0x00B3
           KEY_KPMINUS              0x004A
           KEY_KPPLUS               0x004E
-          KEY_KPPLUSMINUS          0x0076
+#          KEY_KPPLUSMINUS          0x0076
+          KEY_KPPLUSMINUS          0x020B
           KEY_KPRIGHTPAREN         0x00B4
           KEY_KPSLASH              0x0062
           KEY_L                    0x0026

Having made those changes you still need to tell lirc to use them, so edit /etc/lirc/lircd.conf to include /etc/lirc/lircd.conf.devinput instead of the default (for devinput) /usr/share/lirc/remotes/devinput/lircd.conf.devinput.

At this point your remote should work.

Lirc and gdm

There is one other tweak I made. I still use gdm on my system rather than booting directly into mythtv. I have the mythtv user set up to auto-login after 10 seconds. Before Karmic, this used to wait 10 seconds and then start mythtv every time. On Karmic and now Lucid, this only auto-login only works on the initial boot. If you exit myth then it will not re-auto-login. As I have no easily accessible keyboard, this is somewhat annoying.

I just added some extra irexec commands that run on KEY_UP, KEY_DOWN and KEY_OK events. These check if the 'mythtv' user is logged in, and if not then they use xdotool to generate approprate keyboard events. This allows you to use the remote to select the myth user. On Lucid you can then add that user to the nopasswdlogin group so that they don't need a password to login on the console (you want to make sure your remote access is still secure!), and people can now restart the myth frontend effectively with just the remote.

Posted late Saturday afternoon, October 30th, 2010

Android Lock Screen API Design

I want a better lock screen on my Android phone.

Moreover, I don't really want Google or HTC to design one. I really want a good API that allows others to design one. This is much the same design concept behind intents, widgets, etc; build the framework right, rather than building one particular implementation.

Which brings up the question: What would be a good lock screen framework for android?

Background

I made a previous Lock Screen Rundown. Since then I've also come across:

  • WidgetLocker: A standard apk that replaces the lock screen. This allows widgets to be placed on the lock screen.
  • AVLock: This patch requires root. It replaces the default home screen directly, and hence has none of the issues that others have been having with the current API.

It is also important when thinking about this to know what Google has said about the current API.

Desiderata

  • Security
    • Phone security
    • It shouldn't be possible for an 'app widget' added to a lock screen to grant access to the phone when the phone is 'secure'.
    • Not a trojan
    • No Denial of Service (intentional or otherwise)
  • Flexibility
    • Able to replicate the default lock screen on any commercial hardware (e.g. Eclair, Sense, etc.)
    • Able to replicate the 'lock screen replacement' apps currently on the market. (This is less important than the previous.)
    • Able to adjust what (hardware buttons/shaking/???) wakes the device (but see security/DoS)

Use Cases

There appear to be two classes of use cases for the lock screen: standard and secure. By secure I'm referring to the 'pattern lock' that tries to keep prying eyes out of the phone.

  • A simple lock screen that displays the time and has a keylock so you don't pocket-dial.
  • A more complex lock screen that displays some simple information and also allows basic interaction (e.g. control the music playback). Has a keylock so you don't pocket-dial.
  • A very detailed lock screen with lots of information and interaction, like FlyScreen.
  • A simple secure lock screen designed to stop someone briefly alone with the phone from accessing it. The lock function doubles as a keylock to stop pocket-dialing.
  • A secure lock screen that displays some information. e.g. transparently overlay the pattern lock on top of something like Pure Calendar.
  • A secure lock screen that displays information and has some very basic interaction (e.g. a play/pause button)
  • A complex secure lock screen that has multiple 'pages', some of which you can interact with. There is a mechanism to 'unlock' the

Design Ideas

I'm going to start with phone security ideas. The 'unlock' swipe pattern, either simple for a keylock, or complex for something more secure, is going to be an important part of the configurability of the lock screen. This means that it needs to be configurable too. BUT, it also has stronger security requirements. Hence my initial plan would be to separate these: have a plugable 'lock' widget and a separate pluggable information screen. The information app can be complex. The lock widget is significantly more tightly constrained.

Information screen

I'd imagine that the information screen is like a home screen. It can do whatever it likes, but all intents sent from this screen are ignored. There are two ways that this app can be dismissed:

  • If the menu button is held down for 5 seconds then you're taken to a built-in back door that lets you in if you succeed at Google verification. This stops DOS attacks, intentional or otherwise.
  • The lock swipe is implemented using (something like) the widget API. That widget has access to the API that dismisses the lock screen.

This ends up looking much like the current lock-screen apps, but cannot exit itself. If it does exit it could be restarted, or their could be a fallback.s

Lock Widget

As noted above, the lock widget is significantly constrained.

  • When the lock widget is displayed, it is carefully drawn in its own window on top of the information screen. It can be transparent, showing the information screen behind, but no events in the lock screen pass through the information screen app. This stops password 'sniffing'.
  • The lock widget's pixel values should never be visible to other user code.
  • The lock widget's apk should never have any permissions (except reading from the sd-card?). (The idea here is that the plugin can get information from outside, but it cannot send any information anywhere. It can only get information from outside in ways that don't leak information, so net access is forbidden as information could be encoded in the URL accessed.)
  • The lock plugins should never be able to broadcast or call any intents.
  • The currently designated lock plugin (and the menu-key override) are the only ways to dismiss the lock screen.

  • If the user specified a lock widget that just automatically dismissed the lock screen, then it is possible to pass control of unlocking back to the information screen.

Implementation Issues

  • How do you make sure the information screen is sufficiently locked down? I think this could be similar to the current behaviour.
  • How do you make sure that events for the lock widget cannot be captured by anyone else? This seems relevant. I don't know how that relates to widget embeddings. Is it possible to make a widget that keeps its events and pixels private?
Posted Sunday night, July 18th, 2010

I'm looking for a good android lock screen.

Desiderata

  • Lock screen with some form of security - e.g. pattern lock
    • What I'd really like here is a pattern lock that does NOT require me to swipe, then swipe again for the pattern.
  • Lock screen can show me my calendar agenda
  • Lock screen can show me the time
  • Lock screen can do other lock-screen-esque things, like pause music, show new SMS's, missed calls, etc.
  • Lock screen should include 'if found please call' information.
  • Lock screen should include 'emergency dial' capability (but protected somehow so I don't pocket-dial).

Options

  • Executive Assistant is a well implemented app that does most of what I want.
  • myLock is looks like it is heading the right direction. Not sure it does everything I want yet, but is pretty close, and is open source so I might be able to make it do exactly what I want.

Previous attempts

I had a rooted HTC Hero rom installed previously. With that ROM I was able to make the lock screen transparent and put all the widgets I wanted on the home screen. I then used HomeSeek to make sure that the main home screen was showing behind the lock screen. This was good in that it showed my what I wanted without losing any of the standard Hero lock-screen functionality. It wasn't perfect however it in that it still required a double-unlock; I had to swipe down and then do the pattern unlock.

Current Thoughts

If I had freedom to design my own lock screen, I'd take myLock, and use the 'widget embedding' version. Embedding widgets allows me to get most of the other functionality without having to put it in the lockscreen app itself. I'd then use the android gestures API and put a GestureOverlayView over the top. The lock screen would unlock when the user enters the correct gesture.

This gives me more flexibility with the unlock gesture. It means that I don't have to swipe to get the 'pattern lock' screen - the front screen is the gesture lock screen.

Posted late Monday evening, May 31st, 2010

Hi all,

I recently rooted my HTC Hero. I was a little disappointed to find out how insecure the result is. There is a sudo-like app called superuser that behaves as a basic gate-keeper. Any other app that wants something done as root asks the superuser app to do it. The superuser app checks its list of allowed apps, and if the app isn't listed then the user is asked.

The problem is that there is no password. This means that if you have a rooted phone, anyone who plays with your phone can quickly get a root shell (go to one of your shell apps, su and click 'allow', then you have a root shell). They can then use the installed sqlite3 app to, for example, get your Google password.

Ugh.

The MoDaCo Hero 3.1 rom also makes the usb shell (accessed through adb shell) default to a root shell.

Now, it is clear that if someone has physical access to your device then they have your data. Even if you have a stock phone, they could root it and then go looking through your data. But in this case the attack goes from rooting the phone (which requires multiple reboots, takes at least 10 minutes, and leaves an obvious trace) to running a few shell commands (limited more by typing speed than anything else).

Anyway, as mitigation I decided to enable the pattern based lock screen. But that is annoying. I use widgets on my home screen to get information regularly, and constantly entering the pattern is slow. (It is also not wonderfully secure, in that your finger leaves greasy trails on the screen and they show up fairly clearly if you hold the phone at the right angle in the light.)

I spent a while looking for a lock screen replacement app that allowed me to place widgets on the lock screen. I couldn't find one that I liked. The two best were Flyscreen and Executive Assistant, but neither of them was perfect.

I then stumbled across the fact that the default HTC Lockscreen can be made transparent. A standard HTC phone allows you to personalise the lock screen wallpaper. By default it saves a jpeg file to use as the lockscreen in /data/misc/lockscreen/lock_screen_port (note that the trailing .jpg is not there). Luckily, the app can use more than just jpegs. If you put a png file there, the lock screen will happily use it, and png files have an alpha channel - transparency. You can have anything from a totally clear lock screen to a 50% dimmed lock screen, or anything else.

My new lock screen image is completely transparent except for a brief "If found please contact" message. This means that when the phone awakens, I can see the last used screen behind the lock screen. As long as I hit 'home' before I switch off my device, I get my standard home screen, with its useful widgets showing right through my lock screen. I also get all the normal HTC additions like Music controls on the lock screen, etc. When I touch the screen and start dragging down to unlock, the patten unlock view immediately appears.

Thanks to the xda developers for pointing me in the initial direction for this (they recommended deleting the /system/etc/lockscreen/port directory to get a completely transparent lock screen). It was starting from that approach (which requires modifying your system image), that I discovered the lock_screen_port file above that is accessible without modifying your system image (although it might still require root permissions to modify).

Posted Sunday night, January 17th, 2010

I've been wanting to get a street map on my phone that doesn't require a net connection. I have 16Gb of sdcard - I'm happy to use it for maps. It also seems a shame to pay for map data when OpenStreetMap does such a good job. Or rather, if I'm going to pay someone, I'd pay them for the service of updating the OSM data. I wouldn't subscribe to streetmap data.

But, there is no Android app out there that scratches all my itches yet. As I noted last week, the Android content provider concept should allow the separation of the data store from the display and allow the data to be used for different things. This seems like a nice idea. Exactly what those provider interfaces should be is a more interesting question. Before we get to that, let's review the current OpenStreetMap offerings for Android.

Current Apps

There is a list of Android OSM apps on the OSM wiki. I've now tried a bunch of them, and here are my current thoughts (at time of writing - this will get old fast I suspect).

MapDroyd is a vector map viewer on Android. It is commercial. It uses a proprietary map format which 'Breaks "sonic barrier" of loss-free street map compression' by using lossy compression. MapDroyd displays quite quickly. The problem with this is that their maps appear to be poor quality. I've discovered problems with them in the region near my house - problems that don't appear in the OpenStreetMap data.

Navit on Android is a port of the Navit project. Navit works, but the port I tried was extremely SLOW on my Hero. This was a 2D map display. I understand that Navit uses its own C++ renderer under the hood.

osmdroid is the grandaddy of OSM apps for Android. It uses 2d tiles, downloaded from the web - the same as the OSM slippy map. These map tiles are cached on your android device, but the default cache is small. It appears fairly easy to modify this app to read from a tile cache on the sd-card.

osm-android is an open source vector map viewer. It is SLOW, even though it uses its own binary format. It is both slow to convert an OSM XML file into its format, and slow when in use on the phone. It was in looking to speed this app up that I reached most of the conclusions below.

Design Discussion

Lets break the discussion into two parts: map display and route finding.

Map Display

Looking at the OSM-Android code, I noticed a few things. It uses the fairly standard 'tile' concept to index its data. The tiles are stored at variable resolution. The slow performance appears to be because there is not enough approximation in the data - figuring out what to display takes time because the data contains more information than is needed for the display. (Note - this is talking about display speed. Conversion speed is slow because OSMAndroidConverter loads the entire .osm file it is converting into ram, and this runs out of ram and swaps badly.)

So then I started looking at inventing a variable resolution data structure for the map data that would only contain relevant data at any level. It would smoothly drop out detail as you zoomed out. It would also drop out detail from the edges of regions when you're in the centre of them.

For example, imagine you're displaying a small town in central Australia. You need to know that you're in the middle of Australia, and hence use the appropriate background colour, but you don't need to know the exact shape of the coast near Sydney.

I came up with a data structure to do this. To make things efficient, there was a bunch of processing that I was offloading to the format converter. But as I offloaded more and more, it started looking very much like a vector graphics format (not exactly, but there were similarities). If I'm going to store vector graphics, why not jump straight to SVG and use Mapnik to do the rendering? I'd get much nicer looking maps.

Furthermore, once you've jumped to using an image format, why bother staying with a vector format - whether you use a vector or a raster format depends on storage size, and for very pretty maps I could easily imagine the compressed raster format being smaller.

The big loss with jumping to an image format is that the maps no longer rotate nicely. In particular, text and some icons should be written the correct way up. But text and icons are usually the top/last layer of any rendering process. One could store multiple tile-sets. One of base map that can be rotated, and then four more with labels printed at the four compass directions. The labels would compress very well as those images would be mostly transparent. The result would be names and icons that are never more than 45 degrees out.

Even if you were doing 2.5d maps, this pre-rendering approach should still work well - treat the map tiles as textures for OpenGL. Again, the text and icons are the bits you might want to add later.

Choices

If I was to decide on a solution today, I'd go with cached image tiles. Having said that, there is no reason why the map tiles couldn't be generated on the phone if that is really needed, although a pre-generated set would probably work just fine. You could use osmdroid to display the map, have a map cache on the sdcard, and also have a map tile provider that generates map tiles which are not in the cache from streetmap data. Locally generated tiles would take longer to display, but you don't often need to display the map for a completely new area.

Route finding

The issue with using an image format for map display is that you can't use the same data for route finding. On the other hand, it frees you from having to use the same format for both - a separate data-structure can be used for storing the map that you route-find over. I haven't given this as much thought.

Posted Monday afternoon, October 12th, 2009 Tags:

Having listed the Android Apps I currently have installed on my phone in my blog post from last night, I'd now like to list the things that are missing from my android phone.

Mapping and Localisation

The first thing that is missing is a decent turn-by-turn navigation app. I'm looking closely at CoPilot Live, but they don't seem to be releasing Australian maps yet.

I'd want something that runs offline. It would be great if I could get something that works with the OpenStreetMap data. There are a number of people working on this, some listed on the OpenStreetMap Wiki. Unfortunately none of them are quite there yet.

If I was designing an application of this sort, I'd split it up so that different apps supplied different bits of functionality. This would allow the functionality to be used by different parts of the system and hopefully increase the rate of development of all the apps.

Vector Map Data

I'd like an app that supplies information about the local streets to other apps. I imagine an assistant app with an API published on Open Intents. This can then be used to display a picture of those streets, to plan a path, or anything else.

The app would take a level of resolution and a location and return a 'tile' of data that includes the point supplied. There would also need to be APIs to get neighbouring tiles of data.

I imagine that the standard implementation would read OpenStreetMap data from the sdcard. A more advanced version could incrementally download the OSM data from the OSM web-site.

It might be good to define APIs for things like traffic data too so that these could be added later where they're available.

Filtering

I'd like to have an App that uses the vector data supplied by the program above and the Location Provider android API. It should take the provided location as an observation for a multi-hypothesis bayesian filter. Each hypothesis is constrained to be on a nearby road. See this paper for the ideas.

The overall goal of this filter is to help fix the poor localisation I get with plain GPS on my Hero. In many situations it is great, but sometimes it can return a position blocks away from my actual location. This is unhelpful for a Turn-By-Turn directions system. Moreover, it doesn't always seem to correct itself as I walk around.

The aim of this filtering system is to combine knowledge of the road network with knowledge of the GPS position to improve the accuracy of the localisation. If I turn a corner, then any of the hypotheses on a road that doesn't have a corner should be ruled out. In this way the system should converge on a good position estimate even if the GPS unit is being confused by buildings or power lines.

Having tracked the location, this app should then provide it again using the Location Provider API so it can be used by any other app.

Offline WiFi location

It would be nice to be able to localise without either the GPS unit (which uses a fair amount of power) or network access. This could be combined with the Locale app to have low-power location-aware switching of phone state.

A simple app that allowed you to specify particular WiFi Base station MAC addresses and their locations, and which then provided those locations using the Location Provider API with large range, would solve this problem.

This is similar to SkyHook Wireless or Google maps, but keeps a small number of MAC addresses for offline location detection.

Indoor mapping

You could do this to localise indoors. Not sure this is worth the effort over the simple approach above.

Map Display

It would be good to have something that can take vector maps from the map supplier above and produce a nice map for display on the phone. Something like MapDroyd or OSM Android.

It would be great if it could also do 2.5D maps, and allow overlays. It should also respond to the same set of intents as OSMDroid and Google Maps, so it neatly replaces the standard maps.

Contour maps

It would be nice to be able to overlay contour maps. Some Australian contour maps appear to be available.

Route Planning

It would be nice to implement a simple app that asks for a source and destination and then plans a route for that trip. In 'tracking' mode it should be repeatedly re-planning and alert the user when they need to turn around. It should be possible to layer the path on top of the Map Display above.

Turn By Turn Directions

With Route-Planning already implemented, adding turn directions is the final layer on the cake to replace something like CoPilot Live.

Timetables

Together with this tracking, it would be nice to detect when people are on a bus and display current locations of the busses in a city. If this worked well, then we wouldn't have to worry about the NSW STA locking down their data. We could just generate our own.

Locale Changes

The extra Location Providers above would already help Locale make sensible decisions. There are some extra features that could be good for it though.

Carry detector

Add another condition that looks at the g-sensor over time to detect if the phone is being carried or is sitting on a desk. I assume that people move enough that you could tell the difference between a phone is someone's pocket and a phone sitting on a desk, even if they're sitting quite still.

Renotification

It would be nice if Locale could be made to re-notify the user if there are any notifications active when the ringer is turned back on. e.g. If I get an SMS when in a meeting and so my phone doesn't beep, but then I leave the meeting, when Locale resets to the default ring volume it should beep to let me know an SMS had arrived.

Persistent Notify

Add a way to have the phone re-notify if there are active notifications. Should also have a Locale Plugin to switch it on and off.

Combined with the 'carry detector' described above and Locale this could be made to only repeat notifications when the phone is being carried.

Javascript Calculator

I use the Calculate widget on my Mac and really like it. I'd love to see a similar app on Android. It would need to have a nice calculator keypad with the option to bring up the standard ASCII virtual keyboard. I want something that includes these functions. There are other javascript calculators apart from the one above, e.g. Mochikit.

AusLan Dictionary

I'm currently learning Australian Sign Language (at TAFE). It would be nice to have a dictionary like SignBank on my phone. Perhaps a sign-english dictionary would also be possible (Using something like the system in this book).

MobileOTP

MobileOTP is a One Time Password system. It would be nice to have an android app rather than having to use the J2ME one.


A few more quick things I forgot to add this morning...

Sync

I want a contacts sync app for my mac that doesn't suck. Syncing the calendar through Google is OK, although I'd be just as happy not to give them all my data, but syncing my contacts through Google to MacOS address book just doesn't work well enough. I'm hoping that Missing Sync will fill this niche soon.

Things are quite close to working. Funambol have an android SyncML client for contacts. The problem is that Apple's core sync services don't speak SyncML. The iSync app translates their core sync service into SyncML, but it is based around the OBEX protocol for USB and Bluetooth, and the HTTP bearer isn't easy to get working. Either OBEX on the Hero, or HTTP on the Mac would complete the connection... for contacts at least. I think missing sync is probably a better option.

PPTP VPN

NICTA uses a VPN for its internal wireless network. While I get the reasons for this, it means I can't use my phone at work until I have a PPTP VPN. I need to either root my phone or wait for donut to be ported to the Hero.

Posted at teatime on Saturday, October 3rd, 2009 Tags: