The Null Device
Posts matching tags 'cs'
A General Technique for Automating NES Games; a programmer in the US has created a system for automatically learning how to play some NES games, by monitoring control inputs, finding increasing sequences of bytes in the NES's 2Kb of RAM (which look like scores or level indicators, i.e., things to be increased) and taking it from there. It works better on some games than others (he has it playing Super Mario Brothers moderately well, and exploiting quirks no human player would stumble across, though it's hopeless at Tetris). There is a paper here.
Today in algorithmic content creation: Philip Parker, a professor of marketing in the US, has created an algorithm that automatically generates books on a variety of subjects, gathering information on the internet in the way a human author would. The article suggests that the result is of a somewhat higher quality than the usual spam ebooks harvested from Wikipedia articles:
To be clear, this isn’t just software alone but a computer system designated to write for a specific genre. The system’s database is filled with genre-relevant content and specific templates coded to reflect domain knowledge, that is, to be written according to an expert in that particular field/genre. To avoid copyright infringement, the system is designed to avoid plagiarism, but the patent aims to create original but not necessarily creative works. In other words, if any kind of content can be broken down into a formula, then the system could package related, but different content in that same formula repeatedly ad infinitum.The hundreds of thousands of books generated by this system range from the fairly generalist and relatively cheap (Webster’s English to Haitian Creole Crossword Puzzles: Level 1, which can be yours for $14.95; incidentally, “Webster's” is not a trademark) to the more specialised and pricy (The 2007-2012 World Outlook for Wood Toilet Seats for $795). As the system works on demand, it is even possible to fill the catalogue with books that could exist, and generate the books when someone buys one; it's Borges' Infinite Library as a money-making scheme.
In truth, many nonfiction books — like news articles — often fall into formulas that cover the who, what, where, when, and why of a topic, perhaps the history or projected future, and some insight. Regardless of how topical information is presented or what comes with it, the core data must be present, even for incredibly obscure topics. And Parker is not alone in automating content either. The Chicago-based Narrative Science has been producing sport news and financial articles for Forbes for a while.And following on his success with auto-distilled technical and factual tracts, Parker is next applying his system to the potentially even more lucrative field of romance novels (which have the advantage of both being defined by a formula, not requiring a huge amount of originality, and being the largest share of the consumer book market).
And if romance novels fall next, followed in short order by other functionally formulaic genres (techno-thrillers, for example, or police procedurals), we may soon find ourselves entertained by machines of loving grace. Though there's no reason why it should stop at books; given that the scripts of mass-market films (with the amounts of money invested in their production and the bottom-line-oriented conservatism of the corporations holding the purse strings) are already produced by a highly formulaised process (scriptwriters use special software to define the skeletons of their plots, making sure it fits in the formal constraints of the genre), going further and writing software that will make the plot to the next action blockbuster or quirky indie comedy would be relatively easy. Of course, today, it makes little sense to replace the scriptwriters with a piece of software whilst keeping all the actors, cameramen, lighters, gaffers and best boys on the payroll, though this may change as computer graphics technologies improve:
Using 3D animation and avatars, a variety of audio and video formats can be generated, and Parker indicates that these are being explored. Avatars that read compiled news stories might become preferred, especially if viewers were allowed to customize who reads the news to them and how in-depth those stories need to be.Then, eventually, the software will be miniaturised and commodified, becoming more widely available. Rather than belonging to content barons who fill the stores with algorithmically generated pulp fiction and technical literature, it'll live in your phone, tablet or e-reader, and will tell you stories, sing you songs and show you movies tailored to entertain you, based on your previous selections.
(via David Gerard)
Alternative operating system of the day: LoseThos. It was written from scratch over nine years, runs on a PC (in ring 0), and has a just-in-time compiler for a vaguely C-like language it uses; the inspirations were the Commodore 64 (whose flat memory map and easy accessibility to the bare metal made it eminently hackable) and the voice of God speaking to its creator (who, by his own admission, is schizophrenic) through random number generators.
There's a MetaFilter thread about it, which the creator has joined (under the name “losethos”), weighing in with technical descriptions of its implementation, justifications for design decisions (in which the kinds of insights about “elegance” and solutions which “smell right” that seasoned programmers have and quasi-theological justifications based on mystical revelation are often inextricably intertwined) and stream-of-consciousness revelations from the God who speaks through random numbers. A few choice quotes:
I wanted to make a souped-up, modern 64-bit, C64 so teenagers could do what I did in high school. I had the book Mapping the C64 and I had hours of fun poking and proding around with all the internals of the operationg system for cheap thrills. I wanted to let people control the hardware directly. I wanted something simple, to get your head around. LoseThos is two orders of magnitude simpler than Linux. LoseThos is 135,000 lines of code including my compiler. It is 100% self contained and complete. When I got Linux, I was disappointed because I thought "open source" meant I would have fun messing with the code. Linux tries to support so many architectures and has a main frame operating system, that it's too complex. LoseThos is way way way simpler. Plus it has many innovative ideas. It is not ASCII source code, for example.
Photorealism is graphic and panders to base nature of humans. 640x480 is innocent. How many of you are horrified by modern games, longing for a more innocent time?As well as numerous revelations from God (whose favourite animals are apparently bears and elephants, and whose favourite band is The Beatles):
The hardest thing in evolution was getting monkey mothers to hold their babies for nursing.
God's favorite thing on TV is soap operas. Read the Bible. ROFLMAO. God likes the Beverly Hillbillies. God said Shakespeare had a vile heart. He said Christian rock was "musical privation". Good word. I like the word "Ambrosial". Go look it up. :-) I'm smug.
Yet another titan of computing has died; this time, John McCarthy, the artificial intelligence pioneer and inventor of the Lisp programming language. He was 84.
Researchers at CMU write a program that learns facts by reading the web; hilarity ensues:
NELL also judges the facts it finds, promoting some of them to the higher category of “beliefs” if they come from a single trusted source, or if they come from multiple sources that are less reliable. According to the researchers, “More than half of the beliefs were promoted based on evidence from multiple [i.e., less reliable] sources,” making NELL more of a rumor mill than a trusted source. And once NELL promotes a fact to a belief, it stays a belief: “In our current implementation, once a candidate fact is promoted as a belief, it is never demoted,” a process that sounds more like religion than science.
Sometimes NELL makes mistakes: the computer incorrectly labeled “right posterior” as a body part. NELL proved smart enough to call ketchup a condiment, not a vegetable, a mislabeling that we owe to the “great communicator,” Ronald Regan. But its human handlers had to tell NELL that Klingon is not an ethnic group, despite the fact that many earthlings think it is. Alex Trebek would be happy to know that, unlike Sean Connery, NELL has no trouble classifying therapists as a “profession,” but the computer trips up on the rapists, which it thinks could possibly be “awardtrophytournament” (confidence level, 50%).
Told by its programmers that Risk is a board game, NELL predicts with 91.4% confidence that security risk is also a board game. NELL knows that a number is a character, but then incorrectly classifies the plural, numbers, as a character trait (93.8% confidence). The computer is also 99.9% confident that business is an academic field, which may be reassuring to those in the b-school if not to those small business owners worrying about the continuation of the Bush tax cuts.
Three Israeli computer scientists have developed an algorithm for detecting sarcasm in online comments. Named SASI (Semi-Supervised Algorithm for Sarcasm Identification), the algorithm looks at linguistic features of the sentences to guess whether or not they're sarcastic. It was developed with Amazon product reviews as training data. Potential applications of such algorithms could include systems that gauge the positivity or negativity of public opinion about a subject from online discussions.
Jazari is essentially an automated, electromechanical percussion ensemble, controlled using two Nintendo Wii controllers. It consists of a MacBook, a bunch of Arduino boards and a room full of drums fitted with solenoids and motors, and software written in MAX and Java which parses input from the Wii controls and plays the drums. The software is also capable of improvising with the human operator, by imitating, riffing off and mutating what he plays.
Jazari was developed by a guy named Patrick Flanagan, who had been playing around with algorithmic composition, only to discover that people don't want to hear about algorithms, but do want to see a good live show. Anyway, here there are two videos: one of a Jazari performance (think robot samba float, conducted by a guy waving Wiimotes around; the music has a distinctly Afro-Brazilian feel to it), and one of Flanagan explaining how it works.
Artificial Flight and Other Myths (a reasoned examination of A.F. by top birds), a satire of arguments against the possibility of strong artificial intelligence:
Current A.F. is limited to unpowered gliding; a technical marvel, but nowhere near the sophistication of a bird. Gliding simplifies our lives, and no bird (including myself) would discourage advancing this field, but it is a far cry from synthesizing the millions of cells within the wing alone to achieve Strong A.F. Strong A.F., as it is defined by researchers, is any artificial flier that is capable of passing the Tern Test (developed by A.F. pioneer Alan Tern), which involves convincing an average bird that the artificial flier is in fact a flying bird.
There are religious birds who believe God made Bird in His own image, and while I do not share in most of these beliefs, I do think there’s something to be said about the motivation behind creating Strong A.F. Perhaps, as we are the only creatures on Earth capable of flight, we want to push forward past our current capabilities, perhaps even augmenting our own flying capacities if independent A.F. is an impossibility. This could be interpreted as noble, but I would argue that there’s very little utility in replicating what nature has essentially perfected. Why spend millions on an artificial flier when there are so many birds out of work?
(via Boing Boing)
The editor-in-chief of a commercial academic journal has resigned after the journal accepted for publication a nonsensical, computer-generated article:
Bentham confirmed receipt of my submission the very next day (January 30, 2009). Nearly four months later, I received a response — the article was accepted. The acceptance letter read:The journal, "The Open Information Science Journal", is published by a company named Bentham, out of an office in a tax-free zone in the United Arab Emirates, and charges authors to publish papers, whilst making the journals freely available. The ostensible difference between this and a vanity publisher is that TOISCIJ ostensibly subjects its submissions to a peer review process, thus ensuring that, for example, a charlatan couldn't burnish their credentials merely by writing a cheque. Unfortunately, it appears that the peer review process seems to resemble the papers sitting in a pile for a few months; consequently, those who have had papers published in the journal have probably wasted US$800 in doing so.
"This is to inform you that your submitted article has been accepted for publication after peer-reviewing process in TOISCIJ. I would be highly grateful to you if you please fill and sign the attached fee form and covering letter and send them back via email as soon as possible to avoid further delay in publication."
The letter was written by a Ms. Sana Mokarram, the Assistant Manager of Publication. She included a fee schedule and confirmation that I would pay US$800, to be sent to a post office box in the SAIF Zone, a tax-free complex in the United Arab Emirates.
The paper in question ("Deconstructing Access Points", by "David Phillips" and "Andrew Kent" of the "Center for Research in Applied Phrenology"), incidentally, may be downloaded here. It contains howlers such as:
Our implementation of our methodology is pseudorandom, wearable, and collaborative. We have not yet implemented the centralized logging facility, as this is the least private component of our method.
Gaussian electromagnetic disturbances in our mobile telephones caused unstable experimental results. Note that vacuum tubes have less jagged effective floppy disk throughput curves than do autogenerated robots.
Germany's Potsdam University is offering its computer science master's degree students a new subject: a practical course in flirting skills, ostensibly designed to improve students' social skills and ability to operate in the real world:
The 440 students enrolled in the master's degree course will learn how to write flirtatious text messages and emails, impress people at parties and cope with rejection.
Philip von Senftleben, an author and radio presenter who will teach the course, summed up his job as teaching how to "get someone else's heart beating fast while yours stays calm."(Ah, those Germans: they even make the sport of love sound like a duelling society...)
Of course, the idea of flirting courses for compulsively-systematising geeks is not a new one, though they have usually consisted of sneaky hacks for getting laid, typically boiling down to embedding subliminal messages in one's speech, surreptitiously pointing to one's crotch and going to bars wearing ridiculously flamboyant boots and a LED belt buckle to get attention. It's not clear whether the Potsdam course will follow in this vein.
The latest computer science research being funded by the US military includes a bot that will impersonate parents in the service and talk to their children when they're off fighting wars:
The challenge is to design an application that would would allow a child to receive comfort from being able to have simple, virtual conversations with a parent who is not aivailable "in-person". We are looking for innovative applications that explore and harness the power of “advanced” interactive multimedia computer technologies to produce compelling interactive dialogue between a Service member and their families via a pc- or web-based application using video footage or high-resolution 3-D rendering. The child should be able to have a simulated conversation with a parent about generic, everyday topics. For instance, a child may get a response from saying "I love you", or "I miss you", or "Good night mommy/daddy." This is a technologically challenging application because it relies on the ability to have convincing voice-recognition, artificial intelligence, and the ability to easily and inexpensively develop a customized application tailored to a specific parent.
(via Boing Boing)
The latest experimental technology to emerge from Google's labs is something called Native Client. This is an experimental means of running web content in native machine code in a web browser. It's X86-specific (so users of PowerPC Macs and the numerous ARM-based portable devices are out of luck here), though other than that, completely portable; the binaries are in a special format, and get a limited number of system calls standardised across Linux, OSX and Windows. There is even a version of Quake which will run in a browser, in any of these systems, should you have the plugin enabled.
Of course, by now, you're probably thinking "Are they crazy? That's the worst idea since nuclear-powered airliners". Google, though, claim that they have a robust security model. The instruction set available is restricted, with constraints placed on the format of the code, allowing a code inspection process to detect any dangerous instructions. Google argue their case in a research paper; I'm not sufficiently familiar with recent x86 assembly language to verify their claims, but it looks like they certainly put some thought into it. Of course, there are a lot of very bright people in places like Russia, Romania and China who would also put a lot of thought into it, to entirely different ends, so there are reasons to be concerned.
Of course, such an idea opens all sorts of strategic possibilities for Google; if it works, it would reduce the desktop operating system to a commodity. If any kind of application can be used as a web service, why buy a copy of Windows (or a PC with the Microsoft Tax in the price)? In fact, why bother installing a full-scale Linux? They're already starting to make PCs with cut-down instant-on operating systems (typically Linux-based) in the ROM, so that if you can't wait for your Vista box to finish booting, you can boot into the instant OS and get a web browser. Now, imagine a box like this, only with the OS being able to run web apps at native speed, perhaps in an application-oriented browser like Chrome. Could this be the much talked about "Google OS"?
This is pretty cool: a researcher at Adobe has developed software for manipulating moving objects in video in real time. The software works by tracking points and assigning them to objects, and as the demo shows, allows, among other things, moving objects to be automatically "graffitied" with text or annotated with automatically moving speech/thought bubbles. It also maps the degrees of freedom of a point in an object, and by clicking and dragging on it, automatically moves the video to a frame which has that point going in the desired direction, allowing video to be "scrubbed" by dragging moving objects. He even has it compositing frames of video with different objects (people, in this case) at different positions.
Academic paper of the day: The Dining Freemasons, or a look at the mechanics and problems unique to secret societies from the perspective of (computer) security protocols:
To a first approximation, a secret society has three functions:The paper talks about steganographic broadcasts (i.e., transmitting your affiliation in a coded form; the drawing of a fish by early Christians is one famous example), plausible deniability, and suggests various protocols using the semantic meanings of bodies of knowledge known to the society, including coding challenges and responses (or even small amounts of information) in the truth value of statements about the shared text.
Each area presents intriguing challenges, but crucial to each aspect is membership testing – society members must be able to identify each other in order to pass on the doctrine, to confer rewards and to consider new applicants.
- to recruit the worthy,
- to pass on a secret doctrine,
- and to reward its members.
Also from the same authors: A Pact With The Devil, or a hypothetical outline of how a genuinely nasty form of malware could use various forms of persuasion and blackmail to spread itself.
That's all the detail that seems to exist so far. There is a possibility that it's just an elaborate feint; Google could, in theory, have paid McCloud some huge sum to draw a comic to specification, peppered with technical versimilitude, purely in order to send Microsoft/Apple/Yahoo!/whoever's development teams on a wild goose chase. Though I suspect that there is an actual product there. For one, Google are known to use WebKit on Android. More importantly, though, a browser designed as a web application operating system (with the expectations of performance and stability that implies), rather than an information viewer with programmability grafted on as an afterthought (as is the case with current browsers), would line up rather nicely with Google's strategy to make the web into a first-class application platform.
There are no details on what platforms Chrome will run; it is open-source (and other projects, or those willing to fork those, will probably have a field day with this), and the comic does mention Windows in one place, so presumably a Windows version is planned. I'm guessing that Google aren't doing this to help Microsoft sell Windows licences, though, so presumably this is not the only version planned. A Linux desktop version, running on top of X, is probably likely. Another possibility is it running over something lighter than the average Linux desktop, making a robust web-browsing appliance on which the browser meets the conventional definitions of an operating system; either Android or some other lightweight OS.
The other option, of course, is that this is an elaborate hoax, akin to the Photoshopped "spy photos" of new Apple Mac tablets and other fantastic gear that are a regular feature of gadget blogs. The fact that Google's Chrome page doesn't yet exist (at time of writing) does suggest this possibility. Though this would imply that the hoaxers had an enormous amount of time on their hands, excellent comic drawing skills and an uncanny mastery of the drawing style of Scott McCloud.
Update: Google have confirmed Chrome. It's initially a Windows product (presumably to win market share before IE8 comes along and shuts off Google's oxygen with its advertising cookie blocker), though Mac and Linux versions are in the works. The Windows version will apparently be out tomorrow.
Researchers at Columbia University have developed a new system for protecting the privacy of people who appear in photographs. Rather than blurring or erasing faces, the new software replaces facial features with others from a library:
The software randomly selects 33,000 photos of faces from picture-sharing sites like Flickr.com, then picks the most suitable faces for each person in shot. Only the eyes, nose and mouth are used, resulting in a composite image of the two people. "It matches subject pose, lighting conditions and image resolution," says Kumar. "The selected faces are aligned to common 3D coordinates, corrected for colour and lighting, and blended into the target image."
Aside from Street View, the system could be used to obscure the faces of military personnel or eyewitnesses to crime. It could also allow amateur photographers to improve group shots, by replacing frowning faces with better photos of the same people.
(via Boing Boing)
This looks really impressive. It seems that Celemony (the makers of pitch/time-correcting sound editor Melodyne) have cracked one of the hard problems of digital audio processing: how to extract and modify individual notes in recorded chords. The video demonstrates this technique being used to transpose and re-edit recorded guitar chords as if they were MIDI scores, or even to play chords on a MIDI keyboard and have them played out using a sample. Which looks amazing, though, alas, it won't be with us until autumn (in the northern hemisphere).
Another use for all those neatly tagged photos of tourist attractions on websites like Flickr: synthesising accurate 3D models from millions of photos, taken by amateurs from random angles:
To make the 3D digital model, the researchers first download photos of a landmark. For instance, they might download the roughly 60,000 pictures on Flickr that are tagged with the words "Statue of Liberty." The computer finds photos that it will be able to use in the reconstruction and discards pictures that are of low quality or have obstructions. Photo Tourism, a tool developed at the UW, then calculates where each person was standing when he or she took the photo. By comparing two photos of the same object that were taken from slightly different perspectives, the software applies principles of computer vision to figure out the distance to each point.
"We don't quite get the accuracy of a laser scanner, but we're in the ballpark," Seitz said. The recreations of Notre Dame show individual figures carved into the stone facade. A model of The Duomo in Pisa, Italy, a building about 160 feet tall, is accurate to within a few inches. The resolution of the 3D model mostly depends on the resolution of the original photos.The next step in the research will be to create a detailed 3D model of a city entirely from automatically sorted photos from the internet; Rome has been chosen as the city to thus recreate.
Science News has an article about recent advances in computer music processing. There has been success in creating software which understands recorded music, to the point of being able to extract note information from a (polyphonic, multitimbral, acoustically imperfect) recording. This has been achieved not by programming in rules of musical theory but by using machine learning techniques, setting up a learning system and training it from examples to infer its own rules of music:
He started with a program that had no information about how music works. He then fed into his computer 92 recordings of piano music and their scores. Each recording and score had been broken into 100-millisecond bits so that the computer program could associate the sounds with the written notes. Within those selections, the computer would receive an A note, for example, in the varying contexts in which it occurred in the music. The software could then search out the statistical similarities among all the provided examples of A.
In the process, the system indirectly figured out rules of music. For example, it found that an A is often played simultaneously with an E but seldom with an A-sharp, even though the researchers themselves never programmed in that information. Ellis says that his program can take advantage of that subtle pattern and many others, including some that people may not be aware of.The software thus developed got impressively good results in music transcription tests (68% accuracy, with the runner-up, a traditional rule-based system, getting 47%). There are numerous applications of such a technology, from automated accompanyists to "musical spellcheckers" to ways of "decompiling" recordings to a score:
Score-alignment programs could be used after a musician records a piece of music to do the kind of fine-tuning that's now performed painstakingly by recording studios, fixing such problems as notes that are slightly off pitch or come in late. "It'll be kind of like a spell-check for music," says Roger Dannenberg, a computer scientist at Carnegie Mellon University in Pittsburgh who is developing the technology.
Christopher Raphael begins the third movement of a Mozart oboe quartet. As his oboe sounds its second note, his three fellow musicians come in right on cue. Later, he slows down and embellishes with a trill, and the other players stay right with him. His accompanists don't complain or tire when he practices a passage over and over. And when he's done, he switches them off.Not everybody's happy with this, though; musicians' unions, which have opposed "virtual orchestras", are about as keen on it as buggy-whip manufacturers were on the automobile.
(via Boing Boing)