Hack Jam Log Book is a log of progress made in and around a weekly hack session. Topics include natural language processing, high energy electronics, linguistics, interface design, &c. Enjoy.

Recent Posts:

Archives:

31.10.08

 

Greetings

This is my first blog post to this, or any other blog... so please bear with me as I gather up steam and learn the new format.

For those of you who don't know me, I'm Brandon. Hello! I know there isn't much listed on my current project, so here is generally the gist... we got an old upright Lexington-brand piano free from some nice people who were cleaning their basement. The guys here were interested in getting a piano for the foyer, but didn't want to spend a lot [read "any"] money. As such, the piano is what you expect from a free piano. The word "totaled" comes to mind [and that of the piano tuner I had take a look at it].

To make a long story short, being the group full of steam-punk, tinkering, tech heads that only the readers of this blog might enjoy, we decided to turn this 1940's upright piano into an electric keyboard. Perfect! Keeps a tune forever and maybe does other nice nifty things as well.

Having never messed with embedded systems [or electronics even], it made process somewhat scary. However, it still had to be easier [and cheaper] than rebuilding normally. I got together with Sam [who is Fantastic in only ways Dr. Who can describe] and plotted the course. We purchased the following items:

* 100 x Small Raised Tactile Switches
* 3 x Atmega16 Microcontrollers
* 3 x 5 Volt VRMs
* 1 x JTAG-ICE-MKI programmer for said Atmegas
* 1 x "magical" breakout board from Sparkfun [SKU: BOB-00718 ] to turn signals into computer based serial.
* 1 x Jumperkit, including Capacitors, resistors, and some breadboards... various other sundry electronic components [Total cost so far, < $150 US].

The general goal is to have the microcontroller interpret the incoming signals from the various buttons, encode them into a long byte stream, send it over to a laptop running ALSA hidden in the piano cabinent and PRESTO! Electronic piano!

As to installing the AVR Toolkit, I know that Sam mentioned how frustrating some things were. I am running Mandriva Linux 2008 on my devel-machine and installed the following packages to get everything working AOK:

