- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] NLP libraries and tools?
by wren ng thornton 07 Jul '11

07 Jul '11

On 7/6/11 5:58 PM, Aleksandar Dimitrov wrote: > On Wed, Jul 06, 2011 at 09:32:27AM -0700, wren ng thornton wrote: >> On 7/6/11 9:27 AM, Dmitri O.Kondratiev wrote: >>> Hi, >>> Continuing my search of Haskell NLP tools and libs, I wonder if the >>> following Haskell libraries exist (googling them does not help): >>> 1) End of Sentence (EOS) Detection. Break text into a collection of >>> meaningful sentences. >> >> Depending on how you mean, this is either fairly trivial (for English) or >> an ill-defined problem. For things like determining whether the "." >> character is intended as a full stop vs part of an abbreviation; that's >> trivial. > > I disagree. It's not exactly trivial in the sense that it is solved. It is > trivial in the sense that, usually, one would use a list of know abbreviations > and just compare. This, however, just says that the most common approach is > trivial, not that the problem is. Perhaps. I recall David Yarowsky suggesting it was considered solved (for English, as I qualified earlier). The solution I use is just to look at a window around the point and run a standard feature-based machine learning algorithm over it[1]. Memorizing known abbreviations is actually quite fragile, for reasons you mention. This approach will give you accuracy in the high 90s, though I forget the exact numbers. [1] With obvious features like whether the following word is capitalized, whether the preceding word is capitalized, length of the preceding word, whether there's another period after the next word,... >> But for general sentence breaking, how do you intend to deal with >> quotations? What about when news articles quote someone uttering a few >> sentences before the end-quote marker? So far as I'm aware, there's no >> satisfactory definition of what the solution should be in all reasonable >> cases. A "sentence" isn't really very well-defined in practice. > > As long as you have one routine and stick to it, you don't need a formal > definition every linguist will agree on. Computational Linguists (and their > tools,) more often than not, just need a dependable solution, not a correct one. But the problem is that what constitutes an appropriate solution for computational needs is still very ill-defined. For example, the treatment of quotations will depend on the grammar theory used in the tagger, parser, translator, etc. The quality of output is often quite susceptible to EOS being meaningfully[2] distributed. Thus, what constitutes a "dependable" solution often varies depending on the task in question.[3] Also, a lot of the tools in this area assume there's some sort of punctuation marking the end of sentences, even if it's unreliable as an EOS indicator. That works well enough for languages with European-like orthographic traditions, but it falls apart quite rapidly when moving to East Asian languages (e.g., Burmese, Thai,...). And languages like Japanese or Arabic can have "sentences" that go on forever, but are best handled by chunking them into clauses. [2] In a statistical sense, relative to the structure of the model. [3] Personally, I think the idea of having a single EOS type is the bulk of the problem. If we allowed for different kinds of EOS in grammars then the upstream tools could handle sentence fragments better, which would make it easier to make fragment breaking reliable. >> I've been working over the last year+ on an optimized HMM-based POS >> tagger/supertagger with online tagging and anytime n-best tagging. I'm >> planning to release it this summer (i.e., by the end of August), though >> there are a few things I'd like to polish up before doing so. In >> particular, I want to make the package less monolithic. When I release it >> I'll make announcements here and on the nlp@ list. > > I'm very interested in your progress! Keep us posted :-) Will do :) -- Live well, ~wren

2 1

Re: [Haskell-cafe] NLP libraries and tools?
by wren ng thornton 07 Jul '11

07 Jul '11

On 7/6/11 6:45 PM, Aleksandar Dimitrov wrote: > One hint, if you ever find yourself reading in quantitative linguistic data with > Haskell: forget lazy IO. Forget strict IO, except your documents aren't ever > bigger than a few hundred megs. In case you're not keeping the whole document in > memory, but you're keeping some stuff in memory, never keep it around in > ByteStrings, but use Text or SmallString (ByteStrings will invariably leak space > in this scenario.) Learn how to use Iteratees and use them judiciously. I definitely agree with the iteratees comment, but I'm curious about the leaks you mention. I haven't run into leakiness issues (that I'm aware of) in my use of ByteStrings for NLP. -- Live well, ~wren

