際際滷

際際滷Share a Scribd company logo

Mathematics of Incidence (part 4): Lattice dependencies

Benjamin Keller
Benjamin Keller

Motivated by a simple example of collaborative filtering from previous presentations, we look at what it means to be dependent and independent in formal concept analysis, and what the limitations are for deciding how "strong" a dependency might be. Along the way, we catch a glimmer of how association rules arise from the concept lattice, and get a hint that we might need some information theory.

1 of 26
Downloaded 11 times
Mathematics of Incidence part 4: Lattice dependencies Benjamin J. Keller bjkeller.github.io linkedin.com/in/bjkeller v.1.1, 7 November 2014 m a1 g1 g2 g3 g4 Creative Commons Attribution-ShareAlike 4.0 International License g5 g8
sr(a) s s2 s1 t l a u1 u2 uk un(a) Recall: CF and dependency Recommend t to a by composing formal concepts for selection of users {ui } and items { si } Correspond to filter and ideal that capture dependencies Intuition: good recommendation determined by strong dependency [note: ideal and filter are dual, so good enough to define for one b/c other will be same]
Independence in concept lattice apples doughnuts Abby X David X apples doughnuts Abby David no shared objects/attributes
Definition: anti-chain An anti-chain in lattice L is a subset of elements S L where for all p, q 2 S both p6錚 q and q6錚 p apples doughnuts Abby David
Dependencies apples Abby X Brian X apples Abby, Brian apples cherries Abby X Brian X X apples Abby cherries Brian apples cherries grapes Abby X X Brian X X apples grapes Abby cherries Brian
Definition: chain A chain in lattice L is a subset of elements S L where for all p, q 2 S either p 錚 q or q 錚 p apples Abby cherries Brian apples grapes Abby cherries Brian bananas apples doughnuts cherries eggs Brian David Charles Abby
Definition: join and meet For lattice elements p, q 2 L the join of p and q is the least element p _ q 2 L satisfying both p 錚 p _ q and q 錚 p _ q the meet of p and q is the greatest element p ^ q 2 L satisfying both p ^ q 錚 p and p ^ q 錚 q
(In)dependence apples grapes Abby cherries Brian (Abby) _ (Brian) (dependent) 亮(grapes) ^ 亮(cherries) (independent) Is there a shared object/attribute?
Strong Dependency Not clear what strong means Intuitively, Abby and Brian would have a stronger dependency if they shared enough common likes What does lattice look like if we add more common likes? apples grapes Abby cherries Brian
Strong Dependency Adding common likes just increases number of items labeling top of lattice Lattice structure doesn't change These attributes are redundant from the perspective of constructing the lattice apples bananas doughnuts eggs flautas grapes Abby cherries Brian
Repeating is redundant apples Abby apples Abby, Brian apples Abby, Brian,Charles apples Abby X apples Abby X Brian X apples Abby X Brian X Charles X apples cherries Abby X Brian X X apples bananas cherries Abby X X Brian X X X apples Abby cherries Brian apples,bananas Abby cherries Brian cherries Abby Brian X Abby cherries Brian
Strong Dependency FCA is the wrong math to define strength of dependency Concept lattice only tells us independent or not Can construct a minimal (reduced) context that maintains lattice structure without redundancies Strength basically means mutually informative Information constrained by lattice structure, but determined by counts [Topic for a different set of slides]
Attribute implications Define implication A ! B for A,B M whenever 亮A 亮B Can be read as every object with attributes in A, also has attributes in B Rules defined this way capture same relationships as lattice some trivial, some more interesting
apples bananas cherries Abby X Brian X X Charles X X X apples Abby bananas Brian cherries Charles cherries ! cherries cherries ! bananas cherries ! apples bananas ! bananas bananas ! apples apples ! apples cherries, bananas ! apples
m a1 a2 a3 g1 X X X X g2 X X X g3 X X X g4 X X X g5 X X X m a1 a2 a3 g2 g3 g4 g5 g1 A = {a1, a2, a3} Let then have implications B ! ai for ai 2 B A B [ m ! m for B A
m a1 a2 a3 g1 X X X X g2 X X X g3 X X X g4 X X X Let A = {a1, a2, a3} ai, aj 2 A, i6= j then have implications aj ! aj ai, aj ! aj m ! m aj,m ! m ai, aj,m ! m but also have a1, a2, a3 ! m m g2 g3 g4 g1
m a1 a2 a3 g1 X X X X g2 X X X g3 X X X g4 X X X g5 X g6 X g7 X g8 X X g9 X X g10 X X Yields the same implications including a1, a2, a3 ! m m a1 a2 a3 g5 g6 g7 g2 g3 g4 g1 g8 g9 g10
Flavors of implications Implication is A ! B B A for A,B M where either bananas, cherries ! bananas read as people who like bananas and B6 A something else, like bananas cherries ! bananas read as people who like cherries like bananas First is boring, second corresponds to association rules
Pointer: Association Rules An association rule A ) B is a pair of sets A,B M such that B6= ; and A B = ; Evaluated in terms of confidence: | A [ B| | B| FCA used for frequent item set mining to find association rules
Defintion: Interval (P,錚) p, q 2 P [p, q] = {r 2 P | p 錚 r 錚 q} Let be a poset, then the interval for is [ponder: how would you write a principal filter or ideal as an interval?]
Intervals and implications The implication a1, a2, a3 ! m corresponds to [亮{a1, a2, a3}, 亮m] where interval 亮{a1, a2, a3} = 亮{a1, a2, a3,m} m a1 a2 a3 g2 g3 g4 g1
Abby and those pesky doughnuts bananas apples doughnuts cherries eggs Brian David Charles Abby A minimal set of implications cherries ! apples apples ! bananas doughnuts ! bananas cherries ! doughnuts eggs ! doughnuts Shorter chains seem better, but are these rules enough to say what is a good recommendation?
Questions to ponder What information does a formal concept carry? Can we use a measure of it to define strong dependency? How does strength of dependency relate to implications? We can recommend doughnuts and cherries to Abby, but which first?
Corrections 11.7.14: had drawn lattice on slide 16 incorrectly
About me and these slides I am Ben(jamin) Keller. I learn and, sometimes, create through explaining. I had been involved in a big (US) federally funded project that had the goal of helping biomedical scientists tell stories about their experimental observations. The project is long gone, but Im still trying to grok how such a thing would work. Much of biological data comes in the form of observations that are distilled to something that looks like an incidence relation, which brings us to this series of presentations. My goal for the slides is to deal with the mathematics and analysis of incidence in an approachable way, but the intuitive beginnings will eventually allow us to embrace the more complex later.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

More Related Content

Mathematics of Incidence (part 4): Lattice dependencies

  • 1. Mathematics of Incidence part 4: Lattice dependencies Benjamin J. Keller bjkeller.github.io linkedin.com/in/bjkeller v.1.1, 7 November 2014 m a1 g1 g2 g3 g4 Creative Commons Attribution-ShareAlike 4.0 International License g5 g8
  • 2. sr(a) s s2 s1 t l a u1 u2 uk un(a) Recall: CF and dependency Recommend t to a by composing formal concepts for selection of users {ui } and items { si } Correspond to filter and ideal that capture dependencies Intuition: good recommendation determined by strong dependency [note: ideal and filter are dual, so good enough to define for one b/c other will be same]
  • 3. Independence in concept lattice apples doughnuts Abby X David X apples doughnuts Abby David no shared objects/attributes
  • 4. Definition: anti-chain An anti-chain in lattice L is a subset of elements S L where for all p, q 2 S both p6錚 q and q6錚 p apples doughnuts Abby David
  • 5. Dependencies apples Abby X Brian X apples Abby, Brian apples cherries Abby X Brian X X apples Abby cherries Brian apples cherries grapes Abby X X Brian X X apples grapes Abby cherries Brian
  • 6. Definition: chain A chain in lattice L is a subset of elements S L where for all p, q 2 S either p 錚 q or q 錚 p apples Abby cherries Brian apples grapes Abby cherries Brian bananas apples doughnuts cherries eggs Brian David Charles Abby
  • 7. Definition: join and meet For lattice elements p, q 2 L the join of p and q is the least element p _ q 2 L satisfying both p 錚 p _ q and q 錚 p _ q the meet of p and q is the greatest element p ^ q 2 L satisfying both p ^ q 錚 p and p ^ q 錚 q
  • 8. (In)dependence apples grapes Abby cherries Brian (Abby) _ (Brian) (dependent) 亮(grapes) ^ 亮(cherries) (independent) Is there a shared object/attribute?
  • 9. Strong Dependency Not clear what strong means Intuitively, Abby and Brian would have a stronger dependency if they shared enough common likes What does lattice look like if we add more common likes? apples grapes Abby cherries Brian
  • 10. Strong Dependency Adding common likes just increases number of items labeling top of lattice Lattice structure doesn't change These attributes are redundant from the perspective of constructing the lattice apples bananas doughnuts eggs flautas grapes Abby cherries Brian
  • 11. Repeating is redundant apples Abby apples Abby, Brian apples Abby, Brian,Charles apples Abby X apples Abby X Brian X apples Abby X Brian X Charles X apples cherries Abby X Brian X X apples bananas cherries Abby X X Brian X X X apples Abby cherries Brian apples,bananas Abby cherries Brian cherries Abby Brian X Abby cherries Brian
  • 12. Strong Dependency FCA is the wrong math to define strength of dependency Concept lattice only tells us independent or not Can construct a minimal (reduced) context that maintains lattice structure without redundancies Strength basically means mutually informative Information constrained by lattice structure, but determined by counts [Topic for a different set of slides]
  • 13. Attribute implications Define implication A ! B for A,B M whenever 亮A 亮B Can be read as every object with attributes in A, also has attributes in B Rules defined this way capture same relationships as lattice some trivial, some more interesting
  • 14. apples bananas cherries Abby X Brian X X Charles X X X apples Abby bananas Brian cherries Charles cherries ! cherries cherries ! bananas cherries ! apples bananas ! bananas bananas ! apples apples ! apples cherries, bananas ! apples
  • 15. m a1 a2 a3 g1 X X X X g2 X X X g3 X X X g4 X X X g5 X X X m a1 a2 a3 g2 g3 g4 g5 g1 A = {a1, a2, a3} Let then have implications B ! ai for ai 2 B A B [ m ! m for B A
  • 16. m a1 a2 a3 g1 X X X X g2 X X X g3 X X X g4 X X X Let A = {a1, a2, a3} ai, aj 2 A, i6= j then have implications aj ! aj ai, aj ! aj m ! m aj,m ! m ai, aj,m ! m but also have a1, a2, a3 ! m m g2 g3 g4 g1
  • 17. m a1 a2 a3 g1 X X X X g2 X X X g3 X X X g4 X X X g5 X g6 X g7 X g8 X X g9 X X g10 X X Yields the same implications including a1, a2, a3 ! m m a1 a2 a3 g5 g6 g7 g2 g3 g4 g1 g8 g9 g10
  • 18. Flavors of implications Implication is A ! B B A for A,B M where either bananas, cherries ! bananas read as people who like bananas and B6 A something else, like bananas cherries ! bananas read as people who like cherries like bananas First is boring, second corresponds to association rules
  • 19. Pointer: Association Rules An association rule A ) B is a pair of sets A,B M such that B6= ; and A B = ; Evaluated in terms of confidence: | A [ B| | B| FCA used for frequent item set mining to find association rules
  • 20. Defintion: Interval (P,錚) p, q 2 P [p, q] = {r 2 P | p 錚 r 錚 q} Let be a poset, then the interval for is [ponder: how would you write a principal filter or ideal as an interval?]
  • 21. Intervals and implications The implication a1, a2, a3 ! m corresponds to [亮{a1, a2, a3}, 亮m] where interval 亮{a1, a2, a3} = 亮{a1, a2, a3,m} m a1 a2 a3 g2 g3 g4 g1
  • 22. Abby and those pesky doughnuts bananas apples doughnuts cherries eggs Brian David Charles Abby A minimal set of implications cherries ! apples apples ! bananas doughnuts ! bananas cherries ! doughnuts eggs ! doughnuts Shorter chains seem better, but are these rules enough to say what is a good recommendation?
  • 23. Questions to ponder What information does a formal concept carry? Can we use a measure of it to define strong dependency? How does strength of dependency relate to implications? We can recommend doughnuts and cherries to Abby, but which first?
  • 24. Corrections 11.7.14: had drawn lattice on slide 16 incorrectly
  • 25. About me and these slides I am Ben(jamin) Keller. I learn and, sometimes, create through explaining. I had been involved in a big (US) federally funded project that had the goal of helping biomedical scientists tell stories about their experimental observations. The project is long gone, but Im still trying to grok how such a thing would work. Much of biological data comes in the form of observations that are distilled to something that looks like an incidence relation, which brings us to this series of presentations. My goal for the slides is to deal with the mathematics and analysis of incidence in an approachable way, but the intuitive beginnings will eventually allow us to embrace the more complex later.
  • 26. This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.