Bias Mimicking: A Simple Sampling Approach for Bias Mitigation
Maan Qraitem, Kate Saenko, et al.
CVPR 2023
Let @@@@ be an integral domain, P(@@@@) the integral domain of polynomials over @@@@. Let P, Q 蜒 P(@@@@) with m @@@@ deg (P) 蠅 n = deg (Q) > 0. Let M be the matrix whose determinant defines the resultant of P and Q. Let Mij be the submatrix of M obtained by deleting the last j rows of P coefficients, the last j rows of Q coefficients and the last 2j+1 columns, excepting column m 舒 n 舒 i 舒 j (0 蠄 i 蠄 j < n). The polynomial Rj(x) = ∑ii=0 det (Mij)xi is the j-t subresultant of P and Q, R0 being the resultant. If b = £(Q), the leading coefficient of Q, then exist uniquely R, S 蜒 P(@@@@) such that bm-n+1 P = QS + R with deg (R) < n; define R(P, Q) = R. Define Pi 蜒 P(F), F the quotient field of @@@@, inductively: P1 = P, P2 = Q, P3 = RP1, P2 Pi-2 = R(Pi, Pi+1)/c⥈i-1+1i for i 蠅 2 and ni+1 > 0, where ci = £(Pi), ni = deg (Pi) and ⥈i = ni 舒 ni+1. P1, P2, 舰, Pk, for k 蠅 3, is called a reduced polynomial remainder sequence. Some of the main results are: (1) Pi 蜒 P(@@@@) for 1 蠄 i 蠄 k; (2) Pk = ŷ AkRnk-1-1, when Ak = k-2i-2c⥈i-1(⥈i-1)i; (3) c⥈k-1-1k Pk = ŷAk+1Rnk; (4) Rj = 0 for nk < j < nk-1 舒 1. Taking @@@@ to be the integers I, or Pr(I), these results provide new algorithms for computing resultant or greatest common divisors of univariate or multivariate polynomials. Theoretical analysis and extensive testing on a high-speed computer show the new g.c.d. algorithm to be faster than known algorithms by a large factor. When applied to bivariate polynomials, for example this factor grows rapidly with the degree and exceeds 100 in practical cases. © 1967, ACM. All rights reserved.
Maan Qraitem, Kate Saenko, et al.
CVPR 2023
Gang Liu, Michael Sun, et al.
ICLR 2025
Kaiyuan Zhang, Guanhong Tao, et al.
ICLR 2023
L. Joskowicz, Elisha Sacks
aaai 1994