2 1

GHC/ARM registerised port
by Karel Gardas 07 Jul '11

07 Jul '11

Hello, Stephen Blackheath, David Terei and me are working together on ARM registerised port of GHC. The port is using LLVM as a code generator and is kind of working already. (GHCi support still missing) If you are curious and would like to try the code, please read last two paragraphs containing instructions what to do here[1]. This blog[2] is my personal attempt to document the project at least from my point of view. If you would just like to go straight to the code for code review or to follow progress directly, then github.com repo[3] is the right link for you. Thanks for testing, bug reporting and/or patches! Karel [1]: http://ghcarm.wordpress.com/2011/07/06/armv7-thumb-vfpv3-support-and-github… [2]: http://ghcarm.wordpress.com/ [3]: https://github.com/kgardas/ghc

1 0

[Haskell-Cafe] Constructive Probability Theory and RandProc's σ-algebras
by Edward Kmett 07 Jul '11

07 Jul '11

On Sun, Jul 3, 2011 at 11:05 AM, David Banas <dbanas(a)banasfamily.net> wrote: > v0.4 of `RandProc` has just been posted to Hackage: > http://hackage.haskell.org/package/randproc [NB: I transfered this discussion from haskell to haskell-cafe, and started another thread] I have been spending some time exploring constructive probability theory in Haskell, and I have a couple of observations about working with random processes in a constructive setting: Necessarily because you are working in Haskell, a constructive setting, your σ-algebras can't be actual σ-algebras! =/ Notably, they aren't closed under *countable* union/intersection/complement, but merely finite union/intersection/complement, and Gray and Davisson's horrified objections from the bottom of page 39 on Random Processes applies: If a class of sets is only a field rather than a σ-field, that is, if it > satisfies only (3.1) and (3.2), then there is no guarantee that the class > will contain all limits of sets. Hence, for example knowing that a class of > sets contains all half-open intervals of the form (a,b] for a and b finite > does not ensure that it will also contain points or singleton sets! In fact, > it is straightforward to show that the collection of all such half-open > intervals together with the complements of such sets and all finite unions > of the intervals and complements forms a field. The singleton sets, however, > are not in the field. (See exercise 3.4) > Thus if we tried to construct a probability theory based on only a field, > we might have probabilites defined for events such as (a,b) meaning "the > output voltage of a measurement is between a and b" yet not have > probabilities defined for a singleton set {a} meaning "the output voltage is > exactly a." By requiring that the event space be a σ-field instead of only a > field, we are assured that all such limits are indeed events. This limitation, while from some perspective annoying is intrinsic to tackling the problem intuitionistically. Practically, this means you need to be careful when rederiving most of the later results, because you are limited to what you can prove in a constructive measure theory. In particular the approaches of YK Chan, Brian Weatherson, and Glenn Shafer to intuitionistic probability theory are probably appropriate reading. Personally, I don't think this is all that bad, we get some nice properties by being in a constructive setting. Weatherson noted that your measure becomes additive without problems from Dutch book arguments in an intuitionistic setting, because P(A v not A) is not necessarily 1! You may recall that recall that additivity would imply that P(A v B) = P(A) + P(B), given that A and B are disjoint, but that it tends to fall apart in classical probability theory. Intuitionistically, however, this is fine. That is to say that if you placed bets that payed out with market rate interest at a rational booking agent on both whether P = NP and P /= NP, it isn't just as good as having placed a bet on truth, because intuitionistically it is possible that neither of those bets may ever pay out, but in a classical setting P (P = NP v P /= NP) = P(True) = 1, so we lose additivity to gain the excluded middle. The cost of additivity is giving up or refining a lot of results from that text that talk about the limit of a random process. That and that the "σ-fields" in question are mere fields. ;) I am interested in exploring the consequences of this further. -Edward

