These are my recent Pin​board​.in links:

• Nicholas Rombes: Punk | berfrois

  “Most iron­i­cally, being based in the hope­lessly lost cul­tural void of Ann Arbor, a noto­ri­ous mecca for the last sur­viv­ing rem­nants of the pseudo-​​intellectual street peo­ple move­ment that said much and accom­plished little…”
  
  punk history-​​is-​​a-​​feature-​​not-​​a-​​bug cultural-​​dynamics ha-​​ha-​​only-​​semiserious

• [1112.5309] POWERPLAY: Train­ing an Increas­ingly Gen­eral Prob­lem Solver by Con­tin­u­ally Search­ing for the Sim­plest Still Unsolv­able Problem

  An amus­ing col­lec­tion of what seem to be half-​​remembered ideas gleaned from his visit to the GPTP work­shop in Ann Arbor two years ago, pre­sented as his own inven­tions and with­out cita­tion or men­tion of the dozen peo­ple who actu­ally do this work. His keynote, as I remem­ber it, essen­tially revolved around him point­ing out how influ­en­tial his work should have been all along, if only we had both­ered to cite him as we should have done, because he thought up the core con­cepts of genetic pro­gram­ming well before any of us claimed we had. This is pretty much a camel’s-back straw for me. If there is a bet­ter argu­ment for com­pletely boy­cotting the cita­tion sys­tem and rely­ing on per­sonal asso­ci­a­tion and named schools rather than pub­li­ca­tion, I have not yet encoun­tered it. So remem­ber poor oppressed grad­u­ate and post­doc kids: when I cite your work by sim­ply nam­ing you per­son­ally, and not your advi­sor or your insti­tu­tion, and not even your pub­li­ca­tion or jour­nal but merely YOU PERSONALLY, it’s because you per­son­ally deserve the credit, not any of those other leeches. Got that?
  
  now-​​this-​​really-​​pisses-​​me-​​off-​​to-​​no-​​end

• [1203.0856] Online Dis­crim­i­na­tive Dic­tio­nary Learn­ing for Image Clas­si­fi­ca­tion Based on Block-​​Coordinate Descent Method

  “Pre­vi­ous researches have demon­strated that the frame­work of dic­tio­nary learn­ing with sparse cod­ing, in which sig­nals are decom­posed as lin­ear com­bi­na­tions of a few atoms of a learned dic­tio­nary, is well adept to recon­struc­tion issues. This frame­work has also been used for dis­crim­i­na­tion tasks such as image clas­si­fi­ca­tion. To achieve bet­ter per­for­mances of clas­si­fi­ca­tion, experts develop sev­eral meth­ods to learn a dis­crim­i­na­tive dic­tio­nary in a super­vised man­ner. How­ever, another issue is that when the data become extremely large in scale, these meth­ods will be no longer effec­tive as they are all batch-​​oriented approaches. For this rea­son, we pro­pose a novel online algo­rithm for dis­crim­i­na­tive dic­tio­nary learn­ing, dubbed textbf{ODDL} in this paper. First, we intro­duce a lin­ear clas­si­fier into the con­ven­tional dic­tio­nary learn­ing for­mu­la­tion and derive a dis­crim­i­na­tive dic­tio­nary learn­ing prob­lem. Then, we exploit an online algo­rithm to solve the derived prob­lem. Unlike the most exist­ing approaches which update dic­tio­nary and clas­si­fier alter­nately via iter­a­tively solv­ing sub-​​problems, our approach directly explores them jointly. Mean­while, it can largely shorten the run­time for train­ing and is also par­tic­u­larly suit­able for large-​​scale clas­si­fi­ca­tion issues. To eval­u­ate the per­for­mance of the pro­posed ODDL approach in image recog­ni­tion, we con­duct some exper­i­ments on three well-​​known bench­marks, and the exper­i­men­tal results demon­strate ODDL is fairly promis­ing for image clas­si­fi­ca­tion tasks.”
  
  image-​​analysis image-​​segmentation algo­rithms nudge-​​targets