avrdude
avr-libc-1.6.2
binutils-2.19.50
ddd [graphical gdb front-end, kinda nice since I'm not used to gdb]
gcc-4.3.2 for the AVR [you'll use --target=avr]
gdb-6.8 [for handyness]
gmp-4.2.2
mpfr-2.3.0
simulavr-0.1.2.5

Those are all of the packages that you truly need [plus their sub-dependencies, such as a YACC or a BISON... also a neat one called "m4" for gcc.

With those installed, you should be good to go. However, I do want to draw this post to a close as otherwise it will be so long you might loose interest.

I will post my Makefile and other "piano-warez" on my website or this blog for those who are interested. The Makefile is very basic, so remember, just because you graduate with a BS in CS does not make you a programmer.

I will also post on some of my other projects as they happen.

Regards,

Brandon Bagwell

Labels:


 

Words about Language

I've had a pretty productive week with regards to my NLP project; I added an implementation of backward chaining inference, so now I can start playing with interpreting context and unifying concepts. With that built, I'm more or less back up to where I was with my first system, only with a code base that still has room to grow. I can ask simple questions, and so long as the knowledge base is in the right state, get yes or I-don't-know answers. Unfortunately, my approach right now is so general that if I mention two facts about a specific thing, say, emacs, the system won't make the assumption that I'm not talking about two different things, both called emacs.

Which brings me to my next target, context and pronouns. Pronouns are obviously a problem for computers; if I say "Bob threw a brick at the window, and it shattered," what shattered? It's easy for us to say that the window shattered, but we get that from our knowledge of the world, not from any particular structure in the sentence. I could also say "Bob threw a vase at the wall, and it shattered," and this time, with the same structure, "it" now refers to the object being thrown, the vase.

We know this from one of two ways, and I'm not sure which. We either know that a vase or window can shatter, whereas a brick or wall is not likely to, or we visualize the event and our internal model predicts which object shatters. Neither is particularly easy for a computer; the latter has obvious computational problems, the former requires a search through potentially large amounts of data.

For my first crack at it, I'll be keeping a list of 'things' that have been in context, attempting to unify objects referred to by pronouns until I don't end up with a conflict. I'm planning on limiting the domain of 'things' that can be discussed to something small, like the nature of files, programs, and directories, in what I'm sure will be a vain attempt to limit the size of the knowledge base that this approach will require.

In other news, my posts on the comprehension module are still coming, but writing them keeps taking longer than I expect. Just when I get into the flow of writing, I notice something I'm doing wrong and have to go fix it.

I've read two papers in the past week. Modeling Semantic Containment and Exclusion in Natural Language Inference, MacCartney and Manning covers using natural logic for modeling the semantics of language, and the successes and problems they've found there. Recognizing Textual Entailment Via Atomic Propositions, Akhmatova and Molla describes an approach using traditional logic (like you saw in my Haskell-laden post).

Labels: ,


 

Livescribe Pulse Hacking I: The Frequency Domain

One of the frustrating things about the exciting livescribe pulse is it's inability to communicate with linux. Even through virtualization of a windows machine, you'll be lucky to get a working system.

Another is the fact that, while programs build with the livescribe pre-release SDK can save files to the pen, they cannot send those files to the desktop machine --- the only way to interact with program data is through the pen.

Well, I say pooh to that: "Pooh!"

Since I was first able to program my livescribe pulse (in a rude rendition of 'hello, world'), I've been scheming on how to communicate with the pen through hackish means. While reverse engineering the livescribe communications protocol would have been the correct way to do it, I feared it was, and is, beyond my means and motivation. I concentrated instead on the other two ways the pen has of communicating: the screen and the speaker.

My original plan had been to use light sensors, an AVR, and a program that would flash the pen's OLED display in order to send data back to the desktop computer. While this is plausible, the narrow bandwidth of the light produced by the OLED display makes it difficult to sense --- and the communication would always be one way. Besides, special hardware would be necessary, and that would make the potential user base tiny: linux-using livescribe owners who have the knowledge and hardware to program microcontrollers.

No, there must be a better way; so we turn to the speaker. Most computer owners have a microphone on hand; and communicating via tones is a tried and true method. My path is clear: create a livescribe modem!

In order to recieve information, the computer must be able not just to record the sounds coming from the pen, but to analyze them. To write software that can do that, we must have a firm understanding of the frequency domain. (Prerequisites note: If you don't have a firm understanding of the concepts frequency, wavelength, and sinusoidal graphs, it's time for a trip to wikipedia.

The central nugget of the matter goes like this: any continuous, periodic function can be represented as an infinite sum of sines and cosines.

Give that a minute to sink in; any function that is continuous --- not differentiable, just continuous --- and periodic --- but the length of the period can be as long as you like --- will do. Square waves, sawtooths, Bart Simpson's hair; any arbitrary waveform can be represented by a simple sum of sines and cosines.

Wow.

You may be worried about that word 'infinite' up there. Luckily, it turns out that we can approximate our function with some finite number k sines and cosines; and that each time we increase k, the approximation becomes more accurate.

Now let's take a moment to remember what the time domain, looks like. Imagine a signal coming from your microphone. It is a long string of numbers, and each number indicates a magnitude of sound at a single point in time (which is to say, the difference in pressure on the front and rear surfaces of the microphone pickup). If we were to graph the sound of someone whistling by using the time as the independent variable, and magnitude as the dependent, we'd see a lovely sine wave --- the archetypal image of sound, in the time domain.

But there is another way of plotting the same sound. We said that any curve --- no matter how complex our time domain curve might be --- can be represented by a sum of sines and cosines, right?

And, hold on to your hats, we only need 2 numbers to define a sine wave: the frequency of the wave, and the amplitude. So we have lots of data points enumerated by two real numbers? That sounds like a graph. And indeed it is. If we graph frequency as the independent variable and amplitude as the dependent, we have arrived at a graph of our sound in the frequency domain.

For those of you still having a little trouble visualizing, here's what the sound of me whistling looks like in the time domain:




And here's what it looks like in the frequency domain:



See that big sharp spike there around 800Hz? That is the primary frequency of the whistle (772Hz: a G5 that's a little flat). All the other stuff is the shower, the refrigerator, the computer fan, the traffic outside, the wind, and so on; but remember we're measuring in decibels, so they are whole orders of magnitude less in amplitude than the whistle.

Most of you are probably yelling at the screen by now, asking me how on earth we're supposed to find these numbers. Where do we get this sum of sinusoids if all we're given is the time domain information? The empty-words answer is "The fourier transform." To understand that answer, we're going to have to go in a journey --- one that I'll leave to my next post.

Labels: , , ,


30.10.08

 

Hack Jam: 10.29.08

,Topics of discussion: AVR, NLP, and MLB.

Brandon finally received all the parts for his electric piano conversion, so we set about getting his AVR toolchain and JTAG programmer working. We had a discussion of how messy the current binutils/avr-gcc/avr-libc combination is --- it was one of the worst source builds I have have ever had to perform. It took me more than a day on my machine --- and Brandon sped through the process in just 6 hours on his.

For those of you out there that are receiving that relished error "illegal opcode movw for mcu avr3", there is hope! My recommendations are:
  • Remove all traces of avr-binutils. Kill them dead. Remnants of the latest release of binutils will wreak havoc when you try to work either with bleeding edge snapshots or older versions.
  • Forget the latest releases --- go back several stable versions of both gcc and binutils, to at least January 2008, or even back into 2007. (Your other option is to get bleeding edge snapshots, but I did not have any more success with these than with the latest releases.)
  • Download all the avr-gcc and binutils patches you can find from the date of release of binutils and gcc that you downloaded to the date of the next stable version; attempt to apply all of them. Don't worry if some fail --- just push ahead.
  • For the actual configuring, I recommend reading this page.
  • Make and install binutils.
  • Make and install gcc (fingers crossed!)
  • Only upon the successful completion of avr-gcc's install should you even worry about avr-libc.
Note that these are only hints. I am not attempting to give a full overview of what works --- but you'll save many headaches if you start with these steps.

On calling my shots:
  • You may have noticed the lack of posts. Surprise! I failed to meet both drawing post calls
  • I did program my livescribe. penlets.com was a major help
  • I did get a relatively detailed outline ready for nanowrimo
Score: 2/4.

For next week:
  • A post on my evil plans for communicating with linux from my livescribe pulse.
  • The beginning of a nano novel. Huzzah!

Labels: ,


25.10.08

 

Pluralities and Progress

I've been wondering for a while about how to deal with the meaning of plural nouns. In my last post I treated them as referring to all things of a type, as in "The rm program deletes files". But they can also refer to a set of things of a type, as in "Bob deleted files." There's an implied "some" in that second sentence; we know that Bob didn't delete all files everywhere. The tense of the sentence or passage helps quite a bit for determining which interpretation is more probable, but that approach is not ironclad. Contrast "Bob deleted files," with "Bob deleted his files." "His files" is a smaller set of things, one that Bob could conceivably delete all of. Unfortunately, the knowledge of files, the act of deleting, and Bob that we can use to differentiate the two situations come from prior knowledge. I'm hoping to use logical inference for disambiguation like this, but at the moment, I'm not optimistic about the size of the knowledge base that will be necessary.

In other news, I've been working on this long enough now that I'm going to start reading the literature. I'm probably way overdue on this step, having so far only read through what Russell and Norvig had to say about this in their book.

I met both of my goals for last week, though my recognition of plurality is a bit crude. I'm intending to revisit how I'm representing my dictionary soon, so I'll make it less crude then.

For this week, my goals are:
  • Build a simple logical inference framework
  • Read two papers on AI
  • Continue the NLP series with interpretation of verb phrases.

Labels: ,


23.10.08

 

Hackjam 10.22.08

Discussion topics: puzzles, communication, form/content interrelationships, the livescribe pulse, Steven Wright, logic puzzles, cellular automata.

We had a lengthy conversation on how art and communication can work together, and how they can work against each other. We came to no conclusions, but I thought it might be interesting to talk a little about how I think about the form/content interrelationship, and why it's so important to me in art critique and analysis. I'll do it a bit jesuitically, because I think art criticism is too often left too open to opinion --- let's all share the same language, shall we?

For the sake of brevity and generality, I will refer to a work of art as an artifact. The artifact is the actual painting, sculpture, poem, novel... even performance art leaves behind a temporal artifact, which is the primary means of the audience experiencing the piece.

The audience is anyone who comes in contact with the artifact. Note that this is distinguished from the intended audience, which are the people the artist expects or desires to come in contact with the artifact.

The content is the change in the audience caused by contact with the artifact. That is a trickier definition than is often put forward. This definition does not discriminate based on what the content is --- only where it comes from. What is worth taking away from this definition is that content can with a single thought be cleaved from intended content, just as audience and intended audience are distinct. As critics we are as much, if not much more, concerned with the content as with the intended content.

Finally, the hardest one. Form is the thingness of a thing. The form of a painting is the color, line, texture, surface, and technique used to paint it. The form of a poem is the prosody, the rhyme, the aural, temporal, and visual texture of the artifact. The context of the work (where, when, and how the audience comes in contact with it) is also a formal aspect. When we say "That's well made" we're discussing the form.

The relationship between from and content is of the utmost importance to the creation of a successful artifact. To understand why, we need to look even closer at what content is --- and more importantly where content is. "[...]
content is the change in the audience caused by contact with the artifact." Content only exists when the artifact comes in contact with the audience. Without an audience, content cannot exist. How does the audience know what to do? How do they know how they are supposed to change in order to create the proper content? There is no "audience instruction manual," is there? How can the artist tell the audience what to do when they don't even know who the audience is?

There is only one way for the artist to communicate with the audience --- through the artifact itself; through it's form.

Guernica
communicates the anguish of the bombing through line, shape, color, size, and context. Without performing a complete critique of the work (which you could find by doing this), we can see why the form is so important by performing a heavy-handed thought experiment. Can you imagine a photorealistic color image of an unhappy horse, that was, say, 8" by 10"? Compare that to the screaming animal in the center of Guernica (keeping in mind that the whole painting is more than 25 feet long). Would the content be the same? Or does the rough and broken line of the mother and child, the broken and offset curve of the bull's horns, the impossible jagged edge of the fallen sword, do they accomplish something that a different form could not, despite having the same intended content?

The relationship between form and content is impossible difficult, almost invisible, and it is what makes art art.

On calling my shots:

Last week I did get a post for makerfaire, I did not complete my post on drawing, but I did get some work on it done. It will go up this week. Score: 1/2.

This week I call:
  • Successfully programming the livescribe pulse with my own program
  • Completing my rough nanowrimo outline
  • Completing last weeks drawing post and adding another


Labels: ,


22.10.08

 

NLP: Grammar Trees to Logical Statements

I'm going to start a series of detailed posts about the comprehension module. This is the section that translates a grammar tree into a logical statement. For this discussion, we'll be looking at a simplified version of my simplified version of English grammar. We'll expand our grammar in future posts. Since I've started this post, I've improved my approach in this area as well, so you'll be seeing the evolution of this code, with a couple weeks lag time.

It also gives me an opportunity to introduce a bit of Haskell. I'll introduce you to Haskell just enough to understand what I'm doing. If you want to learn it well enough to use it, I suggest one of these fine tutorials.

> module HackjamNLP where

This post is written in literate Haskell. The lines begining with ">" are source lines, everything else is a comment. You can copy this post to a file and load it into an interpreter if you like.

> data Sentence = Declarative NounPhrase VerbPhrase
>
> data NounPhrase = ANoun Word
> | APronoun Word
> | Name Word
>
> data VerbPhrase = AVerb Word

What I'm doing here is defining three new types, Sentence, NounPhrase, and VerbPhrase, each with one or more type constructors. So a Sentence can be constructed with Declarative, a NounPhrase with ANoun, AProunoun, or Name, and VerbPhrase with Verb. Everything after the type constructor's name are the types each constructor requires to build a value of that type. In other code, here's a rough equivalent to Sentence's Declarative constructor in a bastard Java-like:

: Sentence Declarative(NounPhrase np, VerbPhrase vp) { ... }

So type constructors are like functions that return values of a given type (but more useful, as we'll see later).

> data Word = Word {
> wordString :: String,
> partOfSpeech :: PartOfSpeech,
> isPlural :: Bool
> }

Here we see another syntax for declaring a data type. It is common to name the constructor for a type the same thing as the type itself when there is only one constructor for that type. The :: can be read as "has type", so we can reason that a Word is made of wordString of type String, a partOfSpeech of type PartOfSpeech, and isPlural of type Bool. Each of these identifiers is a function that can be applied to a Word to get it's corresponding field.

You've probably noticed that Haskell is case sensitive. Actually, the upper/lower case convention I'm using isn't convention at all; It's required by syntax. All types and type constructors (and names of modules, but I'm not going there) are required to be uppercase, everything else is must be lowercase.

> data PartOfSpeech = Noun | Verb | Adjective | Article | Pronoun
> | Adverb | Unknown

One last definition. Here I'm enumerating the types of speech that I'm using. This is the same syntax as before, except none of these have any parameters, and I compacted the formatting.

Now I can build Sentences out of Strings, PartOfSpeeches, and Bools. As a quick example, let's quickly build a Sentence representing "I win.":

> iWin = Declarative (APronoun (Word "I" Pronoun False))
> (AVerb (Word "win" Verb False))

Tada.

Again, we're going to take for granted that some other nice module has generated these grammatical trees for us. We should only be concerned with converting them to logical statements. First, we define a representation of logical statements. This representation won't describe all logical statements; I've left out constructors that I won't be using here to keep things simple.

> data LogicSentence = Atom ID [Term]
> | And LogicSentence LogicSentence
> | Implies LogicSentence LogicSentence
> | ForAll Term LogicSentence
> | Exists Term LogicSentence
> deriving Show
>
> data Term = Variable ID
> | Set [Term]
> deriving Show
>
> type ID = String

The [] brackets in [Term] indicate a list of that type, and the last line defines ID to be a type equivilant to a String.

The deriving statements for Term and LogicSentence tell the compiler to generate a default implementation of a class. In this case, we want these types to be instances of the Show class so we can convert them to strings and display them on our terminals. This default necessarily be pretty, as we'll see later. We could also have it derive other classes like Read (to convert strings to the type), Eq (equality), and Ord (ordering, i.e. less than, greater than). Think of derive as saying "You're so smart, Mr Compiler, I'm sure you can figure out this on your own."

Now we can start building LogicSentences.

> x = Variable "x"
> iWinLogic = Exists x ((Atom "speaker" [x]) `And` (Atom "win" [x]))

Here I've put And inside backticks to change it from a prefix operator (like "f" in "f(x,y)") to an infix operator (like "+" in "x + y"). The braces are back, and again they denote lists. [x] creates the list with x as it's only element.

We've arrived at the point where we can work on what we came here to do. We'll tackle a bit at a time, starting with converting just the noun phrase to a logical sentence.

> convertNounPhrase :: NounPhrase -> LogicSentence

Here I've declared the type of something I'm calling convertNounPhrase. All this says is that it's a function that takes a NounPhrase and returns a list of LogicSentece. The compiler is smart enough that it could infer the type of the function on it's own, but it's common practice to specify it explicitly. There are two reasons for this. First, it serves to improve readability and provides documentation for the author. Second, it helps to locate compile errors by making sure the compiler arrived at the same type the author intended

> convertNounPhrase (Name name)
> = Exists x (Atom ("called-" ++ wordString name) [x])

Haskell is nice and lets us define functions in parts. Here we define the convertNounPhrase function when given a NounPhrase built with the Name constructor. This is called pattern matching, and it's wonderful for building functions like this cleanly. Haskell will try each definition of convertNounPhrase in the order defined until a match is found (if none are found, it throws an exception). Note that name here doesn't refer to the NounPhrase built with Name, but the word used to build Name with.

A name, by itself, indicates that there is something that is called by that name. In other words, our representation of "Adam" is: there exists some x such that called-Adam(x) is True. (++ is the concatenation operator, and strings are just lists of Chars, so that ("called-" ++ wordString n) buisness builds strings like "called-Adam".)

> convertNounPhrase (ANoun n)
> | isPlural n = ForAll x (Atom (wordString n) [x])

Besides specifying the manner in which a parameter is constructed, we can also place /guards/ in our pattern matches. This definition only matches Nouns built with a Word that satisfy isPlural. For the moment, we'll assume that no non-plural nouns without articles (the, a, an) are passed by the grammar tree builder.

The case statement draws near!

> convertNounPhrase (APronoun n)
> = case wordString n of
> "I" -> Exists x (Atom "speaker" [x])
> "you" -> Exists x (Atom "audience" [x])
> otherwise -> Exists x (Atom "in-context" [x])

I won't go into the syntax of case; I'm sure you can figure out how it works.

Note I'm leaving out a number of possibile pronouns here in the name of brevity.

> convertVerbPhrase :: VerbPhrase -> (Term -> LogicSentence)

We're getting trickier here. convertVerbPhrase is a function that takes a VerbPhrase and returns a list of functions. These functions each take a Term and return a LogicSentence. In Haskell, all functions are curried, so I could remove the parentheses from this type definition if I wanted to. I'm leaving them in for readability.

Why do we want to return a function here? A verb phrase describes an action or relation. It needs the subject of the sentence to complete it's meaning. If I say "dances a jig.", it's not a complete sentence; there is an immediate question of "Who?". It needs the who for the full meaning.

> convertVerbPhrase (AVerb v) = (\subject -> Atom (wordString v) [subject])

We'll expand verb phrases soon, but for now, we'll just deal with a single verb. This definition shows the syntax for a lambda function: (\x -> ... ). When we apply a term to the result of convertVerbPhrase, that term will be used in place of subject.

> convertSentence :: Sentence -> LogicSentence
> convertSentence (Declarative np vp)
> = let nounSentence = convertNounPhrase np
> subject = subjectOf nounSentence
> action = convertVerbPhrase vp
> in combineNVSents nounSentence (action subject)

Finally, the goal of the post. This demonstrates a let block. Those equal signs don't mean what they do in imperative programming. That is to say, we aren't evaluating convertNounPhrase np and storing the result as nounSentence, we are declaring that nounSentence is equivalent to convertNounPhrase np. We could have wrote this function as

> convertSentence2 (Declarative np vp)
> = combineNVSents (convertNounPhrase np)
> (convertVerbPhrase vp
> (subjectOf (convertNounPhrase np)))

So now we need to define subjectOf and combineNVSents, and we'll be done for now.

> subjectOf :: LogicSentence -> Term
> subjectOf (ForAll t _) = t
> subjectOf (Exists t _) = t

Another feature of Haskell's pattern matching: we can tell the compiler that we don't care about some terms. "_" is a wildcard. It will match anything for that term.

Note that we don't have to define subjectOf for all possible Sentences. We'll accept a Exception if it's called for a Sentence it's not defined for. We're careful above to have convertNounPhrase only return these two types of sentences, precisely so this funtion will work.

> combineNVSents :: LogicSentence -> LogicSentence -> LogicSentence
> combineNVSents (ForAll t npDescription) vpDescription
> = ForAll t (npDescription `Implies` vpDescription)
> combineNVSents (Exists t npDescription) vpDescription
> = Exists t (npDescription `And` vpDescription)

Nothing new here.

Now we can load this post into a Haskell interpreter (I'm using ghci) and try it out:

ghci> convertSentence iWin
Exists (Variable "x") (And (Atom "speaker" [Variable "x"]) (Atom "win" [Variable "x"]))

I win.

 

On Makerfaire

Well, we a-traveled to Austin this past weekend to take part in MakerFaire.

Rather than show you photos of what was there, I thought I'd scan in some gestures from my sketchbook. Gesture drawing is something that we'll be coming to (eventually) in the how-to-draw posts, but for the moment, suffice it to say that gestural drawing is a way to capture a person or thing as quickly as possible; important in these circumstances because everyone was a-movin' and a-shakin'.


It's not a terribly long drive to Austin from here, but long enough that we drove well past sunset Friday night. I drew things in the dark. This is one place and time when your blind contour drawing is more than just an exercise. I particularly like this one, because it was drawn as we passed the truck; you can see I drew clockwise from the right, and by the time I got back around to the wheels, they were beside us instead of in front.



The next morning we grabbed coffee before heading out to the Faire; the fairground opened at 10:00, so we had plenty of time. Lisa had some trouble getting a truly dry cappuccino, but the wait staff was eager to remedy the problem. Scarily chipper. Really.



The human-sized mousetrap was impressive --- I got a front-row seat to the first run. This was just before the actual performance; the young man was about to make his stage debut as the strongest boy in the world. He did a fine job.

It was an interesting point, though, that very, very few of the performers at the faire were particularly good showmen. All the tech and engineering was excellent --- really neat --- but if you didn't already know how it worked and why it was so impressive, the presentation would have been a bit off-putting. Several performances had everything right and were just missing a P.T. Barnum to turn it into a real piece of buskering.

When hats were passed, I am sure that they suffered because of that.




There was a lot to see, and much of it is recorded elsewhere. I'm hoping more to capture the spirit of the place than give an exact recounting of what we saw. The highlights for me were the Mice Pace Maze --- a maze made entirely out of sound. I wished it had been much bigger; the concept is really lovely to me. Hats off the them. Cyclecide's guitar/bike machine was also much fun. I think my favorite part, though, was just wandering and listening to people talking, exchanging ideas, learning new skills, and building community. Many of my sketches were just people talking.

It's my hope that next year, that sense of community-building is enhanced. Many of the booth-persons stuck to such a rigid script that it was hard to get into a real conversation. The times when that shell cracked were far more exciting. A lot of time was spend chatting with the people willing to chat.




After Makerfaire on Saturday, we drove up to Dallas, where some of the group went clubbing. I wasn't that well aquainted with downtown Dallas, so I went for a walk. We agreed to meet back at a cafe where this man was on the wait staff.



It was pretty late. While I walked I spent some time thinking on what I had seen at makerfaire, and about the nerdy community in general. It has always been striking to me that only some people are interested in how things work, and that only some are interested in how they express themselves. Ti seems to me that whatever our occupations and whatever our interests, we should understand what we are doing, and do it with a practiced body and a focused mind. Even if you make washers in a nut-bolt-and-washer factory, you ought to make washer-making into an art. Make masterpieces of your life.

When I got tired of walking, I sat under an overpass for a while. Then it was time to head back to the cafe for hot chocolate.


After Dallas we did the Modern and the Kimbell in Fort worth. I might write another post about what we saw and said there, but I think I've said enough.

This was drawn while getting still more coffee, and wondering at how many people are apparently fueled entirely by the stuff.

I don't know whether I discovered anything new this weekend; but time will tell. As a church sign told me at 2:00AM, "This is a test, Joe Clifford."



21.10.08

 

More 10/15/08 Progress

A decent week, if unnecessarily loaded down with homework... Also, it has become apparent that my neighbors expect life to stop for football games.

Motor Drivers:
I have become irritated with the motor driver offerings to the hobby community (and the educational community for that matter). Your choices? Realistically Pololu and IFI. This is unacceptable.

In response I have started designing motor drivers. Everything from the 10A range to 100-300A. Parts are on the way, samples have been shipped, and donations have been collected from friends. I hope to have at least one finished before the Spring semester. Units will be sold at a minimal markup; software and schematics will be made open source.


Underwater ROV:
  • Poured float from urethane foam to allow for near-neutral buoyancy and minimum compression at depth.
  • Finished modifications to propeller hubs and mounted fourth motor.

Linear Accelerator:
  • New coil tested. 3.5" long coil, 3 layers, 14awg tried as 1st stage. Resulting velocities were significantly less than the previous coil(4 layers, approx 2.5" long 14awg) which had achieved 6.5J Kinetic Energy at over 20m/s.
  • I must finish construction of a "V-switch" using 2 SCR banks. Held up by tight budget and lack of high current IGBT drive optoisolators.
  • Got the idea of expanding the V switch out to multiple legs and using either a longer coil or additional coils on the same stage(if that makes sense).
Centaur:
A late night wiring "correction" bypassed a voltage regulator, putting ~10VDC unregulated to the 5VDC "regulated" power bus. Casualties included two MaxSonar's. As a result, I will include a zener diode + fuse with any power bus containing valuable electronics on future projects. It was fortunate my GPS was not wired during the incident and the more than a dozen Dynamixel servos are rated to over 12VDC.

I made progress on a few other projects not deserving of their own section(at this time). My Matlab simulation of obstacle avoidance using RL is working with only 4 bit numbers. Prepare for a RL robot running no code. "Hard-wired for learning?" you ask... that's right. Also, I re-attached my other walker's(cricket?) head because it looked very depressing laying on the ground, connected only by its "spinal cord".

16.10.08

 

Calling Shots for 10/15

My grade for last week's called shots: B-.

I did get them both, just not as thoroughly as I wanted. My post on "where I'm at" became part I, and I had some errors with generated parses. On the other hand, I did get some fodder for an upcoming post entitled "Computers say the darndest things."

For this week:
  • Subject Verb agreement. I'll be completely removing results for now where the subject and verb don't agree. I'll be bringing them back later on when I introduce scoring for results, because sometimes a person speak bad. In the meantime, I'm hoping to work with smaller, more manageable sets of parses while I work with other problems like relevance and context.
  • Further word shenanigans. Nouns can be adjectives: "clown car," "text file," and "blog post." Words can also be built from existing words as well: "bloggy," "blogger," and "bloggily" all communicate meaning, even if we've just invented the word "blog.
  • NLP, Part II

15.10.08

 

10.15.08 Hackjam

Discussed physics, nanowrimo, a little haskell and a little C.

By discussing physics I mean I introduced the group to Fantastic Contraption, and very little got done ;). If you haven't played fantastic contraption, you ought to give it a try; it is a nice pure example of what engineering is. It's certainly better than forcing your kids to build yet another bridge --- there is other engineering in the world than bridge building!

We also got a few more heads interested in nanowrimo --- National Novel Writing Month. The goal is to write 50,000 words in the 30 days of November. It is an incredibly beneficial excersize. We talked about methods of writing --- whether to plan out each scene, or write as you fancy at the moment. I have written with very little planning the past three years, but failed to finish the past two. I'm going to try some more extensive planning this year and we'll see what happens.

This weekend: Makerfaire. I'll do my best to write a few posts from there.


On calling shots:

I made two of three of my shots for this week, and that ain't bad.

For next week:
  • Post on Makerfaire
  • Post another drawing excersize

And now off to bed.

 

On the Livescribe Pulse

The Pitch

The Livescribe Pulse is an e-pen; it allows you to take notes while recording simultaneous audio, and then uplaod both the notes and the audio to your computer.

For instance, you're sitting in a hackjam, and someone says "Oh, a Lagrangian inverted hapgood might be able to solve that problem." You're scribbling math in your notebook as best you can, but you've never heard of a Lagrangian inverted hapgood (for good reason) --- so you make a little note: "soln?" and keep working.

Later, when you get back home, you tap "soln?" with the tip of your pen, and the disembodied voice of your friend repeats "Oh, a Lagrangian inverted hapgood might be able to solve that problem." You happily google the phrase and discover what you needed to know.

Much sillier, but also more fun, is the built in piano. With a few strokes of the livescribe, you can draw a single octave piano --- and then play it with the tip of the pen!

The Product:

The pen comes in a nice box of a reasonable size; inside is the pen, a simple manual (a single folded page), a carrying case for the pen, headphones, a lanyard for the pen, replacement ink cartridges, and a spiral-bound notebook.

The pen has only one button, which the manual explains should be pushed. The pen came charged, and turned on after about two seconds boot time.

Setting the date, and time is an amusing experience --- in the cover of the notebook is a page printed with a calculator and various function keys --- including a left/right handed switch to control the direction of the display (hooray!). The time and date are set by tapping the appropriate 'buttons' on this printed page.

A reasonable tutorial walks you through how to use the pen. At the bottom of each page of the notebook, there is a set of printed controls --- record, pause, stop, time, speed, and volume. Tapping on record begins recording, and anything you write (on any page of the notebook) is tied to what you record as you record. If you want to hear something again, just tap on the note (down to the individual stroke) and listen to exactly what was happening when you drew that line. Or, if you like, turn on the optional latency, and hear what happened starting 5 seconds before you put ink there.

The pen can perform calculator functions in two ways --- by using the scientific(ish) calculator in the front cover of the notebook, or by accessing the calculator function by drawing a 'nav plus' (a big + sign) anywhere in the notebook, starting the calculator, and then writing simple arithmetic: write "24*36=" and the pen's display will alert you that the answer is 864.

The handwriting recognition is quite good; I had no trouble with incorrect readings in the limited vocabulary that the pen currently uses.

The desktop application is another matter. It works only in windows (still no luck with virtualization for me, though some claim that VMWare does the trick). While one can export pages as PDFs, there is little opportunity to take the images or the sound out of the Livescribe program and use them. The search ability (which uses handwriting recognition to search a whole notebook of notes for key words) works fine --- not brilliantly, but just fine.

There is an online portion of the Livescribe application of which I cannot speak --- my native windows machine is not on the interwebs.

How it Works:

The pen's workings are rather clever. The pen contains an ARM9 processor, a OLED display, a pressure sensor, and an tiny infrared camera which points at the tip of the pen. Each page of each notebook (you can use as many as four at once) is printed with a pattern of tiny (.3mm) dots called the anoto pattern. Any five by five section of the anoto pattern (about 3mm^2) is uniquely identified by the pattern of dots. Capturing the pattern with the camera allows the pen to identify its location on a sub-mm level.

Everything else is just clever programming.

The Pros:
  • It does exactly what it says it does
  • Excellent on-pen interface.
  • HIGH wow factor
  • Large capacity (1 or 2 GB)
  • Audio is clear
  • Notes are legible
  • An on-pen application development suite is coming -- and is in pre-release now. <--- VERY exciting. Why I bought the pen.
The Cons:
  • Windows only
  • Desktop application is nearly useless. Good only for archiving notebooks you're replacing
  • Cost: $150-200 US
  • Battery life: 1-2days. Charge time: 1-2 hours.
What I Think Should Change:

I'd love to see .svg, jpg, and .png export of pages, and SOME kind of export of audio.

The pen is completely round. It rolls off of everything.

The pen has no cap --- only a full carrying case.

Livescribe is making a lot of vauge promises about applications (Spanish translation, full handwriting recognition) and coming-soon features (the ability to print your own paper --- notebooks are $5 apiece and up). From what I can tell, livescribe expects the Pulse to be able to heal the sick and expel daemons by the end of this year. But they have not released a timeline. Lots of big talk, but they won't say when it'll all actually be done. That's worrying me a lot guys. I'm happy enough to wait even a year for some of those abilities; just tell me that it's gonna take that long. Don't vaguely suggest that it might be done by this December.

There you have it. The Livescribe Pulse. Available online and at Target for ~$150 and $200, depending on memory capacity. Notebooks are 4 for $20.

14.10.08

 

Natural Language Processing - Part I

I went to see Iron Man back in May when it came out. It was a fun movie and it definitely satisfied my inner comic nerd but the first words out of my mouth when we left the theater were, "I have some software to write." Since then, I've been working on a small portion of that software: a natural language interface for a computer, a sort of natural language shell.

The first stab was a naive one. It worked in a subset of english where every word had only one meaning and every sentence had only one possible parse. I thought I knew how bad of a limitation I had placed on myself, but I wanted to start building an approximate solution and get experience in the problem space. It turned out that I underestimated the limitations I was working under and had to abandon that approach sooner than I had hoped. Before I stopped, however, I had a system that I could make statements to, ask questions of, and even tell to launch programs, provided I was careful in my wordings.

One sentence would be read in at a time, parsed according to a BNF grammar, and classified as declarative, imperative, or inquisitive. Declarative sentences would be added to the knowledge base (KB). There was no validation on what was added; the system could be fed two inconsistent statements and it'd take both as gospel. Answering questions involved a search of the KB for an answer. Yes/no questions did a backward substituion search for satisfiability and "what is" questions searched for facts in the KB that answer the question. So given: "All men are mortal", and "Socrates was a man", it could answer the question "Was Socrates a mortal?" with "Yes." and "Who was Socrates?" with "A man." Imperative sentences were recognized, and if the verb of the sentence was "run" and the object a constant (names like "emacs" that weren't in the dictionary were treated as constants), it would try to run a program with that constant's name in the background.

Just over two months ago, I started from scratch. (I had been learning Haskell as I wrote the first system, so even the code that had reusable functionality was a mess.) Through the magic of Monads, the new parsing code is about 40% smaller and returns a set of all the interpretations for a sentence it can come up with. This set gets much larger than I expected. Just introducing the ability to interpret any word as a name explodes the number of possible responses. The program shows the sentence "Emacs is a program that opens text files" as having 23 unique parses. Now, there's a lot of those 23 that can be discarded through checking some form of subject verb agreement. What's left can even be ignored given a parse that assumes less names, so it looks like there's still a workable solution there. In the worst cases, the system will have to deal with a nondeterministic KB until either more context is available to make the sentence clearer, or the system can ask questions.

This is an interesting problem in a lot of ways. More next week.

11.10.08

 

More from 10/8/08

Montana's still working on his grid evaluation computing thing. I've long forgotten what he calls it. From what I understand, he's got functions that evaluate constants, but realizes he needs functions that can evaluate references. It seems like he's making progress lately, so I'm hoping we can get him to post what he's up to.

So I'm working on a font based on my handwriting. It's something I've wanted for a while as a novelty item, but I've been pleased with how well it's working out. It's nice to have a font that my brain associates with drafts, notes to myself, and unfinished stuff. I'm hoping to have it in a usable state for the start of Nanowrimo so I can put it into an extended test.

I did not quite make my shot for the week. I made progress in the form of a couple of design breakthroughs, but not much in the form of code aside from recognizing plural forms of nouns, and even that was crude. I've got a three day weekend here, so I should do better this week.

My called shots for this week:
  • Most sentences converted to a (possibly large) set of possible logical meanings
  • A post describing where I'm at with this thing.

 

Drawing exersize

I tried writing a few paragraphs about why I think people should learn to draw --- communicating ideas, self expression, recording memories --- and it seemed like so much fluff. It comes down to this: I bet you've said, "I wish I could draw."

Gaining the ability to draw realistically (and even photorealistically) is not hard ; you will need to devote some time to it, however. For this first exersize, you'll need to set aside 20-30 minutes of quiet time alone. I don't recommend music, and if there will be other people, avoid conversation. Alone is best.

You will also need a pen --- ballpoint is fine --- and a nice big piece of paper. You can do this on 8.5x11, but it's much more rewarding on big paper. I'll be doing my example on a page that's nearly 2'x3'.

Set up a comfortable place to sit; you'll want to be able to sit up pretty straight, and be able to reach your paper easily.

Enough preparation, eh? Read all the instructions first:
  1. Place your pen in your writing hand and lightly touch the tip to the center of your paper.
  2. Sit so that you face away from your paper, but your drawing hand can still comfortably reach the page. You should not be able to see it at all.
  3. With your non-writing hand, make a nice relaxed shape; curl your fingers as if you're holding something, or pointing lightly. Just keep it very relaxed.
  4. Now without looking at the paper, begin to draw your hand. Let your eye trace along the exterior outline, very slowly, taking in each bump and curve. As your eye moves, try and move your pen in the same way --- copying each little bump. When you've done the outline, then start working on the little grooves and interior lines.
  5. Take the full 20-30 minutes and try and record every little detail. NO PEEKING. Please, I beg of you, resist the urge to look. Just let the pen move unobserved, and don't worry about the result. Chances are you'll be bored silly after about 10 minutes. Resist the urge to stop --- this is exersize! Keep pushing yourself to find new lines, new curves. Never stop drawing --- if you must, redraw the lines you've already done.
Go ahead. Do it! Reading what you were supposed to learn without doing the exercise is futile --- come back and read the rest when you're done.


Done? Good! Here's mine:A masterwork, no? If yours looks as little like a hand as mine does, I congratulate you --- you didn't peek even once! (Note that for clarity, after my 20 minutes were up I traced directly over the primary contours again --- the ones around my hand.) Right now you're probably despairing eve being able to draw --- and yelling at me about unreasonable constraints, ridiculous time limits, and difficult subject matters.

Tough beans.

There were several purposes to this exersize. None of those purposes was to make you look like Leonardo. Here are some reasons why I made you suffer through that:
  1. Hand-eye coordination. If you can write, you have enough hand-eye coordination to draw. But learning to sync your hand to your eye when they are not pointed in the same direction is a little like patting your stomach and rubbing you head: not hard once you get the hang of it, but it takes a bit of time. You just spent 20 minutes forcing your hand to follow your eye.
  2. Observation NOT classification. One of the greatest roadblocks to realistic drawing is labeling. As long as you continue to see a hand as four fingers and a thumb, you'll never draw it accurately. Blind contour drawing (which is what you just did) forces you to think in terms of lines and curves; you can't tell whether you're drawing a finger because you can't see what you're drawing. You can only concentrate on what the pen is doing right now.
  3. Confidence. I know that that might seem paradoxical, to say you gained confidence from making such a godawful rendition of a hand --- but think of the last time you drew something. Did you use pencil? Did you erase much? How frustrated were you during the process --- and with the result? Now think about how you felt and thought during this drawing. You spent 20 minutes drawing a hand. I hope you felt relaxed during the process --- even meditative. You didn't erase once, because you were using pen, and you couldn't see what you were doing anyway. And you should feel good about your result, too. You drew in pen. You drew blind. And I bet there are recognizable bits in there, aren't there?
Try doing one of these a day for a few days. Don't worry about improvement --- just notice the calm, trance-like state that prolonged observation creates; during later exercises, you'll want to remember what that feels like.

[Note: for those of you who are looking up "blind contour" --- this exersize is a modified blind contour, because we are including many interior lines, which are not technically contours. Doing a pure blind contour is also worth a try, and is much faster. Do just what we did here, but only draw the outline --- no interior curves at all. It should only take a few minutes at most.]

9.10.08

 

Hack Jam: 10.8.08

Discussion: typography, drawing, and the library of our dreams.

Font was on the table because Adam's been working on a font for the coming nanowrimo; for tasks of that nature, several of us use FontForge. Fontforge has a miserable interface; it's highly unintuitive, uses multiple windows that cannot be docked, and is all around a hassle to use. However, it is open source software -- and is pretty much the ONLY free or even reasonably cheap software that will allow you to make the most of what the TrueType and OpenType standard have to offer in terms of kerning pairs, ligatures, and hinting. Powerful but not agile or intuitive? The story of open source.

We also talked about how unfortunate it was that so few pieces of software allow for the use of these features even when they are included in a font; Adobe products remain nearly the only bastion of font flexibility --- outside, of course, the ever miraculous Latex.

I mentioned that I had offended an art student by mentioning that I thought it was worth any artist's time to learn to draw. In my opinion, the ability to communicate visually, to see objects with a draftsman's eyes, is enough excuse. But still further, it is expected of you --- if you say you're an artist, lay people assume that means you can draw. As Adam put it: "When someone asks 'Can you draw that?', 'No' is the boring answer." I brought up Betty Edwards' Drawing on the Right Side of the Brain which is a book of exersizes based on a neuro-psychological understanding of how draftsmen draw; I recommended her methods as pedagogical breakthroughs which ought to be applied but, at least in my experience, have not been.

On calling my shots:
I did not get the Livescribe working with virtualization; I did get the pen working on a native windows system, and it is recognized by a VirtualBox machine, but the LiveScribe Desktop installer throws an unrecoverable error when attempting to communicate with the pen. Will try VMPlayer.

This week I call several small things:
  • A post reviewing the Livescribe.
  • A post with a right-brained drawing excersize you can do at home
  • Screen-print a t-shirt for Maker faire.

3.10.08

 

Fastbootin' Linux

A couple of links are in order regarding recent progress made in booting a linux system faster. Linux developers Arjan van de Ven and Auke Kok gave a presentation at the recent Linux Plumbers conference on booting an Asus eee pc in 5 seconds (video). That's five seconds to usable desktop with processor and disk idle, but no, that doesn't include bios posting. I'm not sure how long that is on a eee. Here's the most detailed article covering the presentation, and here's the ppt itself.

I've been playing around with some of the techniques they used this week. I had pruned my init scripts sometime last year to get a 15 second boot time, though that had climbed up to the 25 second range with my new laptop and new hardware. I've gotten it back down below 20 seconds by applying the available kernel patches in Arjan's fastboot .git tree and modularizing the non-critical part of my kernel. There's three major avenues to pursue to remove more time on my box. I still want to understand why there's a 3 second pause in the kernel loading process that wasn't there on my old laptop. There's a new X.org server that should improve startup time somewhat. I should be able to use super readahead to improve IO throughput in bootup (and possibly preload firefox as well?).

The presentation was done from systems installed with Fedora and Moblin. From what I read, these improvements will end up in most other distributions as well. The kernel patches may make it into 2.6.28 (earlyish 2009), the improvements made to X should make it into the next release of X.org.

I'm putting this all aside for a little while and get back to working on English language processing this weekend; I'll write up more about exactly what I'm doing with that soon. As a target for Wednesday, I'll commit to making significant progress, but I'm in an exploring stage, so I'm won't committing to what that will entail.

2.10.08

 

Hack Jam: 1.10.08

Topics of discussion: the two envelope problem, the livescribe Pulse, slackware bootup times.

Adam brought up a neat examination of a mircocosm within the two envelopes problem:

Select a random number from the positive reals. Now select another. What are the chances that the second is greater than the first?

(Note that what follows is from my mouth -- it is not necessarily Adam's opinion or intention with this example.)

I see several resolutions to this problem. The first cheats, so we'll start there.

Make your first pick; call that number A. Due to the uncountably infinite nature of the reals, there are as many real numbers between zero and a as there are between A and the infinite (think of a function with a vertical asymptote, like tangent --- tan(x) for x from 0 to pi/4 maps to y from 0 to infinity). Therefore, it is equally likely that your next selection will be greater as it will be less --- any A divides R+ into two equal parts, so the answer to our original question is 1/2.

Why does this result cheat? Because the paradox returns if we change from R, the reals, to the natural numbers (1, 2, 3...). Then the infinity trick fails; there is only one number between 0 and 2, and still an infinite number between 2 and infinity.

We can also employ a different cheat --- redefining probability. Mathematicians that subscribe to "frequency probability" define probability as the number of occurances divided by the number of trials. If you flip a coin 100 times, and it comes up heads 57 times, then the probability of it coming up heads is .57. As the number of trials (flips) approaches infinite, then the frequency definition equates to the classical definition of probability. Using the frequency definition solves one big part of the paradox: the expected value of a random selection between one and infinity.

That expected value is infinite --- but no matter how many times you make the selection, your actual return will be a finite number --- 0% of your expected value. Even if you take billions of trials and average them, your actual return will never be infinite. It helps here to keep in mind that 'infinity' is not a number, it is a limit. Our random selection will not return 'infinity' no matter what; just very large numbers.

So how does frequency probability dissolve that paradox? By rejecting the problem definition. If you were able to to 10 trials of selecting a random natural (or real) number between zero and infinity, one of those selections would be the highest. As far as frequency probability is concerned, that number is the maximum possible value. The infinite never enters the equation; and if you change the infinity in the original problem to some number, the answer becomes easily 1/2.

This leads me to believe that the entire paradox stems from the even simpler problem: select a random positive natural number. Such a thing is certainly physically impossible, but I don't want to reject it just for that. But untli the paradox of expected value versus average return is resolved, I think that the original envelopes paradox is contained in many respects in this (admittedly more abstract) simpler question.



My updates:

In the last week I got Hack Jam Log Book up and running.

For next Wednesday, I call getting a livescribe Pulse running via virtualization on a linux box.

This page is powered by Blogger. Isn't yours?

Subscribe to Posts [Atom]