2 1

Re: [Haskell-cafe] NLP libraries and tools?
by wren ng thornton 07 Jul '11

07 Jul '11

On 7/6/11 8:46 PM, Richard O'Keefe wrote: >> I've been working over the last year+ on an optimized HMM-based POS >> tagger/supertagger with online tagging and anytime n-best tagging. I'm >> planning to release it this summer (i.e., by the end of August), though >> there are a few things I'd like to polish up before doing so. In >> particular, I want to make the package less monolithic. When I release it >> I'll make announcements here and on the nlp@ list. > > One of the issues I've had with a POS tagger I've been using is that it > makes some really stupid decisions which can be patched up with a few > simple rules, but since it's distributed as a .jar file I cannot add > those rules. How horrid. I assume the problem is really that the trained model is in the jar and you can't do your own training? Or is this a Brill-like tagger where you really mean to add new rules? If an HMM-based tagger is amenable, you could try switching to Daniël de Kok's Java port of TnT: https://github.com/danieldk/jitar The tagger I'm working on does support being hooked up to a Java client (i.e., consumer of tagging info), but it's fairly ugly due to Java's refusal to believe in IPC. -- Live well, ~wren

1 0

Haskell Weekly News: Issue 189
by Daniel Santa Cruz 07 Jul '11

07 Jul '11

