8000 ENH speed up LDL by better handling q==0 · scikit-learn/scikit-learn@4e1a696 · GitHub
[go: up one dir, main page]

Skip to content

Commit 4e1a696

Browse files
committed
ENH speed up LDL by better handling q==0
1 parent 1d13089 commit 4e1a696

File tree

2 files changed

+17
-22
lines changed

2 files changed

+17
-22
lines chang 10000 ed

sklearn/linear_model/_linear_loss.py

Lines changed: 9 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -727,7 +727,7 @@ class Multinomial_LDL_Decomposition:
727727

728728
def __init__(self, *, proba, proba_sum_to_1=True):
729729
self.p = proba
730-
self.q = 1 - np.cumsum(self.p, axis=1)
730+
self.q = 1 - np.cumsum(self.p, axis=1) # contiguity of p
731731
self.proba_sum_to_1 = proba_sum_to_1
732732
if self.p.dtype == np.float32:
733733
eps = 2 * np.finfo(np.float32).resolution
@@ -745,10 +745,13 @@ def __init__(self, *, proba, proba_sum_to_1=True):
745745
self.q[self.q <= eps] = 0.0
746746
self.p[self.p <= eps] = 0.0
747747
d = self.p * self.q
748+
# From now on, self.q is always used in the denominator. We handle q == 0 by
749+
# setting q to 1 whenever q == 0 such that a division of q is a no-op in this
750+
# case.
751+
self.q[self.q == 0] = 1
748752
if self.proba_sum_to_1:
749753
# If q_{i - 1} = 0, then also q_i = 0.
750-
mask = self.q[:, 1:-1] == 0
751-
d[:, 1:-1] /= self.q[:, :-2] + mask # d[:, -1] = 0 anyway
754+
d[:, 1:-1] /= self.q[:, :-2] # d[:, -1] = 0 anyway.
752755
else:
753756
d[:, 1:] /= self.q[:, :-1]
754757
self.sqrt_d = np.sqrt(d)
@@ -785,11 +788,7 @@ def sqrt_D_Lt_matmul(self, x):
785788
for i in range(0, n_classes - 1): # row i
786789
# L_ij = -p_i / q_j, we need transpose L'
787790
for j in range(i + 1, n_classes): # column j
788-
if self.proba_sum_to_1:
789-
mask = self.q[:, i] == 0
790-
x[:, i] -= self.p[:, j] / (self.q[:, i] + mask) * x[:, j]
791-
else:
792-
x[:, i] -= self.p[:, j] / self.q[:, i] * x[:, j]
791+
x[:, i] -= self.p[:, j] / self.q[:, i] * x[:, j]
793792
x *= self.sqrt_d
794 10000 793
return x
795794

@@ -825,12 +824,7 @@ def L_sqrt_D_matmul(self, x):
825824
for i in range(n_classes - 1, 0, -1): # row i
826825
# L_ij = -p_i / q_j
827826
for j in range(0, i): # column j
828-
if self.proba_sum_to_1:
829-
term = self.p[:, i] * x[:, j]
830-
mask = term == 0
831-
x[:, i] -= term / (self.q[:, j] + mask)
832-
else:
833-
x[:, i] -= self.p[:, i] / self.q[:, j] * x[:, j]
827+
x[:, i] -= self.p[:, i] / self.q[:, j] * x[:, j]
834828
return x
835829

836830
def inverse_L_sqrt_D_matmul(self, x):
@@ -861,12 +855,7 @@ def inverse_L_sqrt_D_matmul(self, x):
861855
n_classes = self.p.shape[1]
862856
for i in range(n_classes - 1, 0, -1): # row i
863857
if i > 0:
864-
if self.proba_sum_to_1:
865-
# 0 / something = 0
866-
mask = self.p[:, i] == 0
867-
fj = self.p[:, i] / (self.q[:, i - 1] + mask)
868-
else:
869-
fj = self.p[:, i] / self.q[:, i - 1]
858+
fj = self.p[:, i] / self.q[:, i - 1]
870859
else:
871860
fj = self.p[:, i]
872861
for j in range(0, i): # column j

sklearn/linear_model/tests/test_linear_loss.py

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -436,9 +436,12 @@ def test_multinomial_LDL_decomposition_binomial_single_point():
436436
"""
437437
p0, p1 = 0.2, 0.8
438438
p = np.array([[p0, p1]])
439+
# Note that LDL sets q = 1 whenever q = 0 for easier handling of divisions by zero.
440+
# We compare those values to "zero", to make that clear.
441+
zero = 1
439442

440443
LDL = Multinomial_LDL_Decomposition(proba=p)
441-
assert_allclose(LDL.q[0, :], [1 - p0, 0])
444+
assert_allclose(LDL.q[0, :], [1 - p0, zero])
442445
assert_allclose(LDL.sqrt_d[0, :] ** 2, [p0 * (1 - p0), 0])
443446

444447
# C = diag(D) L' x with x = [[1, 0]] (n_samples=1, n_classes=2)
@@ -594,7 +597,10 @@ def test_multinomial_LDL_decomposition(global_random_seed):
594597
assert_allclose(np.sum(p, axis=1), np.ones(shape=n_samples))
595598

596599
LDL = Multinomial_LDL_Decomposition(proba=p)
597-
assert_allclose(LDL.q, 1 - np.cumsum(LDL.p, axis=1))
600+
# Note that LDL sets q = 1 whenever q = 0 for easier handling of divisions by zero.
601+
# As q[:, -1] = 0 if p sums to 1, we do not compare the last values corresponding
602+
# to the last class.
603+
assert_allclose(LDL.q[:, :-1], 1 - np.cumsum(LDL.p, axis=1)[:, :-1])
598604

599605
# C = diag(D) L' x with x = X @ coef = raw_prediction
600606
C = LDL.sqrt_D_Lt_matmul(raw_prediction.copy())

0 commit comments

Comments
 (0)
0