Towards concept analysis
BB( B)
in categories:limit inferior as algebra,limit superior as coalgebra
AToshiki Kataoka A&The University of Tokyo,
JSPS Research Fellow( A)Dusko Pavlovic

University of Hawaii at Manoa

Overview•

Concept analysis••

Concept analysis in categories

new problem

Dedekind–MacNeille completion•

Generalizations of Dedekind–MacNeille completion•

Bicompletions of categories

Limit superior and limit inferior as algebras

2

new answer

Toshiki Kataoka (UTokyo, JSPS)Concept Analysis(or, knowledge acquisition,
semantic indexing,
data mining)Example: Text Analysis
CorpusCo-occurrenceThis is a pen. Is that a pen?
…

writedrawpen

thispencilaProximity among words
thispenapple

eatpencil

bananadelicious

bananaLimit superior and limit inferior as algebras

4

Toshiki Kataoka (UTokyo, JSPS)Concept Analysis•

Given data in a matrix•

Extract information as vectors
PQ

RAlice✔

✔

✔

Bob✔

✔

between twoS

✔

Dan✔

Limit superior and limit inferior as algebras

QP

CarolEveeither side✔
5AB

RCSDE

Toshiki Kataoka (UTokyo, JSPS)Formal Concept Analysis[Wille, 1982]•Preordered

Concept lattice

PQRAlice✔

✔

✔

Bob✔

✔

SCarol✔

Dan✔

Eve✔

<{A,B,C,D,E}, {}><{A,B},{P,Q}><{C,D,E},{S}><{A},{P,Q,R}><{}, {P,Q,R,S}>
Limit superior and limit inferior as algebras

6

Toshiki Kataoka (UTokyo, JSPS)Latent Semantic Analysis(Principal Component Analysis)•P[0:0:0:1:1]

M =U V†

Linear algebraic[ 1 : 2 : 1 : 0 ]QAlice

★★

★★★

Bob★★

★★
★★★

RS★★★★

U=★★
★★★

CarolDan

★★★★

Eve

★

1M=
5220003
50004000000541

where=

0000148
500001212†Limit superior and limit inferior as algebras

162616V =700042500142442
1420
152
50001051212

singularvectors

singular
value

000

Toshiki Kataoka (UTokyo, JSPS)Towards Unification•Fixed points (definition)•Completeness (theorem)•Minimality (theorem)

Limit superior and limit inferior as algebras8Toshiki Kataoka (UTokyo, JSPS)Factorizations of RelationsQPABRCminimal
complete latticethat factorize
the relation

SDLimit superior and limit inferior as algebras

E
9Toshiki Kataoka (UTokyo, JSPS)Singular Value
Decomposition•Compact SVD: M = UΣV†•

M: (given) real m×n matrix, rank r•

U: m×r matrix, U†U = Ir•

V: n×r matrix, V†V = Ir•

Σ: diagonal r×r matrix•with positive reals on the diagonal

Limit superior and limit inferior as algebras

10Toshiki Kataoka (UTokyo, JSPS)Factorizations ofReal Matrices{P, Q, R, S}
2525355545000000000000554515{A, B, C, D, E}

000

152
50

100R4R3R500

142
442
1420=

48
5000

42
5000

10
5R3

1212011leastdimension
to factorize{X, Y, Z}=0Limit superior and limit inferior as algebras

†162
61612
12

{X, Y, Z}

000Toshiki Kataoka (UTokyo, JSPS)Concept Analysisin Categories

Components andFunctionalities
Functional modules

Structural components…

Limit superior and limit inferior as algebras

13

Toshiki Kataoka (UTokyo, JSPS)

Engineering•

Functionalities: top-down•

Components: bottom-up
V-model•Relation:
specification

image by Herman Bruyninckx
https://commons.wikimedia.org/
wiki/File:V-model-en.png(under GFDL)

Limit superior and limit inferior as algebras

14

Toshiki Kataoka (UTokyo, JSPS)

Reverse-Engineering•

Want to know

Components•Functionalities

Limit superior and limit inferior as algebras

Can be observed
Components15Functionalities

Toshiki Kataoka (UTokyo, JSPS)

Reverse-Engineering•

Want to know

Components•

Functionalities

Limit superior and limit inferior as algebras

Can be observed
Components

16

Functionalities

Toshiki Kataoka (UTokyo, JSPS)

Actions on Relations
…

…

…

…

•
•

From super-components
From sub-functionalities

Limit superior and limit inferior as algebras

17

op:A

B

Set

Toshiki Kataoka (UTokyo, JSPS)Dedekind–MacNeilleCompletionDedekind Cuts
R = { L, U | Q = Llwhere {< q}, {U, L, U = ,L. uq}{LLimit superior and limit inferior as algebras[Dedekind, 1872]

U. l u}/q}, {> q} (qQ)

U19

Toshiki Kataoka (UTokyo, JSPS)Dedekind–MacNeilleCompletion[MacNeille, 1937]•(P, ≤): poset
P = { L, U | L

L, U•

L ,UP, UP,

L = {l P | u
U = {u P | lL

lower
boundsL

U. l
L. lu},u}}UU

Q |rR}

upper
boundsGeneralizes Dedekind cuts

Q = { ,Q }
={}