Welcome to issue 189 of the HWN, a newsletter covering developments in the Haskell community during the week of June 26 to July 2, 2011. It seems that it was a pretty quiet week in the mailing list. There were no significant announcements made, and the number of threads was low by comparison. Hope everyone is having a great week! You can find the HTML version at: http://contemplatecode.blogspot.com/2011/07/haskell-weekly-news-issue-189.h… Quotes of the Week * iwtu: [#haskell] is a good channel. Really. People are helpful and don't deserve killing or eating * [Cale] Finite dimensional vector spaces over a field F are algebras for the monad of F-linear combinations of elements of a set. [ivanm] oooohhhhh.... _now_ I get you! * [quicksilver] C++ templates can embed arbitrary computation at compile time [quicksilver] that alone tells you something about the complexity of the compiler [edwardk] yeah. they were accidentally turing complete. (whoops!) ;) [quicksilver] edwardk: OOPS I ACCIDENTALLY THE WHOLE TARPIT * bos: other companies use expensive firewalls and crypto hardware to protect their intellectual secrets. edwardk uses category theory! * ManuelChakravarty: After all, you can import any C function with a pure type which also allows you to wreak arbitrary havoc. We enable the user to disguise arbitrary machine code as a Haskell function of essentially arbitrary type. In comparison, `unsafePerformIO' seems angelic. * NihilistDandy: The best part of Haskell is that 80% of module names can be turned into clever blog titles. * AlanPerlis: We will never run out of things to program as long as there is a single program around. Top Reddit Stories * Here be dragons: advances in problems you didn't even know you had Domain: serpentine.com, Score: 78, Comments: 8 On Reddit: http://goo.gl/4RC1W Original: http://goo.gl/Pc0nd * A Gentle Introduction to Category Theory Domain: citeseerx.ist.psu.edu, Score: 33, Comments: 25 On Reddit: http://goo.gl/nb6yJ Original: http://goo.gl/ItUef * Step-wise evaluation of simple Haskell code to hpaste (via Stepeval) Domain: chrisdone.com, Score: 33, Comments: 4 On Reddit: http://goo.gl/VaPXN Original: http://goo.gl/NhWLC * Debugging compilers with optimization fuel Domain: blog.ezyang.com, Score: 30, Comments: 1 On Reddit: http://goo.gl/uUEct Original: http://goo.gl/tSk0e * Fully-Funded PhD Studentship in Functional Programming Domain: cs.nott.ac.uk, Score: 23, Comments: 5 On Reddit: http://goo.gl/Xa231 Original: http://goo.gl/zIvZe * Using Snap in Production! Domain: cdsmith.wordpress.com, Score: 21, Comments: 20 On Reddit: http://goo.gl/KgKxY Original: http://goo.gl/kZ5hp * Monads from Comonads Domain: comonad.com, Score: 19, Comments: 1 On Reddit: http://goo.gl/1yxKe Original: http://goo.gl/R9PyX * Haskell plugin for IntelliJ IDEA Domain: code.google.com, Score: 18, Comments: 7 On Reddit: http://goo.gl/DUiWy Original: http://goo.gl/H1goQ * Barnes & Hut simulator in Haskell! Domain: mortenlysgaard.com, Score: 16, Comments: 4 On Reddit: http://goo.gl/qTKlT Original: http://goo.gl/a5EAb * How do you deal with "long" function bodies? Domain: self.haskell, Score: 12, Comments: 29 On Reddit: http://goo.gl/sRQy0 Top StackOverflow Questions * Bentley-Ottmann Algorithm in Haskell? votes: 31, answers: 1 Read on SO: http://goo.gl/wyJNY * Haskell approaches to error handling votes: 22, answers: 3 Read on SO: http://goo.gl/I2dVG * is point free code more efficient, or just terser? votes: 16, answers: 2 Read on SO: http://goo.gl/em3uu * Are distinct open and close delimiters syntactically necessary? votes: 9, answers: 7 Read on SO: http://goo.gl/roNWE * How to persist large data for efficient deserialization in Haskell votes: 8, answers: 1 Read on SO: http://goo.gl/ixalr * Building with runtime flags using cabal and ghc votes: 6, answers: 1 Read on SO: http://goo.gl/UyrBs About the Haskell Weekly News To help create new editions of this newsletter, please send stories to dstcruz(a)gmail.com. Until next time, Daniel Santa Cruz References 1. http://www.reddit.com/r/haskell/comments/ic3qx/here_be_dragons_advances_in_… 2. http://www.serpentine.com/blog/2011/06/29/here-be-dragons-advances-in-probl… 3. http://www.reddit.com/r/haskell/comments/icogq/a_gentle_introduction_to_cat… 4. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.7317&rep=rep1&t… 5. http://www.reddit.com/r/haskell/comments/iezj6/stepwise_evaluation_of_simpl… 6. http://chrisdone.com/posts/2011-07-02-stepeval-hpaste.html 7. http://www.reddit.com/r/haskell/comments/iacth/debugging_compilers_with_opt… 8. http://blog.ezyang.com/2011/06/debugging-compilers-with-optimization-fuel/ 9. http://www.reddit.com/r/haskell/comments/ie6by/fullyfunded_phd_studentship_… 10. http://www.cs.nott.ac.uk/~gmh/phd-advert.html 11. http://www.reddit.com/r/haskell/comments/iby54/using_snap_in_production/ 12. http://cdsmith.wordpress.com/2011/06/28/im-using-snap-in-production/ 13. http://www.reddit.com/r/haskell/comments/iao3l/monads_from_comonads/ 14. http://comonad.com/reader/2011/monads-from-comonads/ 15. http://www.reddit.com/r/haskell/comments/ib4zu/haskell_plugin_for_intellij_… 16. http://code.google.com/p/ideah/ 17. http://www.reddit.com/r/haskell/comments/idlza/barnes_hut_simulator_in_hask… 18. http://mortenlysgaard.com/wordpress/?p=17 19. http://www.reddit.com/r/haskell/comments/icelh/how_do_you_deal_with_long_fu… 20. http://stackoverflow.com/questions/6487632/bentley-ottmann-algorithm-in-has… 21. http://stackoverflow.com/questions/6537766/haskell-approaches-to-error-hand… 22. http://stackoverflow.com/questions/6494443/is-point-free-code-more-efficien… 23. http://stackoverflow.com/questions/6542724/are-distinct-open-and-close-deli… 24. http://stackoverflow.com/questions/6556042/how-to-persist-large-data-for-ef… 25. http://stackoverflow.com/questions/6505648/building-with-runtime-flags-usin…