• [1203.3271] The ther­mo­dy­nam­ics of prediction

  “A sys­tem respond­ing to a sto­chas­tic dri­ving sig­nal can be inter­preted as com­put­ing, by means of its dynam­ics, an (implicit) model of the envi­ron­men­tal vari­ables. The system’s state retains infor­ma­tion about past envi­ron­men­tal fluc­tu­a­tions, and a frac­tion of this infor­ma­tion is pre­dic­tive of future ones. The remain­ing non­pre­dic­tive infor­ma­tion reflects model com­plex­ity that does not improve pre­dic­tive power, and rep­re­sents the inef­fec­tive­ness of the model. We expose the fun­da­men­tal equiv­a­lence between this model inef­fi­ciency and ther­mo­dy­namic inef­fi­ciency, mea­sured by the energy dis­si­pated dur­ing the inter­ac­tion between sys­tem and envi­ron­ment. Our results hold arbi­trar­ily far from ther­mo­dy­namic equi­lib­rium and are applic­a­ble to a wide range of sys­tems, includ­ing bio­mol­e­c­u­lar machines. They high­light a pro­found con­nec­tion between the effec­tive use of infor­ma­tion and effi­cient ther­mo­dy­namic oper­a­tion: any sys­tem con­structed to keep mem­ory about its envi­ron­ment and to oper­ate ener­get­i­cally effi­ciently has to be predictive.”
  
  mod­el­ing philosophy-​​of-​​science information-​​theory physics ther­mo­dy­nam­ics talking-​​about-​​a-​​model-​​is-​​a-​​model pragmatism-it-ain’t

• [1203.3434] On the Impact of Infor­ma­tion Tech­nolo­gies on Soci­ety: an His­tor­i­cal Per­spec­tive through the Game of Chess

  “The game of chess as always been viewed as an iconic rep­re­sen­ta­tion of intel­lec­tual prowess. Since the very begin­ning of com­puter sci­ence, the chal­lenge of being able to pro­gram a com­puter capa­ble of play­ing chess and beat­ing humans has been alive and used both as a mark to mea­sure hardware/​software pro­gresses and as an ongo­ing pro­gram­ming chal­lenge lead­ing to numer­ous dis­cov­er­ies. In the early days of com­puter sci­ence it was a topic for spe­cial­ists. But as com­put­ers were democ­ra­tized, and the strength of chess engines began to increase, chess play­ers started to appro­pri­ate to them­selves these new tools. We show how these inter­ac­tions between the world of chess and infor­ma­tion tech­nolo­gies have been her­ald of broader social impacts of infor­ma­tion tech­nolo­gies. The game of chess, and more broadly the world of chess (chess play­ers, lit­er­a­ture, com­puter soft­wares and web­sites ded­i­cated to chess, etc.), turns out to be a sur­pris­ingly and par­tic­u­larly sharp indi­ca­tor of the changes induced in our every­day life by the infor­ma­tion tech­nolo­gies. More­over, in the same way that chess is a mod­eliza­tion of war that cap­tures the raw fea­tures of strate­gic think­ing, chess world can be seen as small soci­ety mak­ing the study of the infor­ma­tion tech­nolo­gies impact eas­ier to ana­lyze and to grasp.”
  
  touch­stones his­tory algo­rithms history-​​of-​​science computer-​​science

• Share Books | berfrois

  “Libraries are a recog­ni­tion that schol­ar­ship and cul­ture are more than the busi­ness of cre­at­ing and con­sum­ing. They are a human con­ver­sa­tion, and libraries pro­vide com­mon ground where that con­ver­sa­tion can take place and be remem­bered. By tak­ing aim at the right for the pub­lic to main­tain this con­ver­sa­tion and its mem­ory, pub­lish­ers have shown us what we have to lose. It’s time we resisted the out­sourc­ing of our com­mon her­itage by occu­py­ing the library.”
  
  Occupy libraries intellectual-​​property open-​​access public-​​policy activism

• [1112.3307] Poly­tope Codes Against Adver­saries in Networks

  “Net­work cod­ing is stud­ied when an adver­sary con­trols a sub­set of nodes in the net­work of lim­ited quan­tity but unknown loca­tion. This prob­lem is shown to be more dif­fi­cult than when the adver­sary con­trols a given num­ber of edges in the net­work, in that lin­ear codes are insuf­fi­cient. To solve the node prob­lem, the class of Poly­tope Codes is intro­duced. Poly­tope Codes are con­stant com­po­si­tion codes oper­at­ing over bounded poly­topes in inte­ger vec­tor fields. The poly­tope struc­ture cre­ates addi­tional com­plex­ity, but it induces prop­er­ties on mar­ginal dis­tri­b­u­tions of code vec­tors so that validi­ties of code­words can be checked by inter­nal nodes of the net­work. It is shown that Poly­tope Codes achieve a cut-​​set bound for a class of pla­nar net­works. It is also shown that this cut-​​set bound is not always tight, and a tighter bound is given for an exam­ple network.”
  
  cryp­tog­ra­phy pri­vacy algo­rithms nudge-​​targets network-​​theory com­mu­ni­ca­tion