{{Rr}

{ }

Limit superior and limit inferior as algebras

Q, {20r}{ Q,Toshiki Kataoka (UTokyo, JSPS)}

An Example
P = { L, U | L is lower bounds of U ,U is upper bounds of L}

PP(Hasse diagrams)
Limit superior and limit inferior as algebras

21

Toshiki Kataoka (UTokyo, JSPS)Categorically•(P, ≤): poset,•(↓P, ⊆) (resp. (↑P, ⊇)):the family of lower (resp. upper) sets•

P: fixed point ofthe Galois connection

PPP
P

Limit superior and limit inferior as algebras

22

Toshiki Kataoka (UTokyo, JSPS)Properties•P is inf- and sup-complete. (Complete lattice)•P → P is an inf- and sup-dense embedding.
••Thus, sup- and inf-preserving

The minimal bicompletion

Limit superior and limit inferior as algebras23

sup (and inf)
existing in P

Toshiki Kataoka (UTokyo, JSPS)

Generalizations ofDedekind–MacNeilleCompletion

Completions of Relations•Φ ⊆ P × Q: relation
QQ

PP

s.t. x’ ≤ x, xΦy, y ≤ y’x’Φy’

PPP
PLimit superior and limit inferior as algebras

25

Toshiki Kataoka (UTokyo, JSPS)

Notations• C: V -enriched category,•C = [Cop , V]: category of presheaves,•

C = [C, V]op : category of postsheaves,•:C• AC,:CB denotes A

Limit superior and limit inferior as algebras

op

C: Yoneda embeddings,
B

V.

26

Toshiki Kataoka (UTokyo, JSPS)

Isbell Completion•V = {0,1} (V-category = poset)••

C: Dedekind–MacNeillecompletion

V = [0,∞] (V-category =Lawvere metric space)•C: (directed) tight span[Willerton, 2013]

Limit superior and limit inferior as algebras

27

CC

H

H

C

Isbell duality

Toshiki Kataoka (UTokyo, JSPS)CIf V = [0,∞]B

BCCHHCCAA

Q

PQPPP

Limit superior and limit inferior as algebras

PP28

Toshiki Kataoka (UTokyo, JSPS)Quantitative ConceptAnalysis[Pavlovic, 2012]•A

Lawvere metrized
PQ

Alice

★★

★★★

Bob★★

★★
★★★

RS

B
Q

★★★★
l3Carol

★★
★★★

Dan

★★★★

l3

A

l5

l4

l3

D
l4

l5
l5

l2
Q

R

E=

l3

l5

P

P

DEB

l1
l2

C

l5

★

Eve

B

l4S

l4

RCAd(A, P ) = l2 , d(A, Q) = l3 , . . .
where 0l5···l 1 < l0 =Limit superior and limit inferior as algebras

=P29

Q

R

Toshiki Kataoka (UTokyo, JSPS)S

Bicompletionsof Categories

Question by Lambek•(1966)

Does there exist•

an inf- and sup-dense embedding to•

an inf- and sup-complete category?

Limit superior and limit inferior as algebras

31

Toshiki Kataoka (UTokyo, JSPS)Answer by Isbell•(1968)

Any inf- and sup-dense embedding of
the group Z4 is not inf-complete (nor sup-complete)

Limit superior and limit inferior as algebras

32

Toshiki Kataoka (UTokyo, JSPS)Two Universalities•Cannot be a single self-dual universality

PP

L

Limit superior and limit inferior as algebras

33

Toshiki Kataoka (UTokyo, JSPS)Trouble with V = Set
B

✘✘A

Q

B
CC

H

HCA

PQ

PPC

P

Limit superior and limit inferior as algebras

PP

34

Toshiki Kataoka (UTokyo, JSPS)Our Proposal
H

B

B

C( B)

CA

A

C

H

H

( A)

( C) HC( C) H

H

Q

P

Q

PP

P

Limit superior and limit inferior as algebras

PP

35

Toshiki Kataoka (UTokyo, JSPS)

Supremum along
Discrete Fibration• lim F = lim F (F : JC, F : CopSet)

limdiagonal
functorCC

JlimYoneda
embedding

CCJFFC

Limit superior and limit inferior as algebras

36

Toshiki Kataoka (UTokyo, JSPS)Limit inferior•

The supremum of lower bounds
lim F := lim H FlimCCJCC

JFF

limCC
H F

Limit superior and limit inferior as algebrasH

37

Toshiki Kataoka (UTokyo, JSPS)

Theorems• ( C)

H

is the free lim-completion of C.

• C( C) H is lim- and lim-preserving.

Limit superior and limit inferior as algebras

38

Toshiki Kataoka (UTokyo, JSPS)Example:
Completing Groups
H(G-Set)G

op{1}{I · G | ISet}({1}{G · I | ISet})opH

HGop -Set
H
Limit superior and limit inferior as algebras

39

Toshiki Kataoka (UTokyo, JSPS)Example:
Completing Posets
H

PP

PP

H

H( P)

H

P

P( P )HH
Limit superior and limit inferior as algebras

40

Toshiki Kataoka (UTokyo, JSPS)

Summary•

Algebras, instead of fixed points•

Factorization (future work)•Add limits inferior••

Not always limits superiorBB( B)

AA( A)

Minimality (future work)

Limit superior and limit inferior as algebras

41

Toshiki Kataoka (UTokyo, JSPS)References•

Isbell, John R. "Small subcategories and completeness."
Theory of Computing Systems 2.1 (1968): 27-50.

•

Lambek, Joachim. "Completions of Categories: Seminar
lectures given 1966 in Zürich." Springer Berlin Heidelberg,1966.

•Pavlovic, Dusko. "Quantitative concept analysis." Formal
Concept Analysis. Springer Berlin Heidelberg, 2012. 260-277.

•Wille, Rudolf. "Restructuring Lattice Theory: An Approach
Based on Hierarchies of Concepts." Ordered Sets. Springer
Netherlands, 1982. 445-470.

Limit superior and limit inferior as algebras

42

Toshiki Kataoka (UTokyo, JSPS)