1 0

Re: [Haskell-cafe] NLP libraries and tools?
by wren ng thornton 07 Jul '11

07 Jul '11

On 7/6/11 9:27 AM, Dmitri O.Kondratiev wrote: > Hi, > Continuing my search of Haskell NLP tools and libs, I wonder if the > following Haskell libraries exist (googling them does not help): > 1) End of Sentence (EOS) Detection. Break text into a collection of > meaningful sentences. Depending on how you mean, this is either fairly trivial (for English) or an ill-defined problem. For things like determining whether the "." character is intended as a full stop vs part of an abbreviation; that's trivial. But for general sentence breaking, how do you intend to deal with quotations? What about when news articles quote someone uttering a few sentences before the end-quote marker? So far as I'm aware, there's no satisfactory definition of what the solution should be in all reasonable cases. A "sentence" isn't really very well-defined in practice. > 2) Part-of-Speech (POS) Tagging. Assign part-of-speech information to each > token. There are numerous approaches to this problem; do you care about the solution, or will any one of them suffice? I've been working over the last year+ on an optimized HMM-based POS tagger/supertagger with online tagging and anytime n-best tagging. I'm planning to release it this summer (i.e., by the end of August), though there are a few things I'd like to polish up before doing so. In particular, I want to make the package less monolithic. When I release it I'll make announcements here and on the nlp@ list. > 3) Chunking. Analyze each tagged token within a sentence and assemble > compound tokens that express logical concepts. Define a custom grammar. > > 4) Extraction. Analyze each chunk and further tag the chunks as named > entities, such as people, organizations, locations, etc. > > Any ideas where to look for similar Haskell libraries? I don't know of any work in these areas in Haskell (though I'd love to hear about it). You should try asking on the nlp@ list where the other linguists and NLPers are more likely to see it. -- Live well, ~wren

5 6

(no subject)
by Ian Childs 06 Jul '11

06 Jul '11

Suppose I have two terms s and t of type "a" and "b" respectively, and I want to write a function that returns s applied to t if "a" is an arrow type of form "b -> c", and nothing otherwise. How do i convince the compiler to accept the functional application only in the correct instance? Thanks, Ian

3 7

Arrow instance of function type [a] -> [b]
by Markus Läll 06 Jul '11

06 Jul '11

Hi! Is it possible to define an Arrow instance of list to list functions? Something like import Control.Arrow import Control.Category type X a b = [a] -> [b] instance Category X where id = map Prelude.id g . f = g Prelude.. f instance Arrow X where arr f = map f first f = unzip >>> first f >>> uncurry zip The problem is that it's not allowed to use partially applied type synonyms. It is however possible to define a type synonym which value is a partially applied type, but I haven't been able to figure out if I could somehow use that fact in defining the X... Is it at all possible, or is a newtype the only way to do it? -- Markus Läll

4 3

Automatic Reference Counting
by Thomas Davie 06 Jul '11

06 Jul '11

Hi guys, Apple recently announced a new static analysis in Clang called ARC (Automatic Reference Counting). The idea is to provide what GC provides (zero memory management code by the programmer), but not to incur the runtime penalty of having to have the GC run. It seems to be extremely effective in objective-C land. I was wondering if any of the compiler gurus out there could comment on the applicability of this kind of analysis to Haskell. Dropping the GC and hence stopping it blocking all threads and killing parallel performance seems like nirvana. The one major problem that's still left with ARC is that it does not solve the retain cycle problem of reference counting. Programmers must insert a "weak" keyword to break cycles in their data graphs. Could even this analysis be automated statically? Could we put up with a language extension that added this annotation? I'd love to hear some comments from people more-experienced-than-I on this. Thanks Tom Davie

7 8