Feature structure and minikanren?

[Amirouche Boubekki]

Héllo,


Did anyone implement minikanren for feature structure?


Best!


Amirouche aka. amz3

[Jason Hemann]

I think these can be encoded using trees, yes? (Wiki seems to also suggest so, if I'm reading that correctly). I know of no implementations that implement feature constraints presently, but I know those have been investigated in other contexts. 

JBH

--
You received this message because you are subscribed to the Google Groups "minikanren" group.
To unsubscribe from this group and stop receiving emails from it, send an email to minikanren+unsubscribe@googlegroups.com.
To post to this group, send email to minik...@googlegroups.com.
Visit this group at https://groups.google.com/group/minikanren.
For more options, visit https://groups.google.com/d/optout.

--

JBH

[Dan Friedman]

I agree with Jason, processing alists (even split alists)i standard fare.  

Nested alists might want some constraints  Haven't given that observation

much thought.

... Dan

[Chung-chieh Shan]

But we want the alists
((a . _.0) (b . y))
and
((b . _.1) (a . x))
to unify, yielding the mgu
((a . x) (b . y))
or equivalently
((b . y) (a . x))

And we want the alists
((a . x))
and
((b . y))
to unify, yielding the same mgu as above.

So the only way I know to encode (even unnested) feature structures
using trees is to map each feature name to a globally fixed address
in a binary tree. For example if we decide globally that "a" maps
to the address (left left right) and "b" maps to the address
(left right right left) then the alist above
((a . _.0) (b . y))
can be encoded by the tree
(((_.2 . _.0) . (_.3 . (y . _.4))) . _.5)

Maybe this is what Jason has in mind? It's related to expressing
memoization as a lazy data structure.

On 2016-12-24T12:07:14-0500, Dan Friedman wrote:
> I agree with Jason, processing alists (even split alists)i standard fare.
> Nested alists might want some constraints Haven't given that observation
> much thought.
>

> On Sat, Dec 24, 2016 at 11:08 AM, Jason Hemann <jason....@gmail.com>
> wrote:
> > I think these can be encoded using trees, yes? (Wiki seems to also suggest
> > so, if I'm reading that correctly). I know of no implementations that
> > implement feature constraints presently, but I know those have been investigated
> > in other contexts

> > <http://www.sciencedirect.com/science/article/pii/0743106694900442>.

> >
> > On Sat, Dec 24, 2016 at 8:06 AM, Amirouche Boubekki <
> > amirouche...@gmail.com> wrote:
> >
> >> Did anyone implement minikanren for feature structure

> >> <https://en.wikipedia.org/wiki/Feature_structure>?

--
Edit this signature at http://conway.bostoncoop.net/~ccshan/cgi-bin/sig
Information is not knowledge. Knowledge is not wisdom. Wisdom is not truth.
Truth is not beauty. Beauty is not love. Love is not music. Music is THE BEST.
― Frank Zappa

[Jason Hemann]

Ken,

That's on the order of what I was expecting, although it's more sophisticated than I'd figured on. 

* Feature constraints sound promising, but AFAIK not implemented in any Kanrens

* Your encoding is pretty darn cool, but it maybe isn't the clearest way to encode the data.

The other options I'm coming up with are: 

* hack up the unifier and add it there

* implement a feature-structure-unify as a miniKanren relation.

I think the final choice is the traditional way to do this in Prolog, yes? 

JBH

--
You received this message because you are subscribed to the Google Groups "minikanren" group.
To unsubscribe from this group and stop receiving emails from it, send an email to minikanren+unsubscribe@googlegroups.com.
To post to this group, send email to minik...@googlegroups.com.
Visit this group at https://groups.google.com/group/minikanren.
For more options, visit https://groups.google.com/d/optout.

--

JBH

[Matías Guzmán Naranjo]

Hi all,

are there any updates on this topic? Tahnks

To unsubscribe from this group and stop receiving emails from it, send an email to minikanren+...@googlegroups.com.

To post to this group, send email to minik...@googlegroups.com.
Visit this group at https://groups.google.com/group/minikanren.
For more options, visit https://groups.google.com/d/optout.

--

JBH

[Amirouche Boubekki]

Hello Matías,

On Sunday, November 18, 2018 at 9:31:24 PM UTC+1, Matías Guzmán Naranjo wrote:

Hi all,

are there any updates on this topic? Tahnks

Do you have reference about feature structure you are talking about?

Is it the same thing that is described in http://www.nltk.org/howto/featstruct.html?

[Amirouche Boubekki]

On Saturday, December 1, 2018 at 4:24:31 PM UTC+1, Amirouche Boubekki wrote:

Hello Matías,

On Sunday, November 18, 2018 at 9:31:24 PM UTC+1, Matías Guzmán Naranjo wrote:

Hi all,

are there any updates on this topic? Tahnks

Do you have reference about feature structure you are talking about?

Is it the same thing that is described in http://www.nltk.org/howto/featstruct.html?

FWIW, My latest work on this subject boils down to  mimicking more of datomic, as a simpler than RDF triple store.

I started my experiments with GNU Guile, but I am moving to Chez Scheme. Like I said, previously my work is around

a database that you can query (recursively) using minikanren.

I did not find enough papers about feature structures per se to know how they are useful. My understanding is that

you can implement feature structures in my database. E.g the following feature structure taken from wikipedia:

   { category :  noun phrase, agreement: { number: singular, person: third}}

Can be encoded a set of three tuples (subject, predicate, object):

  

   (P4X432, category noun, phrase)
   (P4X432, agreement, ZXP202)
   (ZXP202, number, singular)
   (ZXP202, person, third)


Then you can query it using minikanren using a specific -o procedure here a full example with data:

(test-check "microkanren fs:queryo"
  (with-env (env-open* "wt" (list *feature-space*) "create")
    ;; fixture
    (let* ((concept/fruit (fs:add! (list '(name . "fruit"))))
           (concept/strawberry (fs:add! (list '(name . "strawberry"))))
           (concept/fig (fs:add! (list '(name . "fig"))))
           (link/strawberry-is-a-good-fruit (fs:add! (list `(from . ,concept/strawberry)
                                                           `(name . "is good")
                                                           `(to . ,concept/fruit))))
           (link/fig-is-a-good-fruit (fs:add! (list `(from . ,concept/fig)
                                                    `(name . "is good")
                                                    `(to . ,concept/fruit)))))
      ;; execute query
      (sort (map car
                 (run* (name?)
                   (fresh (concept?? link?? a-fruit-that-is-good??)
                     (fs:queryo concept?? 'name "fruit")
                     (fs:queryo link?? 'to concept??)
                     (fs:queryo link?? 'name "is good")
                     (fs:queryo link?? 'from a-fruit-that-is-good??)
                     (fs:queryo a-fruit-that-is-good?? 'name name?))))
            string<)))
  '("fig" "strawberry"))

The query anwser the question : what fruit is good? Which boils down to follow relation along a predefined path. This is a example of neighborhood querying, recursive queries are also possible but I did not find a good example / real life example of such query.

I am super thrilled to work together on this if you don't mind sharing some of your knowledge regarding this subject.

Also you might be interested by https://github.com/webyrd/mediKanren/

Best regards,

Amirouche

[Matías Guzmán Naranjo]

Hi Amirouche,

yes, those are the feature structures I am talking about. Your idea for representing them seems interesting, I am wondering whether you have a solution for unification? Say I have [Agr [number sg]] and want to unify it with [Agr [person 1]], it should produce: [Agre [number sg, person 1]] (where order doesn't matter). However, it should fail if I want to unify [Agr [number sg]] [Agr [number pl]]. Ideally, it should also run in reverse: I should be able to ask what [Agr [number sg]] needs to unify with to produce [Agr [number sg, person 1]].

Can your system do this?

Best,

[Amirouche Boubekki]

Le sam. 1 déc. 2018 à 17:00, Matías Guzmán Naranjo <morte...@gmail.com> a écrit :

Hi Amirouche,

yes, those are the feature structures I am talking about. Your idea for representing them seems interesting, I am wondering whether you have a solution for unification?

 

Maybe the term unification is misleading here. That's why I asked the question initially. I also asked the question because I am interested in NLP and feature structures seems to be thing in this field. But I failed to find more ressources to better understand the use cases.

Quick answer is that it doesn't do unification in terms of feature structures. It does unification of triples with a semantic that *looks* like SPARQL (without support for OPTIONAL).

Say I have [Agr [number sg]] and want to unify it with [Agr [person 1]], it should produce: [Agre [number sg, person 1]] (where order doesn't matter).

However, it should fail if I want to unify [Agr [number sg]] and [Agr [number pl]].

But it could unify with [Agr [number sg, gender f]]?

 

Ideally, it should also run in reverse: I should be able to ask what [Agr [number sg]] needs to unify with to produce [Agr [number sg, person 1]].

That is an interesting problem.

 

Can your system do this?

My system narrow the search space. So indeed, if you want to know everything that can unify with [Agr [number sg]] you *could* query every every facts that are an Agr (instead of all the facts) and then filter manualy those that don't have [number sg] or have something else and do that recursively... In theory it's possible to do such thing I guess.

Like I said previously, it can not do feature-structure unification as-is. To support that last query it requires a minikanren with constraints support (and possibly to support bigger than RAM dataset it would require streamable solutions).

I will come back to this subject at some point, but the lack of real-world problem to solve doesn't make it appealing.

[Matías Guzmán Naranjo]

> Maybe the term unification is misleading here.

Well, that's how they call it ;). They are extremely useful when working with grammatical formalisms which make use of them (HPSG, LFG, TAG, etc. ). If you're doing statistical NLP they are not all that useful, but they are at the core of symbolic NLP.

> But it could unify with [Agr [number sg, gender f]]?

yes

> My system narrow the search space. So indeed, if you want to know everything that can unify with [Agr [number sg]] you *could* query every every facts that are an Agr (instead of all the facts) and then filter manualy those that don't have [number sg] or have something else and do that recursively... In theory it's possible to do such thing I guess.

Not sure why you think the search would have to be that deep and complex. To me it feels like it should be like the `appendo` example, where once you define a relational append, it can run backwards just fine. Once one defines `unifyo` relationally it should be able to do the search backwards, no?

> I will come back to this subject at some point, but the lack of real-world problem to solve doesn't make it appealing.

Well, it would be useful for people like me working on symbolic NLP, who want to write relational parsers. I will work on it using your representation, I was trying to do it using lists: (Agr (number sg) (person 3)), but I couldn't figure it out.

--

[Apocalypse Mystic]

Hi,

If your problem will fit the tree-based encoding, that is definitely the easiest way to do it. If not, you could probably hack the unifier and maybe get better performance or something, but probably the best place to start would be by just writing a (feature-structure-unify A B C) relation as mentioned above. I haven't implemented this, so perhaps I'm overlooking something (caveat emptor), but I would think you would just need to iterate through features in A, and for each one check it against each feature in B. If they unify, unify them (recursively feature-unify them) and add the result to C. If they don't (disequality constraint), keep looking through the features of B. At the end of B's features, you would check whether the feature has yet been added to C, and if not, just add the feature. Same process for B, perhaps with some pre-checking to see if A has already added that  feature to C. Have you tried something like this and encountered any particular problems?

Incidentally, I'm also working on NLP in minikanren, and I'm curious to know what you're doing with it, if you don't mind sharing.

Cheers,

Evan

[Matías Guzmán Naranjo]

Hi Evan,

you're idea almost works (at least how I implemented it), thank you! Forward unification works as expected, but backward queries get stuck in infinite loops with run*. The system doesn't seem to be able to figure out that there is a finite number of solutions. Any ideas on how to fix this on the code below?

Since you asked. I am working on a formal theory of proportional analogy for HPSG. So it's mostly theoretical stuff I want to be able to check with the computer, nothing really 'practical'.

----

;; unifies f1 with l2
(define unify-f-with-list°
  (lambda (f1 l2 out)
    (conde
     [(== '() l2) (== `(,f1) out)]
     [(fresh (la ld a2 d2 a1 d1 res)
         (=/= '() l2)
         (== `(,la . ,ld) l2)
         (== `(,a2 . ,d2) la)
         (== `(,a1 . ,d1) f1)
         (conde
          [(== a2 a1)
           (== `(,res . ,ld) out)
           (unify° f1 la res)]
          [(fresh ()
              (=/= a2 a1) ;; if not
              (== `(,la . ,res) out)
              (unify-f-with-list° f1 ld res))]))])))

(define unify-list-with-list°
  (lambda (l1 l2 out)
    (conde
     [(== '() l1) (== l2 out)]
     [(== '() l2) (== l1 out)]
     [(fresh (a1 d1 res)
         (=/= '() l1)
         (== `(,a1 . ,d1) l1)
         (unify-f-with-list° a1 l2 res)
         (unify-list-with-list° d1 res out))])))

(define unify°
  (lambda (f1 f2 out)
    (conde
     [(== f1 f2) (== f1 out)]
     [(fresh (a1 d1 a2 d2)
         (=/= f1 f2)        
         (== `(,a1 . ,d1) f1)
         (== `(,a2 . ,d2) f2)
         (== a1 a2)
         (fresh (res)
            (unify-list-with-list° d1 d2 res)
            (== `(,a1 . ,res) out)))])))

(run* (q)
      (unify° '(a (c b) (e d)) '(a (e d) (c) ) q))

(run* (q)
      (unify° '(a (c b) (e d)) '(a (e d) (c b) ) q))

(run* (q)
      (unify° '(a (c b) (e d)) '(a (e d) (c b) ) q))

(run* (q)
      (unify° '(a (c b)) '(a (c b) (d e) ) q))

(run* (q)
      (unify° '(a (c (x d))) '(a (d e) (c (g o))) q))

(run* (q)
      (unify° '(a (c (x d))) '(a (b d)) q))

(run 2 (q)
     (unify° '(a (c (x d))) q '(a (b d) (c (x d)))))

(run 3 (q)
     (unify° '(a (c (x d))) q '(a (b d) (c (x d)))))

(run 4 (q)
     (unify° '(a (c (x d))) q '(a (b d) (c (x d)))))

;; this one is the problem here

(run* (q)
      (unify° '(a (c (x d))) q '(a (b d) (c (x d)))))

[Apocalypse Mystic]

Not off hand, although maybe if you commented what you thought the code was doing it would become clear. What sort of structure do your features have? I'm not 100% sure I'm reading those tests correctly.

[Matías Guzmán Naranjo]

Right. I'll try. So the feature structures are lists, and I am assuming the car of a feature structure is a symbol eg. (a (b c) (d e)). To unify two feature structures f1 and f2 (say (a (b c) (d e)) with (a (b c) (f g)) with unify°, we first test to see whether they are equal, if they are, then their unification is either one of them and `out` unifies with f1 (it could as well be f2). If they are not we make sure their car is equal (otherwise they can't unify), and call unify unify-list-with-list° on their cdrs (in this case ((b c) (d e)) and ((b c) (f g)), the result is unified to `res`, and the final answer is the car of f1 consed to res.

unify-list-with-list° calls unify-f-with-list° with the car of the first list ((b c)) and the second list ((b c) (f g)). And repeats for all elements of the first list.

unify-f-with-list° tries to unify the the feature f1 ((b c)) with the list l1 ((b c) (f g)). It does so how you suggested, it checks for the first member of l1((b c)) whether the car of f1 is the car of said member (in this case it is), if it is, it tries to unify bot features structures by calling unify° on them (since in this case they are equal, it returns (b c) ). If it succeeds, it returns the result of their unifications consed to the rest of l1. If both cars are not the same, it goes on to the next item in l1. If we get to the end, it just means that f1 was not in l1, and we can return it, and it will be added to the end of l1.

From here the process goes on to try to unify (d e) with our list ((b c) (f g)). Since d is not in any of the members of this list, it returns it and we end up with ((d e) (b c) (f g)). The unification then succeeds with (a (d e) (b c) (f g)).

Now, for the problematic case:

(run* (q)
      (unify° '(a (c (x d))) q '(a (b d) (c (x d)))))

We're asking what feature structured needs to unify with '(a (c (x d))) to produce '(a (b d) (c (x d))). There are several answers: '(a (b d)), '(a (b d) (c)) and '(a (b d) (c (x d))) which minikanren seems to finds, plus some other possibilities which it does not seem to find. Also, as soon as one asks for more, minikanren cannot figure out that there are no more answers and gets stuck.

I've tried reordering the goals, but no luck so far.

My guess is that it may have something to do with returning either f1 or f2 in the first conde line of unify°, and the fact that order in the feature structures shouldn't matter.

In any case, this is pretty close to what I need.

[Apocalypse Mystic]

I suppose I had in mind in-line comments, but this will do. Without offering a complete solution, I look with suspicion at the end of unify-list-with-listo

(unify-f-with-listo a1 l2 res)
(unify-list-with-listo d1 res out)

I would have expected the recursive call to unify-list-with-listo should be called with d1 and l2 rather than d1 and res, because you want to continue comparing the rest of d1 with the full list of features in l2. Res, in turn, I would imagine, is the partially constructed final feature structure, in which case I would sort of imagine something like it being threaded through unify-list-with-listo as an extra argument and only unified with out at the end. But I may misunderstand what unify-f-with-listo is doing. If you wanted to comment that function, I think it would become clear what's going on here. I strongly suspect your divergence problem is a bug rather than a goal ordering issue.

As a side note, I believe it is redundant to declare

(=/= '() l2)
(== `(,la . ,ld) l2)

Since asserting that l2 is a non empty pair will already imply that it is not an empty list.