Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Data Science] Làm trơn Laplace

    Nếu một giá trị đặc trưng chưa từng xuất hiện cùng lớp ccc trong dữ liệu huấn luyện, likelihood ước lượng theo tần suất sẽ bằng 0 và "giết chết" toàn bộ tích xác suất. Làm trơn Laplace (add-one) khắc phục điều này:

    P(x=v∣y=c)=count(x=v,y=c)+1count(y=c)+VP(x = v \mid y = c) = \frac{\text{count}(x=v, y=c) + 1}{\text{count}(y=c) + V}P(x=v∣y=c)=count(y=c)+Vcount(x=v,y=c)+1​

    trong đó VVV là số giá trị khả dĩ của đặc trưng xxx. Cho nnn bản ghi (xi,yi)(x_i, y_i)(xi​,yi​), số giá trị VVV, và truy vấn (v,c)(v, c)(v,c), hãy tính xác suất đã làm trơn. Lớp ccc đảm bảo xuất hiện ít nhất một lần.

    • Định dạng đầu vào:

      Dòng đầu: hai số nguyên nnn VVV. nnn dòng tiếp theo: hai số nguyên xix_ixi​ yiy_iyi​. Dòng cuối: hai số nguyên vvv ccc.

    • Ràng buộc đầu vào:

      1 ≤ n ≤ 10000; 1 ≤ V ≤ 100; 0 ≤ x, v ≤ V−1 hoặc giá trị rời rạc bất kỳ trong miền V giá trị; 0 ≤ y, c ≤ 20.

    • Định dạng đầu ra:

      Một dòng duy nhất: xác suất đã làm trơn Laplace, làm tròn 2 chữ số thập phân ({:.2f}).

    Ví dụ:

    Đầu vào:

    6 3
1 0
2 0
1 0
1 1
2 1
2 1
3 0

    Đầu ra:

    0.17

    Giải thích:

    x=3 chưa từng xuất hiện cùng lớp 0 (count = 0), lớp 0 có 3 bản ghi, V=3 ⇒ P = (0+1)/(3+3) = 1/6 ≈ 0.17 (không bị bằng 0 nhờ Laplace)

    Đang tải editor...