• [1203.3353] Solv­ing Struc­ture with Sparse, Randomly-​​Oriented X-​​ray Data

  “Single-​​particle imag­ing exper­i­ments of bio­mol­e­cules at x-​​ray free-​​electron lasers (XFELs) require pro­cess­ing of hun­dreds of thou­sands (or more) of images that con­tain very few x-​​rays. Each low-​​flux image of the dif­frac­tion pat­tern is pro­duced by a sin­gle, ran­domly ori­ented par­ti­cle, such as a pro­tein. We demon­strate the fea­si­bil­ity of col­lect­ing data at these extremes, aver­ag­ing only 2.5 pho­tons per frame, where it seems doubt­ful there could be infor­ma­tion about the state of rota­tion, let alone the image con­trast. This is accom­plished with an expec­ta­tion max­i­miza­tion algo­rithm that processes the low-​​flux data in aggre­gate, and with­out any prior knowl­edge of the object or its ori­en­ta­tion. The ver­sa­til­ity of the method promises, more gen­er­ally, to rede­fine what mea­sure­ment sce­nar­ios can pro­vide use­ful sig­nal in the high-​​noise regime.”
  
  structural-​​biology image-​​analysis crys­tal­log­ra­phy algo­rithms inverse-​​problems nudge-​​targets sta­tis­tics

• [1203.3203] An effi­cient algo­rithm for gen­er­at­ing AoA networks

  “The activ­i­ties, in project sched­ul­ing, can be rep­re­sented graph­i­cally in two dif­fer­ent ways, by either assign­ing the activ­i­ties to the nodes ‘AoN’ directed acyclic graph (dag) or to the arcs ‘AoA dag’. In this paper, a new algo­rithm is pro­posed for gen­er­at­ing, for a given project sched­ul­ing prob­lem, an Activity-​​on-​​Arc dag start­ing from the Activity-​​on-​​Node dag using the con­cepts of line graphs of graphs.”
  
  sched­ul­ing operations-​​research algo­rithms graph-​​theory

• [1203.3341] A Com­par­i­son of Multi-​​Parametric Pro­gram­ming, Mixed-​​Integer Pro­gram­ming, Gra­di­ent Descent Based, and the Embed­ding Approach on Four Pub­lished Hybrid Opti­mal Con­trol Examples

  “…Com­mon mis­con­cep­tions regard­ing the embed­ding approach are addressed includ­ing whether or not it results in an aver­age value con­trol model (no), is nec­es­sary to “tweak” the algo­rithm to get bang-​​bang solu­tions (no), requires infi­nite switch­ing (no), has real-​​time capa­bil­ity (yes), or reduc­tion to a clas­si­cal non­lin­ear opti­miza­tion prob­lem (a desir­able yes).”
  
  control-​​theory operations-​​research algo­rithms numerical-​​methods philosophy-​​of-​​engineering design-​​patterns nudge-​​targets

• [1203.3270] Extrac­tion of Facial Fea­ture Points Using Cumu­la­tive Histogram

  “This paper pro­poses a novel adap­tive algo­rithm to extract facial fea­ture points auto­mat­i­cally such as eye­brows cor­ners, eyes cor­ners, nos­trils, nose tip, and mouth cor­ners in frontal view faces, which is based on cumu­la­tive his­togram approach by vary­ing dif­fer­ent thresh­old val­ues. At first, the method adopts the Viola-​​Jones face detec­tor to detect the loca­tion of face and also crops the face region in an image. From the con­cept of the human face struc­ture, the six rel­e­vant regions such as right eye­brow, left eye­brow, right eye, left eye, nose, and mouth areas are cropped in a face image. Then the his­togram of each cropped rel­e­vant region is com­puted and its cumu­la­tive his­togram value is employed by vary­ing dif­fer­ent thresh­old val­ues to cre­ate a new fil­ter­ing image in an adap­tive way. The con­nected com­po­nent of inter­ested area for each rel­e­vant fil­ter­ing image is indi­cated our respec­tive fea­ture region. A sim­ple lin­ear search algo­rithm for eye­brows, eyes and mouth fil­ter­ing images and con­tour algo­rithm for nose fil­ter­ing image are applied to extract our desired cor­ner points auto­mat­i­cally. The method was tested on a large BioID frontal face data­base in dif­fer­ent illu­mi­na­tions, expres­sions and light­ing con­di­tions and the exper­i­men­tal results have achieved aver­age suc­cess rates of 95.27%.”
  
  image-​​segmentation image-​​analysis face-​​recognition algo­rithms nudge-​​targets

