IBM

research

Tokyo Research Laboratory

Task 1:

A Semi-supervised Approach to Indoor Location Estimation
Where am I ?
Hisashi Kashima, Shoko Suzuki, Shohei Hido, Yuta Tsuboi,
Toshihiro Takahashi, Tsuyoshi Ide, Rikiya Takahashi, and Akira Tajima

IBM Research, Tokyo Research Laboratory
Data Analytics Group

Presentation for task 1:

A Semi-supervised Approach to Indoor Location Estimation
We formulated task1 as a semi-supervised learning [1] problem
We employed the label propagation [2] as the semi-supervised learning method– A multi-class version of the label propagation method– Design of similarity measure using spatial information(=RSS values) and temporal
information (=time stamps)[1] X. Zhu. Semi-supervised learning literature survey. Technical Report, TR 1530, University of Wisconsin Madison, 2006.
[2] X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, 2003.

© Copyright IBM Corporation 2007

IBMTokyo Research Laboratory research

Task Review: Indoor location estimation by using machine learning
Problem setting:– You want to know where you are in some building– In the building, there are several access points emitting radio signals– You have a client device by which you can know signal strength from each access point
Difficulty: Triangulation is unsatisfactory because of high uncertainty in signals
Solution: Apply machine learning techniques to estimate locations from received signal strengths

Where am I ?

access point 2© Copyright IBM Corporation 2007

access point 1
IBMTokyo Research Laboratory research

The task is formulated as a semi-supervised learning problem
Given: the i-th data is given as a tuple of (x(i), TID(i), t (i), y(i))– spatial information: x(i) 2 X = <101 is the received signal strength (RSS) values– temporal information: TID(i) (trace ID) and t(i) (time ID) indicate the time of the data observed– classs label: y(i) 2Y = {1, 2, ..., 247} is a location label given only for a small fraction of the data
• Semi-supervised learning problem
Goal: predict y(i) for 8i 2 UNLABELLED DATA whose location labels are “ ? ”(=not given)– Transduction problem
data ID (i)trace ID(TID)

12

13
4562
3time ID(t)location label(y 2 {1, 2, ..., 247])

x1x2

x3

x4

…

x101

16-58-88-100-100

…

-802?

-58-95-100-100

…

-100

3

1-65-95-100-100…

-75

123-62-83-59

-90

…

-93

1?

-62

-83-59

-90

…

-100

2

9Missing values are filled with-67
-83lowest-59-84…
-100 (theRSS value)

-100

…

…

…

…

IBM
Tokyo Research Laboratory research
…

…

…

…

…

…

© Copyright IBM Corporation 2007

RSS values ( x 2 [-100, 0]101 )We employed the label propagation as a semi-supervised learning method
Label propagation tries to assign a location label to each observation with satisfying that
1. labeled instances have the given labels, and2. similar instances have the similar class labels
Example of two-class {A, B} case
– f : the probability of the location label of the i-th instance being A– (1 - f ): the probability of the location label of the i-th instance being B– $ means “two observations are similar to each other”

estimated by using rule 2
f=1
location labelis A© Copyright IBM Corporation 2007

f = .66

f = .33

f=0

f=0location labelis BIBM
Tokyo Research Laboratory researchWe employed the label propagation as a semi-supervised learning method
Label propagation tries to realize label assignments satisfying that
1. labeled instances have the given labels, and2. similar instances have the similar class labels(Multi-class) label propagation is cast as an optimization problem
minimizef( i, j )( i, j ) w

y(f ( i )(c) – f ( j )(c) )2where• f (i) (c) : the probability of the location label of the i-th instance being c• w( i, j ) : the similarity measure between the i-th and j-th examples
s.t. for each labeled instance i,• f ( i ) (c) = 1, if c is the true class label• f ( i ) (c) = 0, otherwise
Prediction is made by argmaxc f ( i ) (c) for each i
Instead of a closed form solution requiring the inverse of a large matrix,
we can use the following simple iterative updatef ( i )(c) (© Copyright IBM Corporation 2007

(jw( i, j )cf ( j ) (c) )(jw( i, j ) )IBMTokyo Research Laboratory researchSimilarity measure w( i, j ) is defined by RSS values and time stamps
We have to define the similarity measure w( i, j ) used in the label propagation
Each instance is accompanied by two types of information
1. spatial information: RSS values
2. temporal information: a time stamp
Two instances are similar if– their RSS values are similar, or– their time stamps are similar
The similarity measure is defined by the maximum of two similarity measuresw ( i, j ) = max { wX( i, j ) , wT( i, j ) }where• wX( i, j ) : similarity based on spatial information (=RSS values)• wT( i, j ) : similarity based on temporal information (=time stamps)© Copyright IBM Corporation 2007

IBMTokyo Research Laboratory researchRobust similarity measure based on spatial information: wX( i, j )Since RSS values are noisy,
we need a similarity robust to noise caused by reflection, interference, and shielding
RSS-based similarity wX( i, j ) is defined aswX( i, j ) = exp ( – || x ( i ) – x ( j ) ||p /)where||. ||p is the p-norm (in submission, p = 0.5 (0.5-norm) )is a constant scale parameter (in submission,= 0.5 )We used p-norm with p < 1 , which puts more importanceon presence/absence of signals than the amount of change
Robust to drastic change of each RSS value
Sensitive to change of multiple RSS values

2-norm 1-norm 0.5-norm

level curve of p-norm© Copyright IBM Corporation 2007

IBMTokyo Research Laboratory researchSimilarity measure based on temporal information: wT( i, j )Time-stamp-based similarity wT( i, j ) is defined aswT( i, j ) =, if i and j are consecutive observations in a trace= 0, otherwise– In submission, we used=1

Probably, we could improve the similarity further ...
––= 0.01 performs better
Similarity function like that for RSS values© Copyright IBM Corporation 2007

IBMTokyo Research Laboratory researchSo, what was most important for performance improvement ?
Design of similarity function is crucial
Design of similarity function contributed most to improvement of prediction accuracy– Use of 0.5-norm in RSS similarity– Use of time-stamp-based similarity

Nearest neighbour with 2-norm RSS similarity (baseline)+7% accuracy
Nearest neighbour with 0.5-norm RSS similarity+ 1% accuracy
Label propagation with 0.5-norm RSS similarity+ 5% accuracy
Label propagation with 0.5-norm RSS similarity and time stamp similarity© Copyright IBM Corporation 2007

IBMTokyo Research Laboratory research

Conclusion and future work
We applied a multi-class version of the label propagation to this task
We designed a similarity measure using spatial information(=RSS values) and temporal
information (=time stamps)– Metric design >> semi-supervised learning
It is very difficult to beat the simple methods such as kNN

Possible future work includes– Refinement of the time-based similarity– Out-of-sample prediction• In real situation, test data are not given in advance of test phase• Approximation or explicit learning of the mapping function© Copyright IBM Corporation 2007

IBMTokyo Research Laboratory researchThank you

WE ARE...
Hisashi Kashima, Shoko Suzuki, Shohei Hido, Yuta Tsuboi,
Toshihiro Takahashi, Tsuyoshi Ide, Rikiya Takahashi, and Akira TajimaIBM Research, Tokyo Research Laboratory
Data Analytics Group© Copyright IBM Corporation 2007

IBMTokyo Research Laboratory research