Database Reference
In-Depth Information
Table 5.6 Frobenius error norms for simulations over virtual sessions
1 recommendation
2 recommendations
Linear
Nonlinear
Linear
Nonlinear
c
u
c
u
c
u
c
k
F
u
#sessions
kΔ
k
F
kΔ
k
F
kΔ
k
F
kΔ
k
F
kΔ
k
F
kΔ
k
F
kΔ
kΔ
k
F
10
1.032
1.642
1.215
1.428
0.579
1.748
1.086
1.950
100
0.505
0.522
0.654
0.781
0.852
1.763
0.240
1.744
1,000
0.233
0.299
0.231
0.256
0.711
1.820
0.102
1.763
10,000
0.057
0.171
0.072
0.093
1.126
1.723
0.040
1.752
100,000
0.021
0.054
0.045
0.088
0.963
1.800
0.020
1.720
1,000,000
0.005
0.012
0.015
0.022
0.579
1.748
0.082
1.679
p
a
s
0
ss
0
We separately consider the matrices of the conditional probabilities
P
c
:¼
AðÞ
and the unconditional ones
P
u
:
¼
{
p
ss
0
}
s ∈ S
,
s
0
∈ A
(
s
)
. Let the symbol
tilde represent the probabilities estimated by the algorithms of Sect.
5.2.3
. Then we
use the Frobenius norm of the differences matrices
S
,
s
0
∈
s
∈
Δ
α
:¼ P
α
P
α
,
α∈
fg
to
c
;
estimate the error. The
Frobenius norm
of a matrix
A
is defined as
m
,
n
:¼
X
2
,
A
2
F
mn
kk
a
ij
∈
R
:
ð
5
:
29
Þ
i¼
1
,
j¼
1
Table
5.6
contains the errors
kΔ
α
k
F
for the function of case a) for one and two
recommendations depending on the number of sessions. We compare the linear
Algorithm 5.2 with the nonlinear Algorithm 5.3.
The result confirms that for one recommendation both algorithms work equally
well. However, for two recommendations the linear algorithm fails completely, and
the nonlinear works only for the conditional probabilities. The reason for this
behavior is that the unconditional probabilities are not estimated correctly.
Since the linear Algorithm 5.2 is based on a joined estimation of conditional and
unconditional probabilities, this also leads to wrong estimates of the conditional
probabilities. In contrast, the nonlinear Algorithms 5.3 and 5.4 both estimate the
conditional probabilities independent on the unconditional ones.
What is the reason for the wrong calculation of unconditional probabilities? We
suffer from a special case here. If the number of recommendations
k
is equal to the
number of successor states
m
, the unconditional probabilities cannot change because
the fixed component includes all unconditional probabilities
Π
a
¼ p
ss
f
s
0
∈S
a
.More-
over, the same applies to the case where the
k ¼ m-1
. This follows from the relation
X
p
ss
0
¼
1
X
s
0
∈S
a
p
ss
0
, where the right-hand side is fixed, and the fact that the
s
0
2S
a
“free” set
S
a
¼ s
0
2Sf g
consists of one element only. Notice also that this problem
is truly a special case and far from reality since usually the number of successor states
available is quite high, so that
m k
.
To overcome this problem, we just need to omit the recommendations from time
to time. In our test, each 10th request did not issue recommendations, i.e., then
k ¼
0 applied. The result is shown in Table
5.7
. Now the algorithms work correctly.
