text: 16 PIOTR M. HAJAC AND TOMASZ MASZCZYK Lemma 2.4. Let (H, ∆) be a compact quantum group such that the C*-algebra H admits a character. Then, for any n ∈ N \ {0}, there exists an equivariant (cid:126) *-homomorphism from the n-iterated equivariant join A to A := H ∆H. n 1 Proof. If χ : H → C is a character, then ⊗ ⊗ (cid:126) −→ (2.5) f := ev χ id : H ∆H H χ 1 2 is an equivariant *-homomorphism. More generally, applying f to the leftmost χ factor in the n-times iterated equivariant join A , we obtain an equivariant map − n to the (n 1)-times iterated equivariant join A − : n 1 ⊗ − ⊗ ⊗ ⊗ − −→ (2.6) id (n 1) f id (n 1) : A A − . C([0,1]) χ H n n 1 → (cid:3) Composing all these maps, we obtain an equivariant map A A , as desired. n 1 To ﬁx notation, let us begin by recalling the deﬁnition of SU (2) [31]. We take q H = C(SU (2)) to be the universal unital C*-algebra generated by α and γ subject q to the relations ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ (2.7) αγ = qγα, αγ = qγ α, γγ = γ γ, α α+γ γ = 1, αα +q2γγ = 1, ≤ → ⊗ where 0 <(cid:18)q 1. The(cid:19)cop(cid:18)roduct ∆ : C(SU ((cid:19)2)(cid:18)) C(SU (2)) (cid:19) C(SU (2)) q q min q is given by the formula − ∗ ⊗ − ∗ ⊗ ⊗ ⊗ − ∗ α qγ α 1 qγ 1 1 α 1 qγ (2.8) ∆ ∗ = ⊗ ∗ ⊗ ⊗ ⊗ ∗ . γ α γ 1 (cid:18) α 1 (cid:19) 1 γ 1 α We call the matrix − ∗ α qγ (2.9) u := ∗ γ α the fundament(cid:18)al represen(cid:19)tatio(cid:18)n matr(cid:19)ix of SU (cid:18)(2). The c(cid:19)ounit(cid:18)ε and the(cid:19)antipode O q S of the Hopf algebra (SU (2)) are respectively given by the formulas q − ∗ − ∗ ∗ ∗ α qγ 1 0 α qγ α γ (2.10) ε ∗ = , S ∗ = − . γ α 0 1 (cid:18) γ α(cid:19) qγ α Combining the antipode S with the matrix transposition, we obtain the matrix ∗ − ∨ α qγ (2.11) u := S(uT ) = ∗ γ α ##LTLine##

text: PIOTR

text: M.

text: HAJAC

text: AND

text: TOMASZ

text: MASZCZYK

text: Lemma

text: Let

text: (H,

text: be

text: a

text: compact

text: quantum

text: group

text: such

text: that

text: the

text: C*-algebra

text: H

text: admits

text: a

text: character.

text: Then,

text: for

text: any

text: n

text: N

text: there

text: exists

text: an

text: equivariant

text: *-homomorphism

text: from

text: the

text: n-iterated

text: equivariant

text: join

text: A

text: to

text: A

text: H

text: ∆H.

text: n

text: Proof.

text: If

text: χ

text: H

text: C

text: is

text: a

text: character,

text: then

text: f

text: ev

text: χ

text: id

text: H

text: ∆H

text: H

text: χ

text: is

text: an

text: equivariant

text: *-homomorphism.

text: More

text: generally,

text: applying

text: f

text: to

text: the

text: leftmost

text: χ

text: factor

text: in

text: the

text: n-times

text: iterated

text: equivariant

text: join

text: A

text: we

text: obtain

text: an

text: equivariant

text: map

text: n

text: to

text: the

text: (n

text: iterated

text: equivariant

text: join

text: A

text: n

text: id

text: (n

text: f

text: id

text: (n

text: A

text: A

text: χ

text: H

text: n

text: n

text: Composing

text: all

text: these

text: maps,

text: we

text: obtain

text: an

text: equivariant

text: map

text: A

text: A

text: as

text: desired.

text: n

text: To

text: ﬁx

text: notation,

text: let

text: us

text: begin

text: by

text: recalling

text: the

text: deﬁnition

text: of

text: SU

text: We

text: take

text: q

text: H

text: C(SU

text: to

text: be

text: the

text: universal

text: unital

text: C*-algebra

text: generated

text: by

text: α

text: and

text: γ

text: subject

text: q

text: to

text: the

text: relations

text: αγ

text: qγα,

text: αγ

text: qγ

text: α,

text: γγ

text: γ

text: γ,

text: α

text: α+γ

text: γ

text: αα

text: where

text: C(SU

text: C(SU

text: C(SU

text: q

text: q

text: min

text: q

text: is

text: given

text: by

text: the

text: formula

text: α

text: qγ

text: α

text: qγ

text: α

text: qγ

text: γ

text: α

text: γ

text: α

text: γ

text: α

text: We

text: call

text: the

text: matrix

text: α

text: qγ

text: u

text: γ

text: α

text: the

text: of

text: SU

text: The

text: and

text: O

text: q

text: S

text: of

text: the

text: Hopf

text: algebra

text: (SU

text: are

text: respectively

text: given

text: by

text: the

text: formulas

text: q

text: α

text: qγ

text: α

text: qγ

text: α

text: γ

text: ε

text: S

text: γ

text: α

text: γ

text: qγ

text: α

text: Combining

text: the

text: antipode

text: S

text: with

text: the

text: matrix

text: transposition,

text: we

text: obtain

text: the

text: matrix

text: α

text: qγ

text: u

text: S(uT

text: γ

text: α

text: ##LTLine##


text: PULLING BACK NONCOMMUTATIVE BUNDLES 17 of the representation contragredient to the fundamental representation. Note, however, that (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) ∗ − − − ∗ − −1 α qγ 0 q α qγ 0 q (2.12) ∗ = ∗ , γ α 1 0 γ α 1 0 ∨ which means that u and u are equivalent as complex representations for arbi- trary q. Motivated by the classical situation, we denote the n-iterated equivariant join of C(SU (2)) by C(S4n+3). Note that, except for n = 0, our quantum spheres are q q diﬀerent from Vaksman-Soibel’man quantum spheres [30]. Indeed, it follows imme- diately from the deﬁning relations of the C*-algebra of any Vaksman-Soibel’man quantum sphere that its space of characters is always a circle. In contrast, the space of characters of C(S4n+3) always contains the torus Tn+1 appearing as the q Cartesian product of the circles of characters of copies of C(SU (2)) in the iterated q equivariant join. The quaternionic projective space HPn is deﬁned as the quotient space (Hn+1 \ {0})/H× with respect to the right multiplication by non-zero quaternions of non-zero quaternionic column vectors in Hn+1. Observe that the above quoti- enting restricts to quotienting the space of unit vectors S4n+3 ⊂ Hn+1 by the right multiplication by unit quaternions. The latter can be identiﬁed with the group SU(2). Since, for q = 1, the action of (C(SU (2)), ∆) on C(S4n+3) is equivalent to the above standard right SU(2)-action on Sq4n+3 with HPn aqs the space of orbits, we propose the following deﬁnition. Deﬁnition 2.5. We deﬁne the C*-algebra of the n-th quantum quaternionic pro- jective space as the ﬁxed-point subalgebra (cid:8) (cid:9) HP C( n) := C(S4n+3/SU (2)) :=C(S4n+3)SUq(2) q q q q ∈ | ⊗ := b C(S4n+3) δ (b) = b 1 . q C(Sq4n+3) O For the sake of brevity, let us denote the Hopf algebra (C(SU (2))) by O O P q (SU (2)), and the (SU (2))-comodule algebra (C(S4n+3)) by P q q C(SUq(2)) q (S4n+3). Since the (C(SU (2)), ∆)-action on C(S4n+3) is free, for any ﬁnSiUtqe(-2d)imeqnsional corepresentationqV of O(SU (2)), the asqsociated left C(HPn)- P O q q mreomdu1l.e2]. SUq(2)(Sq4n+3)(cid:50) (SUq(2))V is ﬁnitely generated projective by [15, Theo- Next, let V and V ∨ be left corepresentations of O(SU (2)) on C2 given respec- q ∨ tively by the fundamental and contragredient representation matrices u and u . Now consider the corresponding associated C(HPn)-modules q

text: PULLING

label: paragraph

text: BACK

text: NONCOMMUTATIVE

text: BUNDLES

text: of

label: equation

text: the

text: representation

text: contragredient

text: to

text: the

text: fundamental

text: representation.

text: Note,

text: however,

text: that

text: −1

text: α

text: qγ

text: q

text: α

text: qγ

text: q

text: γ

text: α

text: γ

text: α

text: which

text: means

text: that

text: u

text: and

text: u

text: are

text: equivalent

text: as

text: complex

text: representations

text: for

text: arbi-

text: trary

text: q.

text: Motivated

text: by

text: the

text: classical

text: situation,

text: we

text: denote

text: the

text: n-iterated

text: equivariant

text: join

text: of

text: C(SU

text: by

text: Note

text: that,

text: except

text: for

text: n

text: our

text: quantum

text: spheres

text: are

text: q

text: q

text: diﬀerent

text: from

text: Vaksman-Soibel’man

text: quantum

text: spheres

text: Indeed,

text: it

text: follows

text: imme-

text: diately

text: from

text: the

text: deﬁning

text: relations

text: of

text: the

text: C*-algebra

text: of

text: any

text: Vaksman-Soibel’man

text: quantum

text: sphere

text: that

text: its

text: space

text: of

text: characters

text: is

text: always

text: a

text: circle.

text: In

text: contrast,

text: the

text: space

text: of

text: characters

text: of

text: always

text: contains

text: the

text: torus

text: appearing

text: as

text: the

text: q

text: Cartesian

text: product

text: of

text: the

text: circles

text: of

text: characters

text: of

text: copies

text: of

text: C(SU

text: in

text: the

text: iterated

text: q

text: equivariant

text: join.

text: The

text: quaternionic

text: projective

text: space

text: HPn

text: is

text: deﬁned

text: as

text: the

text: quotient

text: space

text: with

text: respect

text: to

text: the

text: right

text: multiplication

text: by

text: non-zero

text: quaternions

text: of

text: non-zero

text: quaternionic

text: column

text: vectors

text: in

text: Observe

text: that

text: the

text: above

text: quoti-

text: enting

text: restricts

text: to

text: quotienting

text: the

text: space

text: of

text: unit

text: vectors

text: by

text: the

text: right

text: multiplication

text: by

text: unit

text: quaternions.

text: The

text: latter

text: can

text: be

text: identiﬁed

text: with

text: the

text: group

text: Since,

text: for

text: q

text: the

text: action

text: of

text: (C(SU

text: on

text: is

text: equivalent

text: to

text: the

text: above

text: standard

text: right

text: on

text: with

text: HPn

text: aqs

text: the

text: space

text: of

text: orbits,

text: we

text: propose

text: the

text: following

text: deﬁnition.

text: Deﬁnition

text: We

text: deﬁne

text: the

text: C*-algebra

text: of

text: the

text: n-th

text: quantum

text: quaternionic

text: pro-

text: jective

text: space

text: as

text: the

text: ﬁxed-point

text: subalgebra

text: HP

text: C(

text: n)

text: q

text: q

text: q

text: q

text: b

text: δ

text: (b)

text: b

text: q

text: O

text: For

text: the

text: sake

text: of

text: brevity,

text: let

text: us

text: denote

text: the

text: Hopf

text: algebra

text: (C(SU

text: by

text: O

text: O

text: P

text: q

text: (SU

text: and

text: the

text: (SU

text: algebra

text: by

text: P

text: q

text: q

text: q

text: Since

text: the

text: (C(SU

text: ∆)-action

text: on

text: is

text: free,

text: for

text: any

text: corepresentationqV

text: of

text: O(SU

text: the

text: asqsociated

text: left

text: C(HPn)-

text: P

text: O

text: q

text: q

text: is

text: ﬁnitely

text: generated

text: projective

text: by

text: Theo-

text: Next,

text: let

text: V

text: and

text: V

text: be

text: left

text: corepresentations

text: of

text: O(SU

text: on

text: given

text: respec-

text: q

text: tively

text: by

text: the

text: fundamental

text: and

text: contragredient

text: representation

text: matrices

text: u

text: and

text: u

text: Now

text: consider

text: the

text: corresponding

text: associated

text: C(HPn)-modules

text: q


text: PULLING BACK NONCOMMUTATIVE BUNDLES 21 [21] J. W. Milnor, J. C. Moore, On the structure of Hopf algebras, Ann. of Math. (2) 81 (1965), 211–264. [22] S. Montgomery, Hopf Algebras and their Actions on Rings, CBMS Regional Conference Series in Mathematics, 82. Conference Board of the Mathematical Sciences, Washington, DC; American Mathematical Society, Providence, RI, 1993. [23] R. Nest, C. Voigt, Equivariant Poincaré duality for quantum group actions, J. Funct. Anal. 258 (2010), 1466–1503. [24] P. Podleś, Quantum spheres, Lett. Math. Phys. 14 (1987), no. 3, 193–202. [25] P. Podleś, Symmetries of quantum spaces. Subgroups and quotient spaces of quantum SU(2) and SO(3) groups. Comm. Math. Phys. 170 (1995), 1–20. [26] J. Pradines, Au coeur de l’oeuvre de Charles Ehresmann et de la géométrie diﬀérentielle: Les groupoides diﬀérentiables. In C. Ehresmann, Oeuvres Vol. I, Amiens 1984, 526-539. [27] P. Schauenburg, Hopf bi-Galois extensions, Comm. Algebra 24 (1996), no. 12, 3797–3825. [28] P. Schauenburg, H.-J. Schneider, On generalized Hopf Galois extensions, Jour- nal of Pure and Applied Algebra 202 (2005), 168–194. [29] P. M. Sołtan, On actions of compact quantum groups, Illinois Journal of Mathematics 55 (2011), 953–962. [30] L. L. Vaksman, Ya. S. Soibel’man, Algebra of functions on the quantum group SU(n+1), and odd-dimensional quantum spheres, (Russian) Algebra i Analiz 2 (1990), 101–120; translation in Leningrad Math. J. 2 (1991), 1023–1042. [31] S. L. Woronowicz, Twisted SU(2) group: an example of a noncommutative diﬀerential calculus, Publ. RIMS, Kyoto Univ. 23 (1987), 117–181. [32] S. L. Woronowicz, Compact quantum groups, Les Houches, Session LXIV, 1995, Quantum Symmetries, Elsevier 1998. Instytut Matematyczny, Polska Akademia Nauk, ul. Śniadeckich 8, 00–656 Warszawa, Poland Email address: pmh@impan.pl Instytut Matematyki, Uniwersytet Warszawski, ul. Banacha 2, 02–097 Warszawa, Poland Email address: t.maszczyk@uw.edu.pl

text: PULLING

text: BACK

text: NONCOMMUTATIVE

text: BUNDLES

label: reference

text: J.

text: W.

text: Milnor,

text: J.

text: C.

text: Moore,

text: On

text: the

text: structure

text: of

text: Hopf

text: algebras,

text: Ann.

text: of

text: Math.

text: S.

text: Montgomery,

text: Hopf

text: Algebras

text: and

text: their

text: Actions

text: on

text: Rings,

text: CBMS

text: Regional

text: Conference

text: Series

text: in

text: Mathematics,

text: Conference

text: Board

text: of

text: the

text: Mathematical

text: Sciences,

text: Washington,

text: DC;

text: American

text: Mathematical

text: Society,

text: Providence,

text: RI,

text: R.

text: Nest,

text: C.

text: Voigt,

text: Equivariant

text: Poincaré

text: duality

text: for

text: quantum

text: group

text: actions,

text: J.

text: Funct.

text: Anal.

text: P.

text: Podleś,

text: Quantum

text: spheres,

text: Lett.

text: Math.

text: Phys.

text: no.

text: P.

text: Podleś,

text: Symmetries

text: of

text: quantum

text: spaces.

text: Subgroups

text: and

text: quotient

text: spaces

text: of

text: quantum

text: and

text: groups.

text: Comm.

text: Math.

text: Phys.

text: J.

text: Pradines,

text: Au

text: coeur

text: de

text: l’oeuvre

text: de

text: Charles

text: Ehresmann

text: et

text: de

text: la

text: géométrie

text: diﬀérentielle:

text: Les

text: groupoides

text: diﬀérentiables.

text: In

text: C.

text: Ehresmann,

text: Oeuvres

text: Vol.

text: I,

text: Amiens

text: P.

text: Schauenburg,

text: Hopf

text: bi-Galois

text: extensions,

text: Comm.

text: Algebra

text: no.

text: P.

text: Schauenburg,

text: H.-J.

text: Schneider,

text: On

text: generalized

text: Hopf

text: Galois

text: extensions,

text: Jour-

text: nal

text: of

text: Pure

text: and

text: Applied

text: Algebra

text: P.

text: M.

text: Sołtan,

text: On

text: actions

text: of

text: compact

text: quantum

text: groups,

text: Illinois

text: Journal

text: of

text: Mathematics

text: L.

text: L.

text: Vaksman,

text: Ya.

text: S.

text: Soibel’man,

text: Algebra

text: of

text: functions

text: on

text: the

text: quantum

text: group

text: and

text: odd-dimensional

text: quantum

text: spheres,

text: (Russian)

text: Algebra

text: i

text: Analiz

text: translation

text: in

text: Leningrad

text: Math.

text: J.

text: S.

text: L.

text: Woronowicz,

text: Twisted

text: group:

text: an

text: example

text: of

text: a

text: noncommutative

text: diﬀerential

text: calculus,

text: Publ.

text: RIMS,

text: Kyoto

text: Univ.

text: S.

text: L.

text: Woronowicz,

text: Compact

text: quantum

text: groups,

text: Les

text: Houches,

text: Session

text: LXIV,

text: Quantum

text: Symmetries,

text: Elsevier

text: Instytut

text: Matematyczny,

text: Polska

text: Akademia

text: Nauk,

text: ul.

text: Śniadeckich

text: Warszawa,

text: Poland

text: Email

text: address:

text: pmh@impan.pl

text: Instytut

text: Matematyki,

text: Uniwersytet

text: Warszawski,

text: ul.

text: Banacha

text: Warszawa,

text: Poland

text: Email

text: address:

text: t.maszczyk@uw.edu.pl


text: 6 PIOTR M. HAJAC AND TOMASZ MASZCZYK A(cid:48) B(cid:48) B(cid:48) Proof. Since is a faithfully ﬂat right -module, the map of left -modules C right -comodules (cid:101) ◦ ⊗ B(cid:48) ⊗ A −→ A(cid:48) (cid:48) ⊗ (cid:48) (cid:48) (cid:48) (1.4) f := mA(cid:48) (idB(cid:48) B f): B , mA(cid:48)(b a ) = b a , A(cid:48) C is an isomorphism if and only if the map of left -modules right -comodules (cid:101) ⊗ A(cid:48) ⊗ B(cid:48) ⊗ A −→ A(cid:48) ⊗ A(cid:48) (1.5) idA(cid:48) B(cid:48) f : B(cid:48) B B(cid:48) B(cid:48) A is an isomorphism. Replacing the left-hand-side by , the latter is an iso- morphism if and only if ⊗ ⊗ A(cid:48) ⊗ A ⊗ A −→ A(cid:48) ⊗ A(cid:48) (1.6) idA(cid:48) (f B(cid:48) f): A B B(cid:48) A is an isomorphism. Thus, from the commutativity of the diagram (1.7) A(cid:48) ⊗A A ⊗B A idA(cid:48)⊗A(f⊗B(cid:48)f)(cid:47)(cid:47) A(cid:48) ⊗B(cid:48) A(cid:48) idA(cid:48)⊗A can can(cid:48) (cid:15)(cid:15) ∼ (cid:15)(cid:15) A(cid:48) ⊗A A ⊗ C = (cid:47)(cid:47) A(cid:48) ⊗ C (cid:101) and the bijectivit(cid:101)y of the canonical maps, we infer that f is an isomorphism. B(cid:48) C Furthermore, as f is a homomorphism of left -modules right -comodules, we conclude that (cid:101) C B(cid:48) ⊗ A C −→ A(cid:48) C (1.8) f (cid:50) id : ( B )(cid:50) V (cid:50) V V B(cid:48) C is an isomorphism of left -modules. Finally, since is cosemisimple, and any comodule over a cosemisimple coalgebra is injective [11, Theorem 3.1.5 (iii)], B(cid:48) ⊗ − whence coﬂat [11, Theorem 2.4.17 (i)-(iii)], the balanced tensor product B ( ) − C and the cotensor product ( )(cid:50) V commute. Therefore, there is a natural in V B(cid:48) isomorphism of left -modules ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: PIOTR

text: M.

text: HAJAC

text: AND

text: TOMASZ

text: MASZCZYK

text: Proof.

text: Since

text: is

text: a

text: faithfully

text: ﬂat

text: right

text: -module,

text: the

text: map

text: of

text: left

text: -modules

text: C

text: right

text: -comodules

text: A

text: f

text: B

text: f):

text: B

text: a

text: b

text: a

text: C

text: is

text: an

text: isomorphism

text: if

text: and

text: only

text: if

text: the

text: map

text: of

text: left

text: -modules

text: right

text: -comodules

text: A

text: f

text: B

text: A

text: is

text: an

text: isomorphism.

text: Replacing

text: the

text: left-hand-side

text: by

text: the

text: latter

text: is

text: an

text: iso-

text: morphism

text: if

text: and

text: only

text: if

text: A

text: A

text: (f

text: f):

text: A

text: B

text: A

text: is

text: an

text: isomorphism.

text: Thus,

text: from

text: the

text: commutativity

text: of

text: the

text: diagram

text: ⊗A

text: A

text: ⊗B

text: A

text: can

text: ⊗A

text: A

text: C

text: C

text: and

text: the

text: of

text: the

text: canonical

text: maps,

text: we

text: infer

text: that

text: f

text: is

text: an

text: isomorphism.

text: C

text: Furthermore,

text: as

text: f

text: is

text: a

text: homomorphism

text: of

text: left

text: -modules

text: right

text: -comodules,

text: we

text: conclude

text: that

text: C

text: A

text: C

text: C

text: f

text: id

text: B

text: V

text: V

text: V

text: C

text: is

text: an

text: isomorphism

text: of

text: left

text: -modules.

text: Finally,

text: since

text: is

text: cosemisimple,

text: and

text: any

text: comodule

text: over

text: a

text: cosemisimple

text: coalgebra

text: is

text: injective

text: Theorem

text: (iii)],

text: whence

text: coﬂat

text: Theorem

text: (i)-(iii)],

text: the

text: balanced

text: tensor

text: product

text: B

text: C

text: and

text: the

text: cotensor

text: product

text: V

text: commute.

text: Therefore,

text: there

text: is

text: a

text: natural

text: in

text: V

text: isomorphism

text: of

text: left

text: -modules

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 8 PIOTR M. HAJAC AND TOMASZ MASZCZYK (cid:48) − ◦ ⊗ ⊗ ◦ − (1.12) (can ) 1 (f idC) = (f B f) can 1. (cid:48) Therefore, canonical entwinings ψ and ψ are related as follows: (cid:0) (cid:1) (cid:16) (cid:0) (cid:1)(cid:17) (cid:0) (cid:1)(cid:0) (cid:1) ⊗ ◦ ⊗ ⊗ − ⊗ (f idC) ψ (c a) = (f idC) can (can 1(1 c)a) (cid:0) (cid:0) (cid:1)(cid:1) (cid:48) ◦ ⊗ − ⊗ = can(cid:0) (f B f(cid:0)) can 1(1 (cid:1)c)a (cid:1) (cid:48) ⊗ − ⊗ = can (cid:16)((cid:0)f B f) can 1(1 (cid:1)c)a (cid:17) (cid:48) ⊗ − ⊗ = can (f B f) can 1(1 c) f(a) (cid:48)(cid:16)(cid:0) (cid:48) − ⊗(cid:1) (cid:17) = can (can ) 1(f(1) c) f(a) (cid:48) (cid:48) − ⊗ = can (can ) 1(1 c) f(a) (cid:0) (cid:1) (cid:48) ⊗ = ψ (c f(a)) (cid:48) ◦ ⊗ ⊗ (1.13) = ψ (idC f) (c a). As c and a are arbitrary, we conclude that ⊗ ◦ (cid:48) ◦ ⊗ (1.14) (f idC) ψ = ψ (idC f). Now it follows from the invertibility of the entwinings that (cid:48) − ◦ ⊗ ⊗ ◦ − (1.15) (ψ ) 1 (f idC) = (idC f) ψ 1. ⊗ Finally, evaluating the above equation on a e, we get (cid:0) (cid:1) (cid:0) (cid:1) (cid:48) − ◦ ⊗ ⊗ ⊗ ◦ − ⊗ (1.16) (ψ ) 1 (f idC) (a e) = (idC f) ψ 1 (a e), which reads (cid:0) (cid:1) (cid:0) (cid:1) ◦ ⊗ ◦ (1.17) A(cid:48)δ f (a) = (idC f) Aδ (a).

text: PIOTR

text: M.

text: HAJAC

text: AND

text: TOMASZ

text: MASZCZYK

text: (can

text: (f

text: idC)

text: (f

text: B

text: f)

text: can

text: Therefore,

text: canonical

text: entwinings

text: ψ

text: and

text: ψ

text: are

text: related

text: as

text: follows:

text: (f

text: idC)

text: ψ

text: (c

text: a)

text: (f

text: idC)

text: can

text: (can

text: c)a)

text: (f

text: B

text: can

text: can

text: B

text: f)

text: can

text: can

text: (f

text: B

text: f)

text: can

text: c)

text: f(a)

text: can

text: (can

text: c)

text: f(a)

text: can

text: (can

text: c)

text: f(a)

text: ψ

text: (c

text: f(a))

text: ψ

text: (idC

text: f)

text: (c

text: a).

text: As

text: c

text: and

text: a

text: are

text: arbitrary,

text: we

text: conclude

text: that

text: (f

text: idC)

text: ψ

text: ψ

text: (idC

text: f).

text: Now

text: it

text: follows

text: from

text: the

text: invertibility

text: of

text: the

text: entwinings

text: that

text: (ψ

text: (f

text: idC)

text: (idC

text: f)

text: ψ

text: Finally,

text: evaluating

text: the

text: above

text: equation

text: on

text: a

text: e,

text: we

text: get

text: (ψ

text: (f

text: idC)

text: (a

text: e)

text: (idC

text: f)

text: ψ

text: (a

text: e),

text: which

text: reads

text: f

text: (a)

text: (idC

text: f)

text: Aδ

text: (a).


text: unbound researchers from the need for costly supervised Table 1: Number of images per event category for some of datasets. We approach this problem from a multi-modal the most popular event categories in our dataset. perspective (using the image and caption together), which allows us to name and discover higher level image concepts. Event # of Images Event # of Image Visual pattern mining is an important task since it is Attack 52649 Injure 5853 the foundation of many middle-level feature representation Demonstrate 20933 Transport 51187 frameworks. [6] and [22] use low level features and a Elect 9265 Convict 1473 hashing approach to mine visual patterns from image col- Die 26475 Meet 32787 lections. [21] utilizes a spatial random partition to de- velop a fast image matching approach to discover visual In this section we discuss our multimodal pattern min- patterns. All of these methods obtain image patches from ing approach. In particular, how we collected a large scale the original image collection either by random sampling or dataset, generated feature based transactions from the im- salient/objectness detection and utilize image matching or age and captions, and how we ﬁnd semantic visual patterns clustering to detect similar patches to create visual patterns. and name them. These methods are computationally intense, because they 3.1. Weakly Supervised Event Dataset Collection have to examine possibly hundreds or thousands of image patches from each image. These methods rely heavily on We believe that by using weakly supervised image data low level image features, and therefore do not often pro- from target categories that are sufﬁciently broad we can duce image patches that exhibit high level semantic mean- automatically discover meaningful and recongizable image ing. The generated image patterns are usual visually dupli- patch patterns. To accomplish this task we collect a set of cated or near-duplicated image patches. image caption pairs from a variety of types of news event Convolutional neural networks (CNN) have achieved categories. Fig. 1 provides an example of the differences great success in many research areas [17], [8]. Recently, and variability of the visual content between news images [11] combined the image representation from a CNN and and a scene classiﬁcation dataset that allow us to learn association rule mining technology to effectively mine vi- higher level image patterns. sual patterns. They ﬁrst randomly sampled image patches We begin by crawling the complete Twitter feeds of four from the original image and extracted the fully connected prominent news agencies, the Associated Press, Al Jazeera, layer response as features for each image patch utilized in Reuters, and CNN. Each of these agencies have a promi- an association rule mining framework. This approach is nent twitter presence, and tweet links to their articles multi- able to ﬁnd consistent visual patterns, but cannot guarantee ple times a day. We collect the links to the articles and then the discovered visual patterns are semantically meaningful. download the html ﬁle from each extracted link. The arti- Most of the existing visual pattern mining work focuses on cle links span the time frame from 2007-2015, and cover a how to ﬁnd visually consistent patterns. To the best of our variety of different topics. We then parse the raw html ﬁle knowledge, our paper is the ﬁrst attempt to ﬁnd high level and ﬁnd the image and caption pairs from the downloaded semantically meaningful visual patterns. news articles. Through this process we are able to collect Another category of related works is image captioning. approximately 280k image-caption pairs. In recent years, many researchers have focused on teaching Once we have collected the dataset we want to ﬁnd machines to understand images and captions jointly. Im- image-caption pairs that are related to different events cov- age caption generation focuses on automatically generating ered in news. We utilized the event ontology that was de- a caption that directly describes the content in an image us- ﬁned for the Knowledge Base Population (KBP) task in ing a language model. Multimodal CNNs [5] or RNN [14] the National Institute for Standards and Technology Text frameworks are often used to generate sentences for the im- Analysis Conference in 2014 to provide supervision to our ages. All the existing work use supervised approaches to dataset. Within this task there is an event track with the learn a language generation model based on carefully con- stated goal to “extract information such that the information structed image captions created for this task. The datasets would be suitable as input to a knowledge base.” This track used in caption generation, such as the MSCoco dataset goal closely models the goals of learning patterns that are [12] consist of much simpler sentences than appear in news recognizable and hence could be used in knowledge base image-caption pairs. We differ from these approaches in population. Making this ontology a perfect ﬁt for our task. that we do not try to generate a caption for images, but in- The KBP event task utilizes the ontology deﬁned by the stead use them jointly to mine and name the patterns that Lingustic Data Consortium in 2005 [2]. This event ontology appear throughout the images. contains 34 distinct event types, the events are broad actions 3. Multimodal Pattern Mining that appear commonly throughout news documents, such as demonstrate, divorce, and convict. Provided in the training 3 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: unbound

text: researchers

text: from

text: the

text: need

text: for

text: costly

text: supervised

text: Table

text: Number

label: caption

text: of

text: images

text: per

text: event

text: category

text: for

text: some

text: of

text: datasets.

text: We

text: approach

text: this

text: problem

text: from

text: a

text: multi-modal

text: the

text: most

text: popular

text: event

text: categories

text: in

text: our

text: dataset.

text: perspective

text: (using

text: the

text: image

text: and

text: caption

text: together),

text: which

text: allows

text: us

text: to

text: name

text: and

text: discover

text: higher

text: level

text: image

text: concepts.

text: Event

label: table

text: of

text: Images

text: Event

text: of

text: Image

text: Visual

text: pattern

text: mining

text: is

text: an

text: important

text: task

text: since

text: it

text: is

text: Attack

text: Injure

text: the

text: foundation

text: of

text: many

text: middle-level

text: feature

text: representation

text: Demonstrate

text: Transport

text: frameworks.

text: and

text: use

text: low

text: level

text: features

text: and

text: a

text: Elect

text: Convict

text: hashing

text: approach

text: to

text: mine

text: visual

text: patterns

text: from

text: image

text: col-

text: Die

text: Meet

text: lections.

text: utilizes

text: a

text: spatial

text: random

text: partition

text: to

text: de-

text: velop

text: a

text: fast

text: image

text: matching

text: approach

text: to

text: discover

text: visual

text: In

text: this

text: section

text: we

text: discuss

text: our

text: multimodal

text: pattern

text: min-

text: patterns.

text: All

text: of

text: these

text: methods

text: obtain

text: image

text: patches

text: from

text: ing

text: approach.

text: In

text: particular,

text: how

text: we

text: collected

text: a

text: large

text: scale

text: the

text: original

text: image

text: collection

text: either

text: by

text: random

text: sampling

text: or

text: dataset,

text: generated

text: feature

text: based

text: transactions

text: from

text: the

text: im-

text: salient/objectness

text: detection

text: and

text: utilize

text: image

text: matching

text: or

text: age

text: and

text: captions,

text: and

text: how

text: we

text: ﬁnd

text: semantic

text: visual

text: patterns

text: clustering

text: to

text: detect

text: similar

text: patches

text: to

text: create

text: visual

text: patterns.

text: and

text: name

text: them.

text: These

text: methods

text: are

text: computationally

text: intense,

text: because

text: they

text: Weakly

text: Supervised

text: Event

text: Dataset

text: Collection

text: have

text: to

text: examine

text: possibly

text: hundreds

text: or

text: thousands

text: of

text: image

text: patches

text: from

text: each

text: image.

text: These

text: methods

text: rely

text: heavily

text: on

text: We

text: believe

text: that

text: by

text: using

text: weakly

text: supervised

text: image

text: data

text: low

text: level

text: image

text: features,

text: and

text: therefore

text: do

text: not

text: often

text: pro-

text: from

text: target

text: categories

text: that

text: are

text: sufﬁciently

text: broad

text: we

text: can

text: duce

text: image

text: patches

text: that

text: exhibit

text: high

text: level

text: semantic

text: mean-

text: automatically

text: discover

text: meaningful

text: and

text: recongizable

text: image

text: ing.

text: The

text: generated

text: image

text: patterns

text: are

text: usual

text: visually

text: dupli-

text: patch

text: patterns.

text: To

text: accomplish

text: this

text: task

text: we

text: collect

text: a

text: set

text: of

text: cated

text: or

text: near-duplicated

text: image

text: patches.

text: image

text: caption

text: pairs

text: from

text: a

text: variety

text: of

text: types

text: of

text: news

text: event

text: Convolutional

text: neural

text: networks

text: (CNN)

text: have

text: achieved

text: categories.

text: Fig.

text: provides

text: an

text: example

text: of

text: the

text: differences

text: great

text: success

text: in

text: many

text: research

text: areas

text: Recently,

text: and

text: variability

text: of

text: the

text: visual

text: content

text: between

text: news

text: images

text: combined

text: the

text: image

text: representation

text: from

text: a

text: CNN

text: and

text: and

text: a

text: scene

text: classiﬁcation

text: dataset

text: that

text: allow

text: us

text: to

text: learn

text: association

text: rule

text: mining

text: technology

text: to

text: effectively

text: mine

text: vi-

text: higher

text: level

text: image

text: patterns.

text: sual

text: patterns.

text: They

text: ﬁrst

text: randomly

text: sampled

text: image

text: patches

text: We

text: begin

text: by

text: crawling

text: the

text: complete

text: Twitter

text: feeds

text: of

text: four

text: from

text: the

text: original

text: image

text: and

text: extracted

text: the

text: fully

text: connected

text: prominent

text: news

text: agencies,

text: the

text: Associated

text: Press,

text: Al

text: Jazeera,

text: layer

text: response

text: as

text: features

text: for

text: each

text: image

text: patch

text: utilized

text: in

text: Reuters,

text: and

text: CNN.

text: Each

text: of

text: these

text: agencies

text: have

text: a

text: promi-

text: an

text: association

text: rule

text: mining

text: framework.

text: This

text: approach

text: is

text: nent

text: twitter

text: presence,

text: and

text: tweet

text: links

text: to

text: their

text: articles

text: multi-

text: able

text: to

text: ﬁnd

text: consistent

text: visual

text: patterns,

text: but

text: cannot

text: guarantee

text: ple

text: times

text: a

text: day.

text: We

text: collect

text: the

text: links

text: to

text: the

text: articles

text: and

text: then

text: the

text: discovered

text: visual

text: patterns

text: are

text: semantically

text: meaningful.

text: download

text: the

text: html

text: ﬁle

text: from

text: each

text: extracted

text: link.

text: The

text: arti-

text: Most

text: of

text: the

text: existing

text: visual

text: pattern

text: mining

text: work

text: focuses

text: on

text: cle

text: links

text: span

text: the

text: time

text: frame

text: from

text: and

text: cover

text: a

text: how

text: to

text: ﬁnd

text: visually

text: consistent

text: patterns.

text: To

text: the

text: best

text: of

text: our

text: variety

text: of

text: different

text: topics.

text: We

text: then

text: parse

text: the

text: raw

text: html

text: ﬁle

text: knowledge,

text: our

text: paper

text: is

text: the

text: ﬁrst

text: attempt

text: to

text: ﬁnd

text: high

text: level

text: and

text: ﬁnd

text: the

text: image

text: and

text: caption

text: pairs

text: from

text: the

text: downloaded

text: semantically

text: meaningful

text: visual

text: patterns.

text: news

text: articles.

text: Through

text: this

text: process

text: we

text: are

text: able

text: to

text: collect

text: Another

text: category

text: of

text: related

text: works

text: is

text: image

text: captioning.

text: approximately

text: image-caption

text: pairs.

text: In

text: recent

text: years,

text: many

text: researchers

text: have

text: focused

text: on

text: teaching

text: Once

text: we

text: have

text: collected

text: the

text: dataset

text: we

text: want

text: to

text: ﬁnd

text: machines

text: to

text: understand

text: images

text: and

text: captions

text: jointly.

text: Im-

text: image-caption

text: pairs

text: that

text: are

text: related

text: to

text: different

text: events

text: cov-

text: age

text: caption

text: generation

text: focuses

text: on

text: automatically

text: generating

text: ered

text: in

text: news.

text: We

text: utilized

text: the

text: event

text: ontology

text: that

text: was

text: de-

text: a

text: caption

text: that

text: directly

text: describes

text: the

text: content

text: in

text: an

text: image

text: us-

text: ﬁned

text: for

text: the

text: Knowledge

text: Base

text: Population

text: (KBP)

text: task

text: in

text: ing

text: a

text: language

text: model.

text: Multimodal

text: CNNs

text: or

text: RNN

text: the

text: National

text: Institute

text: for

text: Standards

text: and

text: Technology

text: Text

text: frameworks

text: are

text: often

text: used

text: to

text: generate

text: sentences

text: for

text: the

text: im-

text: Analysis

text: Conference

text: in

text: to

text: provide

text: supervision

text: to

text: our

text: ages.

text: All

text: the

text: existing

text: work

text: use

text: supervised

text: approaches

text: to

text: dataset.

text: Within

text: this

text: task

text: there

text: is

text: an

text: event

text: track

text: with

text: the

text: learn

text: a

text: language

text: generation

text: model

text: based

text: on

text: carefully

text: con-

text: stated

text: goal

text: to

text: “extract

text: information

text: such

text: that

text: the

text: information

text: structed

text: image

text: captions

text: created

text: for

text: this

text: task.

text: The

text: datasets

text: would

text: be

text: suitable

text: as

text: input

text: to

text: a

text: knowledge

text: base.”

text: This

text: track

text: used

text: in

text: caption

text: generation,

text: such

text: as

text: the

text: MSCoco

text: dataset

text: goal

text: closely

text: models

text: the

text: goals

text: of

text: learning

text: patterns

text: that

text: are

text: consist

text: of

text: much

text: simpler

text: sentences

text: than

text: appear

text: in

text: news

text: recognizable

text: and

text: hence

text: could

text: be

text: used

text: in

text: knowledge

text: base

text: image-caption

text: pairs.

text: We

text: differ

text: from

text: these

text: approaches

text: in

text: population.

text: Making

text: this

text: ontology

text: a

text: perfect

text: ﬁt

text: for

text: our

text: task.

text: that

text: we

text: do

text: not

text: try

text: to

text: generate

text: a

text: caption

text: for

text: images,

text: but

text: in-

text: The

text: KBP

text: event

text: task

text: utilizes

text: the

text: ontology

text: deﬁned

text: by

text: the

text: stead

text: use

text: them

text: jointly

text: to

text: mine

text: and

text: name

text: the

text: patterns

text: that

text: Lingustic

text: Data

text: Consortium

text: in

text: This

text: event

text: ontology

text: appear

text: throughout

text: the

text: images.

text: contains

text: distinct

text: event

text: types,

text: the

text: events

text: are

text: broad

text: actions

text: Multimodal

text: Pattern

text: Mining

text: that

text: appear

text: commonly

text: throughout

text: news

text: documents,

text: such

text: as

text: demonstrate,

text: divorce,

text: and

text: convict.

text: Provided

text: in

text: the

text: training

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: data with these event ontologies is a list of trigger words for zero-padded representation of the image with zero-padding each of the events that are used to detect when an event ap- around the image edges of 64 pixels and a stride of 32. × pears in text data. An example of some of the trigger words Namely, from a 227 227 scaled input image, a total of × used for the demonstrate event are: protest, riot, insurrec- 6 6 (36) patch areas are covered from all the stride posi- × tion, and rally. We search each of the captions for a trigger tions, resulting in a 6 6 feature map for each ﬁlter in the word from the event category, and if an image caption con- layer 5. Using this approach we are able to use the cur- tains that trigger word we assign that image caption pair to rent existing architecture to compute the ﬁlter responses for the given event category. The number of images found for all patches at once without actually changing the network some of the event categories can be seen in Table. 1. structure. This idea allows us to extract image patch pat- 3.1.1 Review of Pattern Mining terns in a way that is much more efﬁcient than current state of the art methods. In this section we will review the basic ideas and deﬁ- We use the pre-trained CNN model from [8] that was nitions necessary for pattern mining. Assume that we are { } trained using the ImageNet dataset to extract the pool5 fea- given a set of n possible observations X = x , x , ...x , a transaction, T, is a set of observations such t1hat2T ⊆ nX. tures for the news event images. F×or each image, we keep Given a set of transactions S = {T , T , ...T } containing the maximum response over the 6 6 feature map and set 1 2 m m transactions, our goal is to ﬁnd a particular subset of X, other non-maximal values to zero for all 256 ﬁlters, simi- ∗ lar to the non-maximum suppression operation in the liter- say t , which can accurately predict the presence of some ∈ ∗ ⊂ ∩ ∗ ∅ ature. Such an operation is used to ﬁnd the patch trigger- target element y T , given that t T and y t = . t∗ is referred to as a afrequent itemset in tahe pattern mining ing the highest response in each ﬁlter and avoid redundant ∗ → patches in the surrounding neighborhood in the image that literature. The relationship from t y is known as an association rule. The support of t∗ reﬂects how often t∗ may also generate high responses. The above process re- appears in S and is deﬁned as, sults in a 256 dimensional feature vector representation for each image patch. It has been shown in [11] that most of the |{ | ∗ ⊆ ∈ }| ∗ T t T , T S information is carried by the top k magnitude dimensions s(t ) = a a a (1) m of the feature vector, and the magnitude response of these dimensions is not particularly important. Thus, we follow Our goal is to ﬁnd association rules that accurately pre- their suggestion and set the top k magnitude dimensions of dict the correct event category for the image-caption pairs. the CNN vector to 1 and the others to 0, creating a binary ∗ Therefore, we want to ﬁnd patterns such that if t appears in representation of which ﬁlters are activated for each image a transaction there is a high likelihood that y, which repre- patch. We use these sparse binarized features to build trans- sents an event category, appears in that transaction as well. actions for each image patch as discussed in Sec. , where the ∗ ⊆ We deﬁne the conﬁdence as the likelihood that if t T non-zero dimensions are the items in our transaction. ∈ then y T, or, By utilizing the architecture of the CNN directly we are ∗ ∩ able to efﬁciently extract image features that come from ∗ → s(t y) c(t y) = ∗ . (2) speciﬁc ROI that are suitable for pattern mining. The cur- s(t ) rent state of the art pattern mining technique proposed by [11] requires a sampling of the image patches within each 3.1.2 Using CNN Pool5 Features for Transaction Gen- image and then operating the entire CNN over this sam- eration from Images pled and resized image patch. This procedure is very costly, Certain portions of a CNN are only activated by a smaller because the CNN must be used to extract features from a region of interest (ROI) within the original image. The last number of sampled images that can be orders of magnitude layer in which the particular neurons do not correspond to larger than the dataset size. For example, for the MIT in- × the entire image is the output of the ﬁnal convolutional and door dataset the authors of [11] sample 128 128 size im- pooling layer for [8]. Based on this observation, for each age patches with a stride of 32 from images that have been image we ﬁnd the maximum magnitude response from a resized such that their smallest dimension is of size 256. particular feature map from the pool5 layer of the CNN de- Thus, the number of image samples that are taken for each − ﬁned by [8]. The pool5 layer of this network consists of 256 image is greater than or equal to (256 128 + 1)2 = 25. The × 32 ﬁlters, and the response of each of the ﬁlters over a 6 6 full CNN must operate on all of these sampled images. In mapping of the image. The corresponding ROI from the contrast our method works directly on the image themselves original image in which all the pixels in that region con- without any sampling. We are able to extract representa- tribute to the response of a particular neuron in the pool5 tions for 36 image patches from an image while only hav- × × layer is a 196 196 image patch from the 227 227 re- ing the CNN operate on the image once. By leveraging the × sized image. These 196 196 image patches come from a structure of the CNN during test or deployment our method 4 ##LTLine## ##LTLine## ##LTLine##

text: data

text: with

text: these

text: event

text: ontologies

text: is

text: a

text: list

text: of

text: trigger

text: words

text: for

text: zero-padded

text: representation

text: of

text: the

text: image

text: with

text: zero-padding

text: each

text: of

text: the

text: events

text: that

text: are

text: used

text: to

text: detect

text: when

text: an

text: event

text: ap-

text: around

text: the

text: image

text: edges

text: of

text: pixels

text: and

text: a

text: stride

text: of

text: pears

text: in

text: text

text: data.

text: An

text: example

text: of

text: some

text: of

text: the

text: trigger

text: words

text: Namely,

text: from

text: a

text: scaled

text: input

text: image,

text: a

text: total

text: of

text: used

text: for

text: the

text: demonstrate

text: event

text: are:

text: protest,

text: riot,

text: insurrec-

text: patch

text: areas

text: are

text: covered

text: from

text: all

text: the

text: stride

text: posi-

text: tion,

text: and

text: rally.

text: We

text: search

text: each

text: of

text: the

text: captions

text: for

text: a

text: trigger

text: tions,

text: resulting

text: in

text: a

text: feature

text: map

text: for

text: each

text: ﬁlter

text: in

text: the

text: word

text: from

text: the

text: event

text: category,

text: and

text: if

text: an

text: image

text: caption

text: con-

text: layer

text: Using

text: this

text: approach

text: we

text: are

text: able

text: to

text: use

text: the

text: cur-

text: tains

text: that

text: trigger

text: word

text: we

text: assign

text: that

text: image

text: caption

text: pair

text: to

text: rent

text: existing

text: architecture

text: to

text: compute

text: the

text: ﬁlter

text: responses

text: for

text: the

text: given

text: event

text: category.

text: The

text: number

text: of

text: images

text: found

text: for

text: all

text: patches

text: at

text: once

text: without

text: actually

text: changing

text: the

text: network

text: some

text: of

text: the

text: event

text: categories

text: can

text: be

text: seen

text: in

text: Table.

text: structure.

text: This

text: idea

text: allows

text: us

text: to

text: extract

text: image

text: patch

text: pat-

text: Review

text: of

text: Pattern

text: Mining

text: terns

text: in

text: a

text: way

text: that

text: is

text: much

text: more

text: efﬁcient

text: than

text: current

text: state

text: of

text: the

text: art

text: methods.

text: In

text: this

text: section

text: we

text: will

text: review

text: the

text: basic

text: ideas

text: and

text: deﬁ-

text: We

text: use

text: the

text: pre-trained

text: CNN

text: model

text: from

text: that

text: was

text: nitions

text: necessary

text: for

text: pattern

text: mining.

text: Assume

text: that

text: we

text: are

text: trained

text: using

text: the

text: ImageNet

text: dataset

text: to

text: extract

text: the

text: fea-

text: given

text: a

text: set

text: of

text: n

text: possible

text: observations

text: X

text: x

text: x

text: ...x

text: a

text: transaction,

text: T,

text: is

text: a

text: set

text: of

text: observations

text: such

text: nX.

text: tures

text: for

text: the

text: news

text: event

text: images.

text: F×or

text: each

text: image,

text: we

text: keep

text: Given

text: a

text: set

text: of

text: transactions

text: S

text: {T

text: T

text: ...T

text: containing

text: the

text: maximum

text: response

text: over

text: the

text: feature

text: map

text: and

text: set

text: m

text: m

text: transactions,

text: our

text: goal

text: is

text: to

text: ﬁnd

text: a

text: particular

text: subset

text: of

text: X,

text: other

text: non-maximal

text: values

text: to

text: zero

text: for

text: all

text: ﬁlters,

text: simi-

text: lar

text: to

text: the

text: non-maximum

text: suppression

text: operation

text: in

text: the

text: liter-

text: say

text: t

text: which

text: can

text: accurately

text: predict

text: the

text: presence

text: of

text: some

text: ature.

text: Such

text: an

text: operation

text: is

text: used

text: to

text: ﬁnd

text: the

text: patch

text: trigger-

text: target

text: element

text: y

text: T

text: given

text: that

text: t

text: T

text: and

text: y

text: t

text: t∗

text: is

text: referred

text: to

text: as

text: a

text: afrequent

text: itemset

text: in

text: tahe

text: pattern

text: mining

text: ing

text: the

text: highest

text: response

text: in

text: each

text: ﬁlter

text: and

text: avoid

text: redundant

text: patches

text: in

text: the

text: surrounding

text: neighborhood

text: in

text: the

text: image

text: that

text: literature.

text: The

text: relationship

text: from

text: t

text: y

text: is

text: known

text: as

text: an

text: association

text: rule.

text: The

text: support

text: of

text: t∗

text: reﬂects

text: how

text: often

text: t∗

text: may

text: also

text: generate

text: high

text: responses.

text: The

text: above

text: process

text: re-

text: appears

text: in

text: S

text: and

text: is

text: deﬁned

text: as,

text: sults

text: in

text: a

text: dimensional

text: feature

text: vector

text: representation

text: for

text: each

text: image

text: patch.

text: It

text: has

text: been

text: shown

text: in

text: that

text: most

text: of

text: the

text: T

text: t

text: T

text: T

text: S

text: information

text: is

text: carried

text: by

text: the

text: top

text: k

text: magnitude

text: dimensions

text: s(t

text: a

text: a

text: a

text: m

text: of

text: the

text: feature

text: vector,

text: and

text: the

text: magnitude

text: response

text: of

text: these

text: dimensions

text: is

text: not

text: particularly

text: important.

text: Thus,

text: we

text: follow

text: Our

text: goal

text: is

text: to

text: ﬁnd

text: association

text: rules

text: that

text: accurately

text: pre-

text: their

text: suggestion

text: and

text: set

text: the

text: top

text: k

text: magnitude

text: dimensions

text: of

text: dict

text: the

text: correct

text: event

text: category

text: for

text: the

text: image-caption

text: pairs.

text: the

text: CNN

text: vector

text: to

text: and

text: the

text: others

text: to

text: creating

text: a

text: binary

text: Therefore,

text: we

text: want

text: to

text: ﬁnd

text: patterns

text: such

text: that

text: if

text: t

text: appears

text: in

text: representation

text: of

text: which

text: ﬁlters

text: are

text: activated

text: for

text: each

text: image

text: a

text: transaction

text: there

text: is

text: a

text: high

text: likelihood

text: that

text: y,

text: which

text: repre-

text: patch.

text: We

text: use

text: these

text: sparse

text: binarized

text: features

text: to

text: build

text: trans-

text: sents

text: an

text: event

text: category,

text: appears

text: in

text: that

text: transaction

text: as

text: well.

text: actions

text: for

text: each

text: image

text: patch

text: as

text: discussed

text: in

text: Sec.

text: where

text: the

text: We

text: deﬁne

text: the

text: conﬁdence

text: as

text: the

text: likelihood

text: that

text: if

text: t

text: T

text: non-zero

text: dimensions

text: are

text: the

text: items

text: in

text: our

text: transaction.

text: then

text: y

text: T,

text: or,

text: By

text: utilizing

text: the

text: architecture

text: of

text: the

text: CNN

text: directly

text: we

text: are

text: able

text: to

text: efﬁciently

text: extract

text: image

text: features

text: that

text: come

text: from

text: s(t

text: y)

text: c(t

text: y)

text: speciﬁc

text: ROI

text: that

text: are

text: suitable

text: for

text: pattern

text: mining.

text: The

text: cur-

text: s(t

text: rent

text: state

text: of

text: the

text: art

text: pattern

text: mining

text: technique

text: proposed

text: by

text: requires

text: a

text: sampling

text: of

text: the

text: image

text: patches

text: within

text: each

text: Using

text: CNN

text: Features

text: for

text: Transaction

text: Gen-

text: image

text: and

text: then

text: operating

text: the

text: entire

text: CNN

text: over

text: this

text: sam-

text: eration

text: from

text: Images

text: pled

text: and

text: resized

text: image

text: patch.

text: This

text: procedure

text: is

text: very

text: costly,

text: Certain

text: portions

text: of

text: a

text: CNN

text: are

text: only

text: activated

text: by

text: a

text: smaller

text: because

text: the

text: CNN

text: must

text: be

text: used

text: to

text: extract

text: features

text: from

text: a

text: region

text: of

text: interest

text: (ROI)

text: within

text: the

text: original

text: image.

text: The

text: last

text: number

text: of

text: sampled

text: images

text: that

text: can

text: be

text: orders

text: of

text: magnitude

text: layer

text: in

text: which

text: the

text: particular

text: neurons

text: do

text: not

text: correspond

text: to

text: larger

text: than

text: the

text: dataset

text: size.

text: For

text: example,

text: for

text: the

text: MIT

text: in-

text: the

text: entire

text: image

text: is

text: the

text: output

text: of

text: the

text: ﬁnal

text: convolutional

text: and

text: door

text: dataset

text: the

text: authors

text: of

text: sample

text: size

text: im-

text: pooling

text: layer

text: for

text: Based

text: on

text: this

text: observation,

text: for

text: each

text: age

text: patches

text: with

text: a

text: stride

text: of

text: from

text: images

text: that

text: have

text: been

text: image

text: we

text: ﬁnd

text: the

text: maximum

text: magnitude

text: response

text: from

text: a

text: resized

text: such

text: that

text: their

text: smallest

text: dimension

text: is

text: of

text: size

text: particular

text: feature

text: map

text: from

text: the

text: layer

text: of

text: the

text: CNN

text: de-

text: Thus,

text: the

text: number

text: of

text: image

text: samples

text: that

text: are

text: taken

text: for

text: each

text: ﬁned

text: by

text: The

text: layer

text: of

text: this

text: network

text: consists

text: of

text: image

text: is

text: greater

text: than

text: or

text: equal

text: to

text: The

text: ﬁlters,

text: and

text: the

text: response

text: of

text: each

text: of

text: the

text: ﬁlters

text: over

text: a

text: full

text: CNN

text: must

text: operate

text: on

text: all

text: of

text: these

text: sampled

text: images.

text: In

text: mapping

text: of

text: the

text: image.

text: The

text: corresponding

text: ROI

text: from

text: the

text: contrast

text: our

text: method

text: works

text: directly

text: on

text: the

text: image

text: themselves

text: original

text: image

text: in

text: which

text: all

text: the

text: pixels

text: in

text: that

text: region

text: con-

text: without

text: any

text: sampling.

text: We

text: are

text: able

text: to

text: extract

text: representa-

text: tribute

text: to

text: the

text: response

text: of

text: a

text: particular

text: neuron

text: in

text: the

text: tions

text: for

text: image

text: patches

text: from

text: an

text: image

text: while

text: only

text: hav-

text: layer

text: is

text: a

text: image

text: patch

text: from

text: the

text: re-

text: ing

text: the

text: CNN

text: operate

text: on

text: the

text: image

text: once.

text: By

text: leveraging

text: the

text: sized

text: image.

text: These

text: image

text: patches

text: come

text: from

text: a

text: structure

text: of

text: the

text: CNN

text: during

text: test

text: or

text: deployment

text: our

text: method

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ⊂ Deﬁnition 4. Suppose H is a ﬁnitely generated group and S H is a ﬁnite symmetric H ⊂ generating set. Let Cay(H, S ) be the associated Cayley graph. Given a subset F H, H let ∂F be the set of all edges e of Cay(H, S ) with one endpoint in F and one endpoint in \ H H F . ⊂ Lemma 3.4. Suppose H is a ﬁnitely generated group and S H is a ﬁnite symmetric H ⊂ generating set. Suppose there exists a constant C > 0 and ﬁnite subsets F H such that n • | | ≤ ∈ N ∂F C for all n , n • | | ∞ lim →∞ F = . n n Then H has at least 2 ends. Proof. We identify each F with its induced subgraph in Cay(H, S ). We may assume n H \ without loss of generality that every connected component of the complement Cay(H, S ) F \ H n is inﬁnite. This is because we may add all ﬁnite components of Cay(H, S ) F to F without H n n increasing the size of its boundary. ∈ ∈ Choose elements g F , s S so that n n n H • ∈ (g , g s ) ∂F n n n n • ◦ ⊂ | ◦| ∞ if F F is the connected component of F containing g then lim →∞ F = + n n n n n n • ⊂ \ there exists an inﬁnite path p Cay(H, S ) F starting from g s . n H n n n (cid:48) − ◦ (cid:48) − Let F = g 1F and p = g 1p . After passing to a subsequence if necessary, we may assume n (cid:48) n n n n n(cid:48) (cid:48) (cid:48) that F converges to a limit F∞ and p converges to a limit p∞ (in the topology of uniform n n (cid:48) (cid:48) ⊂ \ (cid:48) convergence on compact subsets). We observe that F∞ is inﬁnite, p∞ Cay(H, S ) F∞ | (cid:48) | ≤ (cid:48) H is an inﬁnite path and ∂F∞ C. Thus the compact set K := ∂F∞ is such that there are \ (cid:48) at least two inﬁnite components of Cay(H, S ) K (namely, the component containing p∞ (cid:48) H and the component containing F∞). This proves that H has at least two ends. F Proposition 3.5. Suppose Γ is an inﬁnite ﬁnitely generated group, G = be a nonabelian (cid:121) ×r → free group, Γ (X, µ) a probability measure-preserving action and α : Γ X G an L1- embedding. Then Γ has more than one end. Proof. We ﬁx a free generating set of G from which we obtain a word metric and a Cayley graph (which is a regular tree since G is a free group). We also ﬁx a ﬁnite generating set S Γ for Γ. { } → To obtain a contradiction, we assume that End(Γ) = ξ is a singleton. Deﬁne φ : X (cid:48) (cid:48) End(G) by φ(x) = α (ξ, x) where α is as in Theorem 3.1. By Theorem 3.1, φ(hx) = α(h, x)φ(x). ∈ N ∈ ∈ | ≤ For n , x X, let G(n, x) be the set of all g G such that (g φ(x)) n where ·|· | (cid:54) e ∈ ( ) is the Gromov product. To be precise (g φ(x)) = d(e, m) where, if g = e, m G is e e 7 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Deﬁnition

text: Suppose

text: H

text: is

text: a

text: ﬁnitely

text: generated

text: group

text: and

text: S

text: H

text: is

text: a

text: ﬁnite

text: symmetric

text: H

text: generating

text: set.

text: Let

text: Cay(H,

text: S

text: be

text: the

text: associated

text: Cayley

text: graph.

text: Given

text: a

text: subset

text: F

text: H,

text: H

text: let

text: ∂F

text: be

text: the

text: set

text: of

text: all

text: edges

text: e

text: of

text: Cay(H,

text: S

text: with

text: one

text: endpoint

text: in

text: F

text: and

text: one

text: endpoint

text: in

text: H

text: H

text: F

text: Lemma

text: Suppose

text: H

text: is

text: a

text: ﬁnitely

text: generated

text: group

text: and

text: S

text: H

text: is

text: a

text: ﬁnite

text: symmetric

text: H

text: generating

text: set.

text: Suppose

text: there

text: exists

text: a

text: constant

text: C

text: and

text: ﬁnite

text: subsets

text: F

text: H

text: such

text: that

text: n

text: N

text: ∂F

text: C

text: for

text: all

text: n

text: n

text: lim

text: F

text: n

text: n

text: Then

text: H

text: has

text: at

text: least

text: ends.

text: Proof.

text: We

text: identify

text: each

text: F

text: with

text: its

text: induced

text: subgraph

text: in

text: Cay(H,

text: S

text: We

text: may

text: assume

text: n

text: H

text: without

text: loss

text: of

text: generality

text: that

text: every

text: connected

text: component

text: of

text: the

text: complement

text: Cay(H,

text: S

text: F

text: H

text: n

text: is

text: inﬁnite.

text: This

text: is

text: because

text: we

text: may

text: add

text: all

text: ﬁnite

text: components

text: of

text: Cay(H,

text: S

text: F

text: to

text: F

text: without

text: H

text: n

text: n

text: increasing

text: the

text: size

text: of

text: its

text: boundary.

text: Choose

text: elements

text: g

text: F

text: s

text: S

text: so

text: that

text: n

text: n

text: n

text: H

text: (g

text: g

text: s

text: ∂F

text: n

text: n

text: n

text: n

text: if

text: F

text: F

text: is

text: the

text: connected

text: component

text: of

text: F

text: containing

text: g

text: then

text: lim

text: F

text: n

text: n

text: n

text: n

text: n

text: n

text: there

text: exists

text: an

text: inﬁnite

text: path

text: p

text: Cay(H,

text: S

text: F

text: starting

text: from

text: g

text: s

text: n

text: H

text: n

text: n

text: n

text: Let

text: F

text: g

text: and

text: p

text: g

text: After

text: passing

text: to

text: a

text: subsequence

text: if

text: necessary,

text: we

text: may

text: assume

text: n

text: n

text: n

text: n

text: n

text: that

text: F

text: converges

text: to

text: a

text: limit

text: F∞

text: and

text: p

text: converges

text: to

text: a

text: limit

text: p∞

text: (in

text: the

text: topology

text: of

text: uniform

text: n

text: n

text: convergence

text: on

text: compact

text: subsets).

text: We

text: observe

text: that

text: F∞

text: is

text: inﬁnite,

text: p∞

text: Cay(H,

text: S

text: F∞

text: H

text: is

text: an

text: inﬁnite

text: path

text: and

text: ∂F∞

text: C.

text: Thus

text: the

text: compact

text: set

text: K

text: ∂F∞

text: is

text: such

text: that

text: there

text: are

text: at

text: least

text: two

text: inﬁnite

text: components

text: of

text: Cay(H,

text: S

text: K

text: (namely,

text: the

text: component

text: containing

text: p∞

text: H

text: and

text: the

text: component

text: containing

text: F∞).

text: This

text: proves

text: that

text: H

text: has

text: at

text: least

text: two

text: ends.

text: F

text: Proposition

text: Suppose

text: Γ

text: is

text: an

text: inﬁnite

text: ﬁnitely

text: generated

text: group,

text: G

text: be

text: a

text: nonabelian

text: ×r

text: free

text: group,

text: Γ

text: (X,

text: µ)

text: a

text: probability

text: measure-preserving

text: action

text: and

text: α

text: Γ

text: X

text: G

text: an

text: embedding.

text: Then

text: Γ

text: has

text: more

text: than

text: one

text: end.

text: Proof.

text: We

text: ﬁx

text: a

text: free

text: generating

text: set

text: of

text: G

text: from

text: which

text: we

text: obtain

text: a

text: word

text: metric

text: and

text: a

text: Cayley

text: graph

text: (which

text: is

text: a

text: regular

text: tree

text: since

text: G

text: is

text: a

text: free

text: group).

text: We

text: also

text: ﬁx

text: a

text: ﬁnite

text: generating

text: set

text: S

text: Γ

text: for

text: Γ.

text: To

text: obtain

text: a

text: contradiction,

text: we

text: assume

text: that

text: End(Γ)

text: ξ

text: is

text: a

text: singleton.

text: Deﬁne

text: φ

text: X

text: End(G)

text: by

text: φ(x)

text: α

text: (ξ,

text: x)

text: where

text: α

text: is

text: as

text: in

text: Theorem

text: By

text: Theorem

text: φ(hx)

text: α(h,

text: x)φ(x).

text: N

text: For

text: n

text: x

text: X,

text: let

text: G(n,

text: x)

text: be

text: the

text: set

text: of

text: all

text: g

text: G

text: such

text: that

text: (g

text: φ(x))

text: n

text: where

text: e

text: is

text: the

text: Gromov

text: product.

text: To

text: be

text: precise

text: (g

text: φ(x))

text: d(e,

text: m)

text: where,

text: if

text: g

text: e,

text: m

text: G

text: is

text: e

text: e

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: A revised version of this manuscript was published in CMIG (PMID: 18982583). Please cite the ﬁnal version: “Computational Pathology: Challenges and Promises for Tissue Analysis”, Thomas J. Fuchs and Joachim M. Buhmann, Computerized Medical Imaging and Graphics, Volume 35, Issue 7, 515–530, 2011. Computational Pathology: Challenges and Promises for Tissue Analysis Thomas J. Fuchsa,b, Joachim M. Buhmanna,b aDepartment of Computer Science, ETH Zurich, Universitaetstrasse 6, CH-8092 Zurich, Switzerland bCompetence Center for Systems Physiology and Metabolic Diseases, ETH Zurich, Schafmattstr. 18, CH-8093 Zurich, Switzerland Abstract The histological assessment of human tissue has emerged as the key challenge for detection and treatment of cancer. A plethora of different data sources ranging from tissue microarray data to gene expression, proteomics or metabolomics data provide a detailed overview of the health status of a patient. Medical doctors need to assess these information sources and they rely on data driven automatic analysis tools. Methods for classiﬁcation, grouping and segmentation of heterogeneous data sources as well as regression of noisy dependencies and estimation of survival probabilities enter the processing workﬂow of a pathology diagnosis system at various stages. This paper reports on state-of-the-art of the design and effectiveness of computational pathology workﬂows and it discusses future research directions in this emergent ﬁeld of medical informatics and diagnostic machine learning. Keywords: Computational Pathology, Machine Learning, Medical Imaging, Survival Statistics, Cancer Research Contents promises a standardized and hopefully more objective diagnosis of the disease state of a patient than manual 1 Computational Pathology: The systems view 1 inspection can provide today. An automatic computa- 2 Data: Tissue and Ground Truth 1 tional pathology pipeline also enables the medical user to quantitatively benchmark the processing pipeline and 3 Imaging: From Classical Image Processing to Statistical to identify error sensitive processing steps which can Pattern Recognition 8 substantially degrade the ﬁnal prediction of survival 4 Statistics: Survival Analysis and Machine Learning in times. Medical Statistics 12 5 The Computational Pathology Pipeline: A holistic View 14 1.1. Deﬁnition 6 Future Directions 16 Computational Pathology as well as the medical dis- cipline Pathology is a wide and diverse ﬁeld which en- 1. Computational Pathology: The systems view compass scientiﬁc research as well as day-to-day work in medical clinics. The following deﬁnition is an at- Modern pathology studies of biopsy tissue encom- tempt for a concise and practical description of this pass multiple stainings of histological material, ge- novel ﬁeld: nomics and proteomics analyses as well as compara- tive statistical analyses of patient data. Pathology lays Computational Pathology investigates a com- not only a scientiﬁc foundation for clinical medicine plete probabilistic treatment of scientiﬁc and but also serves as a bridge between the fundamental clinical workﬂows in general pathology, i.e. sciences in natural science, medicine and patient care. it combines experimental design, statistical Therefore, it can be viewed as one of the key hubs for pattern recognition and survival analysis to translational research in the health and life sciences, an uniﬁed framework for answering scientiﬁc subsequently facilitating translational medicine. In par- and clinical questions in pathology. ticular, the abundance of heterogeneous data sources with a substantial amount of randomness and noise Figure 1 depicts a schematic overview of the ﬁeld and poses challenging problems for statistics and machine the three major parts it consists of: data generation, im- learning. Automatic processing of this wealth of data age analysis and medical statistics. 1 Preprint, June 29, 2010 ##LTLine## ##LTLine## ##LTLine##

text: A

text: revised

text: version

text: of

text: this

text: manuscript

text: was

text: published

text: in

text: CMIG

text: (PMID:

text: Please

text: cite

text: the

text: ﬁnal

text: version:

text: “Computational

text: Pathology:

text: Challenges

text: and

text: Promises

text: for

text: Tissue

text: Analysis”,

text: Thomas

text: J.

text: Fuchs

text: and

text: Joachim

text: M.

text: Buhmann,

text: Computerized

text: Medical

text: Imaging

text: and

text: Graphics,

text: Volume

text: Issue

text: Computational

label: title

text: Pathology:

text: Challenges

text: and

text: Promises

text: for

text: Tissue

text: Analysis

text: Thomas

label: author

text: J.

text: Fuchsa,b,

text: Joachim

text: M.

text: Buhmanna,b

text: aDepartment

text: of

text: Computer

text: Science,

text: ETH

text: Zurich,

text: Universitaetstrasse

text: Zurich,

text: Switzerland

text: bCompetence

text: Center

text: for

text: Systems

text: Physiology

text: and

text: Metabolic

text: Diseases,

text: ETH

text: Zurich,

text: Schafmattstr.

text: Zurich,

text: Switzerland

text: Abstract

text: The

label: abstract

text: histological

text: assessment

text: of

text: human

text: tissue

text: has

text: emerged

text: as

text: the

text: key

text: challenge

text: for

text: detection

text: and

text: treatment

text: of

text: cancer.

text: A

text: plethora

text: of

text: different

text: data

text: sources

text: ranging

text: from

text: tissue

text: microarray

text: data

text: to

text: gene

text: expression,

text: proteomics

text: or

text: metabolomics

text: data

text: provide

text: a

text: detailed

text: overview

text: of

text: the

text: health

text: status

text: of

text: a

text: patient.

text: Medical

text: doctors

text: need

text: to

text: assess

text: these

text: information

text: sources

text: and

text: they

text: rely

text: on

text: data

text: driven

text: automatic

text: analysis

text: tools.

text: Methods

text: for

text: classiﬁcation,

text: grouping

text: and

text: segmentation

text: of

text: heterogeneous

text: data

text: sources

text: as

text: well

text: as

text: regression

text: of

text: noisy

text: dependencies

text: and

text: estimation

text: of

text: survival

text: probabilities

text: enter

text: the

text: processing

text: workﬂow

text: of

text: a

text: pathology

text: diagnosis

text: system

text: at

text: various

text: stages.

text: This

text: paper

text: reports

text: on

text: state-of-the-art

text: of

text: the

text: design

text: and

text: effectiveness

text: of

text: computational

text: pathology

text: workﬂows

text: and

text: it

text: discusses

text: future

text: research

text: directions

text: in

text: this

text: emergent

text: ﬁeld

text: of

text: medical

text: informatics

text: and

text: diagnostic

text: machine

text: learning.

text: Keywords:

text: Computational

text: Pathology,

text: Machine

text: Learning,

text: Medical

text: Imaging,

text: Survival

text: Statistics,

text: Cancer

text: Research

text: Contents

text: promises

text: a

text: standardized

text: and

text: hopefully

text: more

text: objective

text: diagnosis

text: of

text: the

text: disease

text: state

text: of

text: a

text: patient

text: than

text: manual

text: Computational

text: Pathology:

text: The

text: systems

text: view

text: inspection

text: can

text: provide

text: today.

text: An

text: automatic

text: computa-

text: Data:

text: Tissue

text: and

text: Ground

text: Truth

text: tional

text: pathology

text: pipeline

text: also

text: enables

text: the

text: medical

text: user

text: to

text: quantitatively

text: benchmark

text: the

text: processing

text: pipeline

text: and

text: Imaging:

text: From

text: Classical

text: Image

text: Processing

text: to

text: Statistical

text: to

text: identify

text: error

text: sensitive

text: processing

text: steps

text: which

text: can

text: Pattern

text: Recognition

text: substantially

text: degrade

text: the

text: ﬁnal

text: prediction

text: of

text: survival

text: Statistics:

text: Survival

text: Analysis

text: and

text: Machine

text: Learning

text: in

text: times.

text: Medical

text: Statistics

text: The

text: Computational

text: Pathology

text: Pipeline:

text: A

text: holistic

text: View

text: Deﬁnition

text: Future

text: Directions

text: Computational

text: Pathology

text: as

text: well

text: as

text: the

text: medical

text: dis-

text: cipline

text: Pathology

text: is

text: a

text: wide

text: and

text: diverse

text: ﬁeld

text: which

text: en-

text: Computational

text: Pathology:

text: The

text: systems

text: view

text: compass

text: scientiﬁc

text: research

text: as

text: well

text: as

text: day-to-day

text: work

text: in

text: medical

text: clinics.

text: The

text: following

text: deﬁnition

text: is

text: an

text: at-

text: Modern

text: pathology

text: studies

text: of

text: biopsy

text: tissue

text: encom-

text: tempt

text: for

text: a

text: concise

text: and

text: practical

text: description

text: of

text: this

text: pass

text: multiple

text: stainings

text: of

text: histological

text: material,

text: ge-

text: novel

text: ﬁeld:

text: nomics

text: and

text: proteomics

text: analyses

text: as

text: well

text: as

text: compara-

text: tive

text: statistical

text: analyses

text: of

text: patient

text: data.

text: Pathology

text: lays

text: Computational

text: Pathology

text: investigates

text: a

text: com-

text: not

text: only

text: a

text: scientiﬁc

text: foundation

text: for

text: clinical

text: medicine

text: plete

text: probabilistic

text: treatment

text: of

text: scientiﬁc

text: and

text: but

text: also

text: serves

text: as

text: a

text: bridge

text: between

text: the

text: fundamental

text: clinical

text: workﬂows

text: in

text: general

text: pathology,

text: i.e.

text: sciences

text: in

text: natural

text: science,

text: medicine

text: and

text: patient

text: care.

text: it

text: combines

text: experimental

text: design,

text: statistical

text: Therefore,

text: it

text: can

text: be

text: viewed

text: as

text: one

text: of

text: the

text: key

text: hubs

text: for

text: pattern

text: recognition

text: and

text: survival

text: analysis

text: to

text: translational

text: research

text: in

text: the

text: health

text: and

text: life

text: sciences,

text: an

text: uniﬁed

text: framework

text: for

text: answering

text: scientiﬁc

text: subsequently

text: facilitating

text: translational

text: medicine.

text: In

text: par-

text: and

text: clinical

text: questions

text: in

text: pathology.

text: ticular,

text: the

text: abundance

text: of

text: heterogeneous

text: data

text: sources

text: with

text: a

text: substantial

text: amount

text: of

text: randomness

text: and

text: noise

text: Figure

text: depicts

text: a

text: schematic

text: overview

text: of

text: the

text: ﬁeld

text: and

text: poses

text: challenging

text: problems

text: for

text: statistics

text: and

text: machine

text: the

text: three

text: major

text: parts

text: it

text: consists

text: of:

text: data

text: generation,

text: im-

text: learning.

text: Automatic

text: processing

text: of

text: this

text: wealth

text: of

text: data

text: age

text: analysis

text: and

text: medical

text: statistics.

text: Preprint,

text: June

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: A revised version of this manuscript was published in CMIG (PMID: 18982583). Please cite the ﬁnal version: “Computational Pathology: Challenges and Promises for Tissue Analysis”, Thomas J. Fuchs and Joachim M. Buhmann, Computerized Medical Imaging and Graphics, Volume 35, Issue 7, 515–530, 2011. RCC remains controversial. Although many parame- high-throughput analysis. ters have been tested for prognostic signiﬁcance, only a 2.3. Analyzing Pathologists few have achieved general acceptance in clinical prac- tice. An especially interesting observation of [6] is that To assess the inter and intra variability of patholo- multivariate Cox proportional hazards regression mod- gists we designed three different labeling experiments els including multiple clinical and pathologic covari- for the major tasks involved in TMA analysis. To fa- ates were more accurate in predicting patient outcome cilitate the labeling process for trained pathologists we than the TNM staging system. On one hand this ﬁnding developed software suite which allows the user to view demonstrates the substantial difﬁculty of the task and on single TMA spots and which provides zooming and the other hand it is a motivation for research in compu- scrolling capabilities. The expert can annotate the im- tational pathology to develop robust machine learning age with vectorial data in SVG (support vector graph- frameworks for reliable and objective prediction of dis- ics) format and he/she can mark cell nuclei, vessels and ease progression. other biological structures. In addition each structure can be labeled with a class which is encoded by its color. 2.2. Tissue Microarrays To increase usability and the adoption in hospitals we speciﬁcally designed the software for tablet PC so that a The tissue microarray (TMA) technology signiﬁ- pathologist can perform all operations with a pen alone cantly accelerated studies seeking for associations be- in a simple and efﬁcient manner. Figure 3 depicts the tween molecular changes and clinical endpoints [7]. In graphical user interfaces of the three applications. this technology, 0.6mm tissue cylinders are extracted Nuclei Detection: The most tedious labeling task from primary tumor material of hundreds of different is the detection of cell nuclei. In this experiment two patients and these cylinders are subsequently embed- experts on renal cell carcinoma exhaustively labeled a ded into a recipient tissue block. Sections from such quarter of each of the 9 spots from the previous exper- array blocks can then be used for simultaneous in situ iment. Overall each expert independently marked the analysis of hundreds or thousands of primary tumors on center, the approximate radius and the class of more DNA, RNA, and protein level (cf. 2). These results can than 2000 nuclei. Again a tablet PC was used so it then be integrated with expression proﬁle data which was possible to split up the work into several sessions is expected to enhance the diagnosis and prognosis of and the experts could use the machine at their conve- ccRCC [8, 3, 9]. The high speed of arraying, the lack of nience. The user detects nuclei by marking the location a signiﬁcant damage to donor blocks, and the regular ar- with the pen on the tablet and indicates the diameter by rangement of arrayed specimens substantially facilitates moving the pen. A circular semi-transparent polygon automated analysis. is then drawn to mark the nucleus. The ﬁnal step con- Although the production of tissue microarrays is an sists of choosing a class for the nucleus. In this setting almost routine task for most laboratories, the evaluation it was either black for cancerous nuclei or red for nor- of stained tissue microarray slides remains tedious hu- mal ones. This task has to be repeated for each nucleus man annotation work, it is time consuming and prone to on each spot. Finally it is possible to show and hide error. Furthermore, the signiﬁcant intratumoral hetero- the annotation to gain an overview over the original tis- geneity of RCC results in high interobserver variabil- sue. Figure 4 depicts a quarter of one of the RCC TMA ity. The variable architecture of RCC also results in a spots together with the annotation and the inter expert difﬁcult assessment of prognostic parameters. Current disagreement. image analysis software requires extensive user inter- The average precision of one pathologist compared to action to properly identify cell populations, to select re- the other is 0.92 and the average recall amounts to 0.91. gions of interest for scoring, to optimize analysis param- These performance numbers show that even detecting eters and to organize the resulting raw data. Because of nuclei on an histological slide is by far not an easy or these drawbacks in current software, pathologists typi- undisputed task. cally collect tissue microarray data by manually assign- Nuclei Classiﬁcation: The third experiment was de- ing a composite staining score for each spot - often dur- signed to evaluate the inter and intra pathologist vari- ing multiple microscopy sessions over a period of days. ability for nuclei classiﬁcation, i.e. determining if a Such manual scoring can result in serious inconsisten- nucleus is normal/benign or abnormal/malignant. This cies between data collected during different microscopy step crucially inﬂuences the ﬁnal outcome due to the sessions. Manual scoring also introduces a signiﬁcant fact that the percentage of staining is only estimated on bottleneck that hinders the use of tissue microarrays in the subset of cancerous nuclei. In the experiment, 180 3 Preprint, June 29, 2010 ##LTLine##

text: A

text: revised

text: version

text: of

text: this

text: manuscript

text: was

text: published

text: in

text: CMIG

text: (PMID:

text: Please

text: cite

text: the

text: ﬁnal

text: version:

text: “Computational

text: Pathology:

text: Challenges

text: and

text: Promises

text: for

text: Tissue

text: Analysis”,

text: Thomas

text: J.

text: Fuchs

text: and

text: Joachim

text: M.

text: Buhmann,

text: Computerized

text: Medical

text: Imaging

text: and

text: Graphics,

text: Volume

text: Issue

text: RCC

text: remains

text: controversial.

text: Although

text: many

text: parame-

text: high-throughput

text: analysis.

text: ters

text: have

text: been

text: tested

text: for

text: prognostic

text: signiﬁcance,

text: only

text: a

label: section

text: Analyzing

text: Pathologists

text: few

text: have

text: achieved

text: general

text: acceptance

text: in

text: clinical

text: prac-

text: tice.

text: An

text: especially

text: interesting

text: observation

text: of

text: is

text: that

text: To

text: assess

text: the

text: inter

text: and

text: intra

text: variability

text: of

text: patholo-

text: multivariate

text: Cox

text: proportional

text: hazards

text: regression

text: mod-

text: gists

text: we

text: designed

text: three

text: different

text: labeling

text: experiments

text: els

text: including

text: multiple

text: clinical

text: and

text: pathologic

text: covari-

text: for

text: the

text: major

text: tasks

text: involved

text: in

text: TMA

text: analysis.

text: To

text: fa-

text: ates

text: were

text: more

text: accurate

text: in

text: predicting

text: patient

text: outcome

text: cilitate

text: the

text: labeling

text: process

text: for

text: trained

text: pathologists

text: we

text: than

text: the

text: TNM

text: staging

text: system.

text: On

text: one

text: hand

text: this

text: ﬁnding

text: developed

text: software

text: suite

text: which

text: allows

text: the

text: user

text: to

text: view

text: demonstrates

text: the

text: substantial

text: difﬁculty

text: of

text: the

text: task

text: and

text: on

text: single

text: TMA

text: spots

text: and

text: which

text: provides

text: zooming

text: and

text: the

text: other

text: hand

text: it

text: is

text: a

text: motivation

text: for

text: research

text: in

text: compu-

text: scrolling

text: capabilities.

text: The

text: expert

text: can

text: annotate

text: the

text: im-

text: tational

text: pathology

text: to

text: develop

text: robust

text: machine

text: learning

text: age

text: with

text: vectorial

text: data

text: in

text: SVG

text: (support

text: vector

text: graph-

text: frameworks

text: for

text: reliable

text: and

text: objective

text: prediction

text: of

text: dis-

text: ics)

text: format

text: and

text: he/she

text: can

text: mark

text: cell

text: nuclei,

text: vessels

text: and

text: ease

text: progression.

text: other

text: biological

text: structures.

text: In

text: addition

text: each

text: structure

text: can

text: be

text: labeled

text: with

text: a

text: class

text: which

text: is

text: encoded

text: by

text: its

text: color.

text: Tissue

text: Microarrays

text: To

text: increase

text: usability

text: and

text: the

text: adoption

text: in

text: hospitals

text: we

text: speciﬁcally

text: designed

text: the

text: software

text: for

text: tablet

text: PC

text: so

text: that

text: a

text: The

text: tissue

text: microarray

text: (TMA)

text: technology

text: signiﬁ-

text: pathologist

text: can

text: perform

text: all

text: operations

text: with

text: a

text: pen

text: alone

text: cantly

text: accelerated

text: studies

text: seeking

text: for

text: associations

text: be-

text: in

text: a

text: simple

text: and

text: efﬁcient

text: manner.

text: Figure

text: depicts

text: the

text: tween

text: molecular

text: changes

text: and

text: clinical

text: endpoints

text: In

text: graphical

text: user

text: interfaces

text: of

text: the

text: three

text: applications.

text: this

text: technology,

text: tissue

text: cylinders

text: are

text: extracted

text: Nuclei

text: Detection:

text: The

text: most

text: tedious

text: labeling

text: task

text: from

text: primary

text: tumor

text: material

text: of

text: hundreds

text: of

text: different

text: is

text: the

text: detection

text: of

text: cell

text: nuclei.

text: In

text: this

text: experiment

text: two

text: patients

text: and

text: these

text: cylinders

text: are

text: subsequently

text: embed-

text: experts

text: on

text: renal

text: cell

text: carcinoma

text: exhaustively

text: labeled

text: a

text: ded

text: into

text: a

text: recipient

text: tissue

text: block.

text: Sections

text: from

text: such

text: quarter

text: of

text: each

text: of

text: the

text: spots

text: from

text: the

text: previous

text: exper-

text: array

text: blocks

text: can

text: then

text: be

text: used

text: for

text: simultaneous

text: in

text: situ

text: iment.

text: Overall

text: each

text: expert

text: independently

text: marked

text: the

text: analysis

text: of

text: hundreds

text: or

text: thousands

text: of

text: primary

text: tumors

text: on

text: center,

text: the

text: approximate

text: radius

text: and

text: the

text: class

text: of

text: more

text: DNA,

text: RNA,

text: and

text: protein

text: level

text: (cf.

text: These

text: results

text: can

text: than

text: nuclei.

text: Again

text: a

text: tablet

text: PC

text: was

text: used

text: so

text: it

text: then

text: be

text: integrated

text: with

text: expression

text: proﬁle

text: data

text: which

text: was

text: possible

text: to

text: split

text: up

text: the

text: work

text: into

text: several

text: sessions

text: is

text: expected

text: to

text: enhance

text: the

text: diagnosis

text: and

text: prognosis

text: of

text: and

text: the

text: experts

text: could

text: use

text: the

text: machine

text: at

text: their

text: conve-

text: ccRCC

text: The

text: high

text: speed

text: of

text: arraying,

text: the

text: lack

text: of

text: nience.

text: The

text: user

text: detects

text: nuclei

text: by

text: marking

text: the

text: location

text: a

text: signiﬁcant

text: damage

text: to

text: donor

text: blocks,

text: and

text: the

text: regular

text: ar-

text: with

text: the

text: pen

text: on

text: the

text: tablet

text: and

text: indicates

text: the

text: diameter

text: by

text: rangement

text: of

text: arrayed

text: specimens

text: substantially

text: facilitates

text: moving

text: the

text: pen.

text: A

text: circular

text: semi-transparent

text: polygon

text: automated

text: analysis.

text: is

text: then

text: drawn

text: to

text: mark

text: the

text: nucleus.

text: The

text: ﬁnal

text: step

text: con-

text: Although

text: the

text: production

text: of

text: tissue

text: microarrays

text: is

text: an

text: sists

text: of

text: choosing

text: a

text: class

text: for

text: the

text: nucleus.

text: In

text: this

text: setting

text: almost

text: routine

text: task

text: for

text: most

text: laboratories,

text: the

text: evaluation

text: it

text: was

text: either

text: black

text: for

text: cancerous

text: nuclei

text: or

text: red

text: for

text: nor-

text: of

text: stained

text: tissue

text: microarray

text: slides

text: remains

text: tedious

text: hu-

text: mal

text: ones.

text: This

text: task

text: has

text: to

text: be

text: repeated

text: for

text: each

text: nucleus

text: man

text: annotation

text: work,

text: it

text: is

text: time

text: consuming

text: and

text: prone

text: to

text: on

text: each

text: spot.

text: Finally

text: it

text: is

text: possible

text: to

text: show

text: and

text: hide

text: error.

text: Furthermore,

text: the

text: signiﬁcant

text: intratumoral

text: hetero-

text: the

text: annotation

text: to

text: gain

text: an

text: overview

text: over

text: the

text: original

text: tis-

text: geneity

text: of

text: RCC

text: results

text: in

text: high

text: interobserver

text: variabil-

text: sue.

text: Figure

text: depicts

text: a

text: quarter

text: of

text: one

text: of

text: the

text: RCC

text: TMA

text: ity.

text: The

text: variable

text: architecture

text: of

text: RCC

text: also

text: results

text: in

text: a

text: spots

text: together

text: with

text: the

text: annotation

text: and

text: the

text: inter

text: expert

text: difﬁcult

text: assessment

text: of

text: prognostic

text: parameters.

text: Current

text: disagreement.

text: image

text: analysis

text: software

text: requires

text: extensive

text: user

text: inter-

text: The

text: average

text: precision

text: of

text: one

text: pathologist

text: compared

text: to

text: action

text: to

text: properly

text: identify

text: cell

text: populations,

text: to

text: select

text: re-

text: the

text: other

text: is

text: and

text: the

text: average

text: recall

text: amounts

text: to

text: gions

text: of

text: interest

text: for

text: scoring,

text: to

text: optimize

text: analysis

text: param-

text: These

text: performance

text: numbers

text: show

text: that

text: even

text: detecting

text: eters

text: and

text: to

text: organize

text: the

text: resulting

text: raw

text: data.

text: Because

text: of

text: nuclei

text: on

text: an

text: histological

text: slide

text: is

text: by

text: far

text: not

text: an

text: easy

text: or

text: these

text: drawbacks

text: in

text: current

text: software,

text: pathologists

text: typi-

text: undisputed

text: task.

text: cally

text: collect

text: tissue

text: microarray

text: data

text: by

text: manually

text: assign-

text: Nuclei

text: Classiﬁcation:

text: The

text: third

text: experiment

text: was

text: de-

text: ing

text: a

text: composite

text: staining

text: score

text: for

text: each

text: spot

text: often

text: dur-

text: signed

text: to

text: evaluate

text: the

text: inter

text: and

text: intra

text: pathologist

text: vari-

text: ing

text: multiple

text: microscopy

text: sessions

text: over

text: a

text: period

text: of

text: days.

text: ability

text: for

text: nuclei

text: classiﬁcation,

text: i.e.

text: determining

text: if

text: a

text: Such

text: manual

text: scoring

text: can

text: result

text: in

text: serious

text: inconsisten-

text: nucleus

text: is

text: normal/benign

text: or

text: abnormal/malignant.

text: This

text: cies

text: between

text: data

text: collected

text: during

text: different

text: microscopy

text: step

text: crucially

text: inﬂuences

text: the

text: ﬁnal

text: outcome

text: due

text: to

text: the

text: sessions.

text: Manual

text: scoring

text: also

text: introduces

text: a

text: signiﬁcant

text: fact

text: that

text: the

text: percentage

text: of

text: staining

text: is

text: only

text: estimated

text: on

text: bottleneck

text: that

text: hinders

text: the

text: use

text: of

text: tissue

text: microarrays

text: in

text: the

text: subset

text: of

text: cancerous

text: nuclei.

text: In

text: the

text: experiment,

text: Preprint,

text: June

text: ##LTLine##