• [1203.3284] Effi­cient Enu­mer­a­tion of the Directed Binary Per­fect Phy­lo­ge­nies from Incom­plete Data

  “We study a character-​​based phy­logeny recon­struc­tion prob­lem when an incom­plete set of data is given. More specif­i­cally, we con­sider the sit­u­a­tion under the directed per­fect phy­logeny assump­tion with binary char­ac­ters in which for some species the states of some char­ac­ters are miss­ing. Our main object is to give an effi­cient algo­rithm to enu­mer­ate (or list) all per­fect phy­lo­ge­nies that can be obtained when the miss­ing entries are com­pleted. While a sim­ple branch-​​and-​​bound algo­rithm (B&B) shows a the­o­ret­i­cally good per­for­mance, we pro­pose another approach based on a zero-​​suppressed binary deci­sion dia­gram (ZDD). Exper­i­men­tal results on ran­domly gen­er­ated data exhibit that the ZDD approach out­per­forms B&B. We also prove that count­ing the num­ber of phy­lo­ge­netic trees con­sis­tent with a given data is #P-​​complete, thus pro­vid­ing an evi­dence that an effi­cient ran­dom sam­pling seems hard.”
  
  phy­lo­ge­net­ics inverse-​​problems genet­ics algo­rithms sta­tis­tics nudge-​​targets

• [1203.0879] Design­ing and using prior knowl­edge for phase retrieval

  “In this work we develop an algo­rithm for sig­nal recon­struc­tion from the mag­ni­tude of its Fourier trans­form in a sit­u­a­tion where some (non-​​zero) parts of the sought sig­nal are known. Although our method does not assume that the known part com­prises the bound­ary of the sought sig­nal, this is often the case in microscopy: a spec­i­men is placed inside a known mask, which can be thought of as a known light source that sur­rounds the unknown sig­nal. There­fore, in the past, sev­eral algo­rithms were sug­gested that solve the phase retrieval prob­lem assum­ing known bound­ary val­ues. Unlike our method, these meth­ods do rely on the fact that the known part is on the bound­ary. Besides the recon­struc­tion method we give an expla­na­tion of the phe­nom­ena observed in pre­vi­ous work: the recon­struc­tion is much faster when there is more energy con­cen­trated in the known part. Quite sur­pris­ingly, this can be explained using our pre­vi­ous results on phase retrieval with approx­i­mately known Fourier phase.”
  
  image-​​analysis image-​​processing learn­ing inverse-​​problems algo­rithms nudge-​​targets

• [1203.3415] A New Approach to Count Pat­tern Motifs Using Com­bi­na­to­r­ial Techniches

  “We pro­posed two new exact algo­rithms to detect net­work motifs of size 3 and 4. Con­sid­er­ing that motifs need to count the iso­mor­phic pat­terns in the orig­i­nal graph $G(V,E)$ and in a set of ran­dom­ized graphs, the fol­low­ing com­plex­i­ties con­cern about count iso­mor­phic pat­terns in a sin­gle graph. Let $m=|E|$ and let $a(G)$ be the arboric­ity of $G$. Assume $|E|geq|V|$. We describe a $O(a(G)m)$ time com­plex­ity algo­rithm to count iso­mor­phic pat­terns of size 3. The com­plex­ity is a $O({msqrt{m}})$ in the worst graph. The sec­ond algo­rithm is a $O(m^2)$ com­plex­ity algo­rithm to count iso­mor­phic pat­terns of size 4. The final result was expres­sive faster when com­pared with other imple­mented algorithms.”
  
  network-​​theory graph-​​theory algo­rithms nudge-​​targets