Sensor net­works are all about uncer­tainty: if the sensor says it’s 20°C  out there, then it might be 20°C plus-or-minus half a degree or so (lim­ited pre­ci­sion); or it might be some dif­fer­ent tem­per­at­ure, and the sensor’s just repor­ted a duff value for some reason (lim­ited accur­acy). By con­trast, com­puters most def­in­itely aren’t about uncer­tainty, a fact enshrined in the fam­ous maxim “garbage in, garbage out”. What does this mean for our abil­ity to build really large, robust and flex­ible sensor networks?

All the really found­a­tional mod­els of com­put­ing — λ cal­cu­lus, Tur­ing machines and the like — pretty much reflect this notion that input is cor­rect in some sense, and if it’s wrong then that’s an error to be cor­rec­ted out­side the com­pu­ta­tional sys­tem. That seems to mean that the com­pu­ta­tional sys­tem can’t itself either tol­er­ate or express the notions of lim­ited cer­tainty — pre­ci­sion and accur­acy — that lie at the core of sensor net­works (and a lot of other mod­ern sys­tems, or course). That sug­gests to me that there might be a prob­lem at the heart of com­puter sci­ence as we cur­rently for­mu­late it: it isn’t a real­istic model of the world we’re try­ing to com­pute over.

In some ways this is nether sur­pris­ing nor threat­en­ing. Any math­em­at­ical or com­pu­ta­tional model is only a sim­pli­fied abstrac­tion of the real world, for which we have to make often stag­ger­ingly bold sim­pli­fic­a­tions if we’re to get any­where. We should how­ever always be pre­pared to chal­lenge the valid­ity and neces­sity of these sim­pli­fic­a­tions, and that’s what I’d like to do here.

As far as valid­ity is con­cerned, the sim­pli­fic­a­tion is quite pat­ently invalid when it comes to any sys­tem that oper­ates with real-world data: some of it is bound to be “wrong” in some sense. This isn’t the same as being tol­er­ant of mis­takes, such as when someone presses the delete key by mis­take: that’s a action that cer­tainly happened and to which the sys­tem respon­ded cor­rectly, albeit “wrongly” from the user’s per­spect­ive. Inter­est­ing prob­lem, but dif­fer­ent: we’re talk­ing here about respond­ing to inher­ently erro­neous input — the delete key seem­ing to press itself, if you like.

Neces­sity, then: is it neces­sary to handle com­pu­ta­tion in this way? Clearly not: we can eas­ily con­jec­ture a com­pu­ta­tional model that’s more tol­er­ant of input with lim­ited certainty.

Con­sider pre­ci­sion first. If the input is only known to a lim­ited pre­ci­sion, then we don’t want that error mar­gin to cause enorm­ous errors. If we have a func­tion , then we want to exhibit a tol­er­ance of impre­ci­sion such that for some scal­ing factor . doesn’t cause errors to blow-up in unpre­dict­able ways. A lot of func­tions behave in exactly this way: for example, in a sliding-window aver­age func­tion for an aver­age com­puted from recent obser­va­tions, we have that . Small errors there­fore per­turb the res­ult sig­ni­fic­antly less than the input is per­turbed. If the errors are uni­formly dis­trib­uted, the func­tion should con­verge on the “true” value.

Con­versely, a large, accur­ate new obser­va­tion will per­turb the aver­age only slowly, so large step-changes will be detec­ted only slowly. It’s hard to dis­tin­guish such a change when it first hap­pens from an inac­cur­ate read­ing. There are vari­ous ways of deal­ing with this, such as using a weighted slid­ing win­dow with non-linear weighting.

This is a rather topo­lo­gical idea. Rather than simply map­ping points in an input space (such as tem­per­at­ure) to an out­put space (aver­age tem­per­at­ure over the past few minutes), we’re also requir­ing that the map­ping take ele­ments close in the input space to ele­ments close in the res­ult space: we require that it be a con­trac­tion map­ping. Build­ing sys­tems from con­trac­tion map­pings, per­haps com­bined with contraction-preserving oper­at­ors, yields sys­tems that are robust to small errors in pre­ci­sion from their sensors.

Of course not all sys­tems are actu­ally like this, and in many cases we want rapid changes to be detec­ted quickly and/or propag­ated. The point, per­haps, is that this is a choice we should make rather than a con­sequence of choos­ing a par­tic­u­lar model of com­pu­ta­tion. There might actu­ally be a model of com­pu­ta­tion lurk­ing about here, in which we define func­tions coupled with a model of how their input and out­put errors should behave. At the very least, this yields sys­tems in which we can pre­dict the con­sequences of errors and impre­ci­sions, which is a major chal­lenge to deal with at present.

You can eas­ily share this post on any of the fol­low­ing social book­mark­ing sites: