用机器学习的方法理解社会媒体

Understanding

Social

Media

with

Machine

Learning

Xiaojin

Zhu

Department

of

Computer

Sciences

University

of

Wisconsin–Madison,

USA

CCF/ADL

Beijing

20231

/

95OutlineSpatio-Temporal

Signal

Recovery

from

Social

MediaMachine

Learning

Basics

Probability

Statistical

Estimation

Decision

Theory

Graphical

Models

Regularization

Stochastic

ProcessesSocioscope:

A

Probabilistic

Model

for

Social

MediaCase

Study:

Roadkill2

/

95

Spatio-Temporal

Signal

Recovery

from

Social

MediaOutlineSpatio-Temporal

Signal

Recovery

from

Social

MediaMachine

Learning

Basics

Probability

Statistical

Estimation

Decision

Theory

Graphical

Models

Regularization

Stochastic

ProcessesSocioscope:

A

Probabilistic

Model

for

Social

MediaCase

Study:

Roadkill3

/

95

Spatio-Temporal

Signal

Recovery

from

Social

MediaSpatio-temporal

Signal:

When,

Where,

How

Much

Direct

instrumental

sensing

is

di

cult

and

expensive4

/

95

Spatio-Temporal

Signal

Recovery

from

Social

MediaHumans

as

Sensors5

/

95

Spatio-Temporal

Signal

Recovery

from

Social

MediaHumans

as

Sensors

Not

“hot

trend”

discovery:

We

know

what

event

we

want

to

monitor

Not

natural

language

processing

for

social

media:

We

are

given

a

reliable

text

classifier

for

“hit”

Our

task:

precisely

estimating

a

spatiotemporal

intensity

function

fst

of

a

pre-defined

target

phenomenon.6

/

95

Spatio-Temporal

Signal

Recovery

from

Social

MediaChallenges

of

Using

Humans

as

Sensors

Keyword

doesn’t

always

mean

eventIII

was

just

told

I

look

like

dead

crow.Don’t

blame

me

if

one

day

I

treat

you

like

a

dead

crow.Human

sensors

aren’t

under

our

controlLocation

stamps

may

be

erroneous

or

missingIIII3%

have

GPS

coordinates:

(-98.24,

23.22)47%

have

valid

user

profile

location:

Bristol,

UK,

New

York50%

don’t

have

valid

location

informationHogwarts,

In

the

tra

c..blah,

Sitting

On

A

Taco7

/

95

Spatio-Temporal

Signal

Recovery

from

Social

MediaProblem

Definition

Input:

A

list

of

time

and

location

stamps

of

the

target

posts.

Output:

fst

Intensity

of

target

phenomenon

at

location

s

(e.g.,

New

York)

and

time

t

(e.g.,

0-1am)8

/

95

Spatio-Temporal

Signal

Recovery

from

Social

MediaWhy

Simple

Estimation

is

Bad

fst

=

xst,

the

count

of

target

posts

in

bin

(s,t)

Justification:

MLE

of

the

model

x

⇠

Poisson(f)

However,IIIPopulation

Bias:

Assume

fst

=

fs0t0,

if

more

users

in

(s,t),

thenxst

>

xs0t0Imprecise

location:

Posts

without

location

stamp,

noisy

user

profilelocationZero/Low

counts:

If

we

don’t

see

tweets

from

Antarctica,

no

penguinsthere?9

/

95

Machine

Learning

BasicsOutlineSpatio-Temporal

Signal

Recovery

from

Social

MediaMachine

Learning

Basics

Probability

Statistical

Estimation

Decision

Theory

Graphical

Models

Regularization

Stochastic

ProcessesSocioscope:

A

Probabilistic

Model

for

Social

MediaCase

Study:

Roadkill10

/

95OutlineSpatio-Temporal

Signal

Recovery

from

Social

MediaMachine

Learning

Basics

Probability

Statistical

Estimation

Decision

Theory

Graphical

Models

Regularization

Stochastic

ProcessesSocioscope:

A

Probabilistic

Model

for

Social

MediaCase

Study:

Roadkill11

/

95Probability

The

probability

of

a

discrete

random

variable

A

taking

the

value

a

is

P(A

=

a)

2

[0,1].

Sometimes

written

as

P(a)

when

no

danger

of

confusion.

Normalization

Joint

probability

P(A

=

a,B

=

b)

=

P(a,b),

the

two

events

both

happen

at

the

same

time.

Marginalization

P(A

=

a)

=

B”.

P(a,b)

The

product

rule

P(a,b)

=

P(a)P(b|a)

=

P(b)P(a|b).12

/

95Bayes

rule

P(a|b)

=P(b|a)P(a).In

general,

P(a|b,C)

=P(b|C)Rp(D|✓)p(✓)d✓

the

evidence,Bayes

RuleP(b)

P(b|a,C)P(a|C)where

C

can

be

one

or

morerandom

variables.Bayesian

approach:

when

✓

is

model

parameter,

D

is

observed

data,we

havep(✓|D)

=p(D|✓)p(✓)

p(D),Rp(D|✓)d✓

6=

1),IIIIp(✓)

is

the

prior,p(D|✓)

the

likelihood

function

(of

✓,

not

normalized:p(D)

=p(✓|D)

the

posterior.13

/

95Independence

The

product

rule

can

be

simplified

as

P(a,b)

=

P(a)P(b)

i↵

A

and

B

are

independent

Equivalently,

P(a|b)

=

P(a),

P(b|a)

=

P(b).14

/

95R

x2P(x1

<

X

<

x2)

=Z

1R

1Probability

density

A

continuous

random

variable

x

has

a

probability

density

function

(pdf)

p(x)

2

[0,1].

p(x)

>

1

is

possible!

Integrates

to

1.

x1Marginalization

p(x)

=

p(x)dx

=

1

1p(x)dx

1

p(x,y)dy15

/

95pExpectation

and

Variance

The

expectation

(“mean”

or

“average”)

of

a

function

f

under

the

probability

distribution

P

is

EP[f]

=

P(a)f(a)

a

Ep[f]

=

p(x)f(x)dx

x

In

particular

if

f(x)

=

x,

this

is

the

mean

of

the

random

variable

x.

The

variance

of

f

isVar(f)

=

E[(f(x)E[f(x)])2]

=

E[f(x)2]E[f(x)]2The

standard

deviation

is

std(f)

=Var(f).16

/

95Multivariate

Statistics

When

x,y

are

vectors,

E[x]

is

the

mean

vector

Cov(x,y)

is

the

covariance

matrix

with

i,j-th

entry

being

Cov(xi,yj).Cov(x,y)

=

Ex,y[(xE[x])(yE[y])]

=

Ex,y[xy]E[x]E[y]17

/

958

✓

◆<px(1:8

✓:Qdk=1

pkPdSome

Discrete

Distributions

a

if

P(X

=

a)

=

1

Binomial.

n

(number

of

trials)

and

p

(head

probability)p)n

x

for

x

=

0,1,...,notherwise

n

f(x)

=

x

0Bernoulli.

Binomial

with

n

=

1.Multinomial

p

=

(p1,...,pd)>

(d-sided

die)f(x)

=

nx1,...,xd◆xk<

0

if

k=1

xk

=

notherwise18

/

95More

Discrete

Distributions

Poisson.

X

⇠

Poisson(

)

if

xx!

f(x)

=

efor

x

=

0,1,2,....

the

rate

or

intensity

parametermean:,

variance:

2)

thenX1

+

X2

⇠

Poisson(

1

+

2).This

is

a

distribution

on

unbounded

counts

with

a

probability

massfunction“hump”

(mode

at

d

e1).19

/

95Gaussian

(Normal):

X

⇠

N(µ,Some

Continuous

Distributions2)with

parameters

µ

2

R

(themean)

and

2

(the

variance)

1f(x)

=

p2⇡exp✓(x2µ)22◆.is

the

standard

deviation.If

µ

=

0,=

1,

X

has

a

standard

normal

distribution.

2),

then

Z

=

(X

2

2i

i20

/

95Some

Continuous

Distributions

Multivariate

Gaussian.

Let

x,µ

2

Rd,

⌃

2

S+

d

a

symmetric,

positive

definite

matrix

of

size

d

⇥

d.

Then

X

⇠

N(µ,⌃)

with

PDF

1

1

1

f(x)

=

exp

(x

µ)

⌃

(x

µ)

.

2

and

⌃

1

its

inverse21

/

95Marginal

and

Conditional

of

Gaussian

If

two

(groups

of)

variables

x,y

are

jointly

Gaussian:

xy⇠

N✓µxµy,

A

CC>

B◆(1)(Marginal)

x

⇠

N(µx,A)(Conditional)

y|x

⇠

N(µy

+

C>A1(xµx),BC>A1C)22

/

95More

Continuous

Distributions

0

with

↵

>

0.

Generalizes

factorial:

(n)

=

(n

1)!

when

n

is

a

positive

integer.

(↵

+

1)

=

↵

(↵)

for

↵

>

0.

parameter

↵

>

0

and

scale

parameter

>

0f(x)

=↵1

(↵)x↵1ex/,

x

>

0.Conjugate

prior

for

Poisson

rate.23

/

95OutlineSpatio-Temporal

Signal

Recovery

from

Social

MediaMachine

Learning

Basics

Probability

Statistical

Estimation

Decision

Theory

Graphical

Models

Regularization

Stochastic

ProcessesSocioscope:

A

Probabilistic

Model

for

Social

MediaCase

Study:

Roadkill24

/

95Parametric

Models

A

statistical

model

H

is

a

set

of

distributions.

In

machine

learning,

we

call

H

the

hypothesis

space.

A

parametric

model

can

be

parametrized

by

a

finite

number

of

parameters:

f(x)

⌘

f(x;✓)

with

parameter

✓

2

Rd:

H

=

f(x;✓)

:

✓

2

⇥

⇢

Rd

where

⇥

is

the

parameter

space.25

/

95

Machine

Learning

BasicsParametric

Models

We

denote

the

expectationE✓(g)

=Zxg(x)f(x;✓)dxE✓

means

Ex⇠f(x;✓),

not

over

di↵erent

✓’s.

data

1All

(parametric)

models

are

wrong.

Some

are

more

useful

than

others.26

/

95Nonparametric

model

A

nonparametric

model

cannot

be

parametrized

by

a

fixed

number

of

parameters.

Model

complexity

grows

indefinitely

with

sample

size

Example:

H

=

{P

:

V

arP(X)

<

1}.

Given

iid

data

x1,...,xn,

the

optimal

estimator

of

the

mean

is

again

xi.

Nonparametric

makes

weaker

model

assumptions

and

thus

is

preferred.

But

parametric

models

converge

faster

and

are

more

practical.27

/

95(

✓Estimation

X1

...Xn

that

attempts

to

estimate

a

parameter

✓.

This

is

the

“learning”

in

machine

learning!

Example:

In

classification

Xi

=

Pxi,yi)

and

bn

is

the

learned

model.

Consistent

estimators

learn

the

correct

model

with

more

training

data

eventually.28

/

95bias(✓

bn)

=

E✓(✓

bn)qThe

standard

error

of

an

estimator

is

se(✓

bn)

=Var✓(✓

bn)Pi

xi,

where

xi

⇠

N(0,1).

Then

the

standardBias

E✓

is

w.r.t.

the

joint

distribution

f(x1,...,xn;✓)

=

i=1

f(xi;✓).

The

bias

of

the

estimator

is✓ˆdeviation

of

xi

is

1

regardless

of

n.

In

contrast,

se(µ)

=

1/pn

=

n12An

estimator

is

unbiased

if

bias(✓

bn)

=

0.Example:

Let

µ

ˆ

=

n

1which

decreases

with

n.29

/

95mse(✓

bn)

=

E✓

(✓

bnMSE

The

mean

squared

error

of

an

estimator

is⇣✓)2⌘Bias-variance

decompositionmse(✓

bn)

=

bias2(✓

bn)

+

se2(✓

bn)

=

bias2(✓

bn)

+

Var✓(✓

bn)

P30

/

95YMaximum

Likelihood

Let

x1,...,xn

⇠

f(x;✓)

where

✓

2

⇥.

The

likelihood

function

isLn(✓)

=

f(x1,...,xn;✓)

=

ni=1f(xi;✓)The

log

likelihood

function

is

`n(✓)

=

logLn(✓).The

maximum

likelihood

estimator

(MLE)

is

✓

bn

=

argmax✓2⇥Ln(✓)

=

argmax✓2⇥`n(✓)31

/

95MLE

examples

The

MLE

for

p(head)

from

n

coin

flips

is

count(head)/n

for

i

Xi

and

2

=

1/n

(Xi

2.

The

MLE

does

not

always

agree

with

intuition.

The

MLE

for

X1,...,Xn

⇠

uniform(0,✓)

is

✓

b=

max(X1,...,Xn).32

/

95Properties

of

MLE

When

H

is

identifiable,

underPcertain

conditions

(see

Wasserman

parameter

✓.

That

is,

the

MLE

is

consistent.

Asymptotic

Normality:

Let

se

=

1/In(✓)

where

In(✓)

is

the

Fisher

information,

and

✓

N(0,1)

se

The

MLE

is

asymptotically

e

cient

(achieves

the

Cram´er-Rao

lower

bound),

“best”

among

unbiased

estimators.33

/

95Frequentist

statistics

Probability

refers

to

limiting

relative

frequency.

Data

are

random.

Estimators

are

random

because

they

are

functions

of

data.

Parameters

are

fixed,

unknown

constants

not

subject

to

probabilistic

statements.

Procedures

are

subject

to

probabilistic

statements,

for

example

95%

confidence

intervals

trap

the

true

parameter

value

95

Classifiers,

even

learned

with

deterministic

procedures,

are

random

because

the

training

set

is

random.

PAC

bound

is

frequentist.

Most

procedures

in

machine

learning

are

frequentist

methods.34

/

95Bayesian

statistics

Probability

refers

to

degree

of

belief.

Inference

about

a

parameter

✓

is

by

producing

a

probability

distributions

on

it.

Starts

with

prior

distribution

p(✓).

Likelihood

function

p(x

|

✓),

a

function

of

✓

not

x.

After

observing

data

x,

one

applies

the

Bayes

rule

to

obtain

the

posterior

1

=

p(✓

Z

evidence.

Prediction

by

integrating

parameters

out:

p(x

|

Data)

=

Z

p(x

|

✓)p(✓

|

Data)d✓35

/

95Frequentist

vs

Bayesian

in

machine

learning

Frequentists

produce

a

point

estimate

✓

ˆ

from

Data,

and

predict

with

p(x

|

✓

ˆ).

integrating

over

✓s.

Bayesian

integration

is

often

intractable,

need

either

“nice”

distributions

or

approximations.

The

maximum

a

posteriori

(MAP)

estimate

✓MAP

=

argmax✓p(✓

|

x)

is

a

point

estimate

and

not

Bayesian.36

/

95OutlineSpatio-Temporal

Signal

Recovery

from

Social

MediaMachine

Learning

Basics

Probability

Statistical

Estimation

Decision

Theory

Graphical

Models

Regularization

Stochastic

ProcessesSocioscope:

A

Probabilistic

Model

for

Social

MediaCase

Study:

Roadkill37

/

95✓

✓✓

✓

✓Comparing

Estimators

Training

set

D

=

(x1,...,xn)

⇠

p(x;✓)

Learned

model:

✓

ˆ⌘

✓

ˆ(D)

an

estimator

of

✓

based

on

data

D.

Loss

function

L(✓,✓

ˆ)

:

⇥

⇥

⇥

7!

R+

squared

loss

L(✓,

ˆ)

=

(✓

ˆ)2

0

✓

=

✓

ˆ

1

✓

6=

✓

ˆ

KL

loss

L(✓,

ˆ)

=

p(x;✓)log

p(x;ˆ)

dx

Since

D

is

random,

both

✓

ˆ(D)

and

L(✓,✓

ˆ)

are

random

variables38

/

95✓Risk

The

risk

R(✓,✓

ˆ)

is

the

expected

loss

R(✓,✓

ˆ)

=

ED[L(✓,✓

ˆ(D))]

ED

averaged

over

training

sets

D

sampled

from

the

true

✓

The

risk

is

the

“average

training

set”

behavior

of

a

learning

algorithm

when

the

world

is

✓

Not

computable:

we

don’t

know

which

✓

the

world

is

in.

Assume

squared

loss.

Then

R(✓,✓

ˆ1)

=

1

(hint:

variance),

R(✓,

ˆ2)

=

ED(✓

3.14)2

=

(✓

3.14)2.

Smart

learning

algorithm

✓

ˆ1

and

a

dumb

one

✓

ˆ2.

However,

for

tasks✓

2

(3.141,3.14

+

1)

the

dumb

algorithm

is

better.39

/

95

Machine

Learning

BasicsMinimax

Estimatormaximum

riskRmax(✓

ˆ)

=

supR(✓,✓

ˆ)✓

✓The

minimax

estimator

✓

ˆminimax

minimizes

the

maximum

risk

✓

ˆminimax

=

arginf

supR(✓,✓

ˆ)

ˆ

✓The

infimum

is

over

all

estimators

✓

ˆ.The

minimax

estimator

is

the

“best”

in

guarding

against

the

worstpossible

world.40

/

95OutlineSpatio-Temporal

Signal

Recovery

from

Social

MediaMachine

Learning

Basics

Probability

Statistical

Estimation

Decision

Theory

Graphical

Models

Regularization

Stochastic

ProcessesSocioscope:

A

Probabilistic

Model

for

Social

MediaCase

Study:

Roadkill41

/

95

Machine

Learning

BasicsThe

envelope

quiz42

/

95The

envelope

quiz

P(E

=

1)

=

P(E

=

0)

=

1/2

P(B

=

r

|

E

=

1)

=

1/2,P(B

=

r

|

E

=

0)

=

0

1/2?

P(B=b)

Switch.

The

graphical

model:

E

B42

/

95Probabilistic

Reasoning

The

world

is

reduced

to

a

set

of

random

variables

x1,...,xn

I

e.g.

(x1,...,xn

1)

Inference:

given

joint

distribution

p(x1,...,xn),

compute

I

p(x1,...,xn

1,xn)

1)

v

p(x1,...,xn

1,xn

=

v)

Learning:

estimate

p(x1,...,xn)

from

training

data

X(1),...,X(N),

(i)

(i)43

/

95It

is

di

cult

to

reason

with

uncertainty

joint

distribution

p(x1,...,xn)IIexponential

na¨ıve

storage

(2n

for

binary

r.v.)hard

to

interpret

(conditional

independence)

I

Often

can’t

a↵ord

to

do

it

by

brute

forceIf

p(x1,...,xn)

not

given,

estimate

it

from

dataIOften

can’t

a↵ord

to

do

it

by

brute

force44

/

95Graphical

models

Graphical

models:

e

cient

representation,

inference,

and

learning

on

p(x1,...,xn),

exactly

or

approximately

Two

main

“flavors”:IIdirected

graphical

models

=

Bayesian

Networks

(often

frequentistinstead

of

Bayesian)undirected

graphical

models

=

Markov

Random

FieldsKey

idea:

make

conditional

independence

explicit45

/

95Bayesian

Network

Directed

graphical

models

are

also

called

Bayesian

networks

A

directed

graph

has

nodes

X

=

(x1,...,xn),

some

of

them

connected

by

directed

edges

xi

!

xj

A

cycle

is

a

directed

path

x1

!

...

!

xk

where

x1

=

xk

A

directed

acyclic

graph

(DAG)

contains

no

cycles

A

Bayesian

network

on

the

DAG

is

a

family

of

distributions

satisfying{p

|

p(X)

=Yip(xi

|

Pa(xi))}where

Pa(xi)

is

the

set

of

parents

of

xi.p(xi

|

Pa(xi))

is

the

conditional

probability

distribution

(CPD)

at

xiBy

specifying

the

CPDs

for

all

i,

we

specify

a

particular

distributionp(X)46

/

95Example:

Alarm

Binary

variablesGraphical

Models

P(E)=0.002

E

A

M

P(M

|

A)

=

0.7

P(M

|

~A)

=

0.01Machine

Learning

Basics

P(B)=0.001

BP(A

|

B,

E)

=

0.95P(A

|

B,

~E)

=

0.94P(A

|

~B,

E)

=

0.29P(A

|

~B,

~E)

=

0.001

J

P(J

|

A)

=

0.9

P(J

|

~A)

=

0.05

P(B,⇠

E,A,J,⇠

M)=

P(B)P(⇠

E)P(A

|

B,⇠

E)P(J

|

A)P(⇠

M

|

A)

0.7)⇡

.00025347

/

95

Machine

Learning

BasicsExample:

Naive

Bayes

yy...x1xdx

dp(y,x1,...xd)

=

p(y)

i=1

p(xiUsed

extensively

in

natural

language

processingPlate

representation

on

the

right48

/

95

Machine

Learning

BasicsNo

Causality

WhatsoeverP(A)=aP(B|A)=bP(B|~A)=cABBAP(B)=ab+(1−a)cP(A|B)=ab/(ab+(1−a)c)P(A|~B)=a(1−b)/(1−ab−(1−a)c)The

two

BNs

are

equivalent

in

all

respects

Bayesian

networks

imply

no

causality

at

all

They

only

encode

the

joint

probability

distribution

(hence

correlation)

However,

people

tend

to

design

BNs

based

on

causal

relations49

/

95Conditional

Independence

Two

A,

B

are

independent

if

P(A,B)

=

P(A)P(B)

or

P(A|B)

=

P(A)

(the

two

are

equivalent)

Two

A,

B

are

conditionally

independent

given

C

if

two

are

equivalent)

This

extends

to

groups

of

Conditional

independence

in

a

BN

is

precisely

specified

by

d-separation

(“directed

separation”)50

/

95d-Separation

Case

1:

Tail-to-TailCABCABA,

B

in

general

dependentA,

B

conditionally

independent

given

C

(observed

nodes

are

shaded)An

observed

C

is

a

tail-to-tail

node,

blocks

the

undirected

path

A-B51

/

95d-Separation

Case

2:

Head-to-TailACBACBA,

B

in

general

dependentA,

B

conditionally

independent

given

CAn

observed

C

is

a

head-to-tail

node,

blocks

the

path

A-B52

/

95d-Separation

Case

3:

Head-to-HeadABABCCA,

B

in

general

independentA,

B

conditionally

dependent

given

C,

or

any

of

C’s

descendantsAn

observed

C

is

a

head-to-head

node,

unblocks

the

path

A-B53

/

95The

path

is

head-to-tail

or

tail-to-tail

at

x

and

x

2

C,

ord-Separation

Any

groups

of

nodes

A

and

B

are

conditionally

independent

given

another

group

C,

if

all

undirected

paths

from

any

node

in

A

to

any

node

in

B

are

blocked

A

path

is

blocked

if

it

includes

a

node

x

such

that

eitherIIThe

path

is

head-to-head

at

x,

and

neither

x

nor

any

of

itsdescendants

is

in

C.54

/

95d-Separation

Example

1

The

undirected

path

from

A

to

B

is

unblocked

by

E

(because

of

C),

and

is

not

blocked

by

F

A,

B

dependent

given

CABFEC55

/

95d-Separation

Example

2

The

path

from

A

to

B

is

blocked

both

at

E

and

F

A,

B

conditionally

independent

given

FABFEC56

/

951

YC(XC)Markov

Random

Fields

Undirected

graphical

models

are

also

called

Markov

Random

Fields

The

e

ciency

of

directed

graphical

model

(acyclic

graph,

locally

normalized

CPDs)

also

makes

it

restrictive

A

clique

C

in

an

undirected

graph

is

a

fully

connected

set

of

nodes

(note:

full

of

loops!)

Define

a

nonnegative

potential

function

C

An

undirected

graphical

model

is

a

family

of

distributions

satisfying)Z

=RQC

Z

CC(XC)dX

is

the

partition

function57

/

95Example:

A

Tiny

Markov

Random

Fieldx1x2Cx1,x2

2

{

1,1}A

single

cliqueC(x1,x2)

=eax1x2

1

ax1x2Z

=

(ea

+

e

a

+

e

a

+

ea)p(1,1)

=

p(

1,

1)

=

ea/(2ea

+

2ea)p(

1,1)

=

p(1,

1)

=

ea/(2ea+

2ea)When

the

parameter

a

>

0,

favor

homogeneous

chainsWhen

the

parameter

a

<

0,

favor

inhomogeneous

chains58

/

95XLog

Linear

Models

Real-valued

feature

functions

f1(X),...,fk(X)

Real-valued

weights

w1,...,wkp(X)

=1Zexp

ki=1wifi(X)!59

/

95XX0exp@p✓(x)

=

✓sxs

+✓stxsxtA

Machine

Learning

BasicsExample:

The

Ising

Modelθs

xsxtθst1This

is

an

undirected

model

with

x

2

{0,1}.

1

Z

s2V

(s,t)2E

fs(X)

=

xs,

fst(X)

=

xsxtws

=✓s,

wst

=✓st60

/

95XX0exp@⇢c

ys

=

0✓stxsxtA

Machine

Learning

BasicsExample:

Image

Denoising[From

Bishop

PRML]

p✓(X

|

Y

)

=argmaxXP(X|Y

)

1

1Z

✓s

=noisy

image

✓sxs

+

s2V

(s,t)2E

c

ys

=

161

/

95Example:

Gaussian

Random

Fieldp(X)

⇠

N(µ,⌃)

=

1(2⇡)n/2|⌃|1/2exp✓12(Xµ)>⌃1(Xµ)◆Multivariate

Gaussian

1xi,xj

are

conditionally

independent

given

all

other

variables,

if

andonly

if

⌦ij

=

0When

⌦ij

6=

0,

there

is

an

edge

between

xi,xj62

/

95Conditional

Independence

in

Markov

Random

Fields

Two

group

of

variables

A,

B

are

conditionally

independent

given

another

group

C,

if:

A,

B

become

disconnected

by

removing

C

and

all

edges

involving

CA

CB63

/

95OutlineSpatio-Temporal

Signal

Recovery

from

Social

MediaMachine

Learning

Basics

Probability

Statistical

Estimation

Decision

Theory

Graphical

Models

Regularization

Stochastic

ProcessesSocioscope:

A

Probabilistic

Model

for

Social

MediaCase

Study:

Roadkill64

/

95Regularization

for

Maximum

Likelihood

Can

overfit.

Regularized

likelihood

`n(✓)

+

⌦(✓)

⌦(✓)

is

the

regularizer,

for

example

⌦(✓)

=

k✓k2.

Coincides

with

MAP

estimate

with

prior

distributionp(✓)

/

exp(⌦(✓))65

/

95kxiGraph-based

regularization

Nodes:

x1

...xn,

✓

=

f

=

(f(x1),...,f(xn))

Edges:

similarity

weights

computed

from

features,

e.g.,IIk-nearest-neighbor

graph,

unweighted

(0,

1

weights)fully

connected

graph,

weight

decays

with

distancexjk2/

2Iw

=

exp✏-radius

graphAssumption

Nodes

connected

by

heavy

edge

tend

to

have

the

samevalue.

x1

x3

x266

/

95

Machine

Learning

BasicsGraph

energy

f

incurs

the

energyXi⇠jwij(f(xi)f(xj))2smooth

f

has

small

energyconstant

f

has

zero

energy67

/

95An

electric

network

interpretation

Edges

are

resistors

with

conductance

wij

Nodes

clamped

at

voltages

specified

by

f

Energy

=

heat

generated

by

the

network

in

unit

time+1

voltRij=

1wij1068

/

95The

graph

Laplacian

We

can

express

the

energy

of

f

in

closed-form

using

the

graph

Laplacian.

I

symmetric,

non-negative

Diagonal

degree

matrix

D:

Dii

=

j=1

Wij

Graph

Laplacian

matrix=

DWThe

energyXi⇠jwij(f(xi)f(xj))2

=

f>

f69

/

95XGaussian

likelihood

yi

=

f(xi)

+

✏i

where

✏i

⇠

N(0,

2),

andGraph

Laplacian

as

a

Regularizer

Regression

problem

with

training

data

xi

2

Rd,yi

2

R,

i

=

1...n

Allow