Thuật toán học máy để dự đoán thứ tự sự kiện?

Question

Câu hỏi học máy đơn giản. Có lẽ rất nhiều cách để giải quyết việc này:

Có một dòng vô hạn của 4 sự kiện thể:

'event_1', 'event_2', 'event_4', 'event_4'

Các sự kiện không đến ở trong trật tự hoàn toàn ngẫu nhiên. Chúng tôi sẽ giả định rằng có một số mẫu phức tạp theo thứ tự mà hầu hết các sự kiện đến, và phần còn lại của các sự kiện chỉ là ngẫu nhiên. Tuy nhiên, chúng tôi không biết các mẫu trước.

Sau mỗi sự kiện được nhận, tôi muốn dự đoán sự kiện tiếp theo sẽ dựa trên thứ tự các sự kiện đã xảy ra trong quá khứ. Vì vậy, câu hỏi của tôi là: Thuật toán học máy nào tôi nên sử dụng cho dự đoán này?

Các dự đoán sau đó sẽ được kể lại những gì sự kiện tiếp theo thực sự là:

Predictor=new_predictor() 

prev_event=False 
while True: 
    event=get_event() 
    if prev_event is not False: 
     Predictor.last_event_was(prev_event) 
    predicted_event=Predictor.predict_next_event(event) 

Câu hỏi đặt ra trong bao lâu của một lịch sử mà các yếu tố dự báo nên duy trì, vì duy trì lịch sử vô hạn sẽ không được tốt. Tôi sẽ để điều này cho bạn trả lời. Câu trả lời không thể được infinte mặc dù cho thực tiễn.

Vì vậy, tôi tin rằng các dự đoán sẽ phải được thực hiện với một số loại lịch sử lăn. Thêm một sự kiện mới và hết hạn một sự kiện cũ do đó sẽ là khá hiệu quả, và không yêu cầu xây dựng lại toàn bộ mô hình dự báo, ví dụ.

Mã cụ thể, thay vì tài liệu nghiên cứu, sẽ thêm cho tôi giá trị to lớn cho câu trả lời của bạn. Thư viện Python hoặc C là tốt đẹp, nhưng bất cứ điều gì sẽ làm.

Cập nhật: Và điều gì xảy ra nếu nhiều sự kiện có thể xảy ra đồng thời trên mỗi vòng. Điều đó có thay đổi giải pháp không?

Answer 1

Câu hỏi đặt ra trong bao lâu của một lịch sử mà các yếu tố dự báo nên duy trì

Câu trả lời duy nhất là "nó phụ thuộc".

Tùy thuộc vào mức độ chính xác của điều này. Tôi không tin rằng chiến lược này có thể chính xác 100% ngay cả với một lịch sử vô hạn. Hãy thử một lịch sử 10 và bạn sẽ nhận được độ chính xác x%, sau đó thử 100 và bạn sẽ nhận được độ chính xác y%, v.v ...

Cuối cùng bạn sẽ tìm thấy hệ thống chính xác như bạn mong muốn được hoặc bạn sẽ thấy sự gia tăng độ chính xác sẽ không đáng để tăng độ dài lịch sử (và tăng mức sử dụng bộ nhớ, thời gian xử lý, v.v ...). Tại thời điểm này, một trong hai công việc được thực hiện, hoặc bạn cần phải tìm một chiến lược mới.

Đối với những gì tôi đáng giá, hãy xem xét một mạng lưới thần kinh "mềm" đơn giản có thể là một kế hoạch tốt hơn.

Answer 2

Chúng tôi vừa nghiên cứu về branch-predictors trong kiến ​​trúc máy tính (Vì bộ xử lý sẽ mất quá nhiều thời gian để thực sự đánh giá điều kiện nếu (EXPRESSION), nó cố gắng 'đoán' và tiết kiệm thời gian theo cách đó). Tôi chắc chắn nhiều nghiên cứu hơn đã được thực hiện trong lĩnh vực này, nhưng đó là tất cả những gì tôi có thể nghĩ đến vào lúc này.

Tôi chưa thấy thiết lập duy nhất như của bạn, vì vậy tôi nghĩ bạn có thể cần thực hiện một số thử nghiệm sơ bộ của riêng bạn. Hãy thử chạy giải pháp của bạn cho X số giây với một lịch sử của N khe, tỷ lệ chính xác là gì? Và so sánh điều đó với cùng X cố định và các khe N lịch sử khác nhau để cố gắng tìm tỷ lệ bộ nhớ-lịch sử tốt nhất (vẽ đồ thị chúng ra).

Nếu có nhiều sự kiện có thể xảy ra tương tự ... đó là một chút tâm trí bẻ cong, phải có một số hạn chế ở đó: nếu vô số sự kiện xảy ra cùng một lúc? Uhoh, đó là tính toán không thể đối với bạn. Tôi sẽ thử cách tiếp cận tương tự như chỉ một sự kiện tại một thời điểm, ngoại trừ nơi dự đoán được kích hoạt dự đoán nhiều sự kiện cùng một lúc.

Answer 3

Đây thực chất là một vấn đề dự đoán chuỗi, vì vậy bạn muốn mạng nơron tái diễn hoặc các mô hình Markov ẩn.

Nếu bạn chỉ có thời gian cố định để xem lại, các cách tiếp cận cửa sổ thời gian có thể đủ. Bạn lấy dữ liệu chuỗi và chia nó thành các cửa sổ chồng chéo có độ dài n. (ví dụ: bạn tách một chuỗi ABCDEFG thành ABC, BCD, CDE, DEF, EFG). Sau đó, bạn đào tạo một hàm xấp xỉ (ví dụ: mạng nơron hoặc hồi quy tuyến tính) để ánh xạ các phần n-1 đầu tiên của cửa sổ đó lên phần thứ n.

Dự đoán của bạn sẽ không thể nhìn lại trong thời gian dài hơn kích thước cửa sổ của bạn. RNN và HMM có thể làm như vậy theo lý thuyết, nhưng khó điều chỉnh hoặc đôi khi không hoạt động.

(Nhà nước của nghệ thuật hiện thực RNN có thể được tìm thấy trong PyBrain http://pybrain.org)

Cập nhật: Đây là mã pybrain cho vấn đề của bạn. (Tôi đã không kiểm tra nó, có thể có một số lỗi chính tả và các công cụ, nhưng cấu trúc tổng thể nên làm việc.)

from pybrain.datasets import SequentialDataSet 
from pybrain.supervised.trainers import BackpropTrainer 
from pybrain.tools.shortcuts import buildNetwork 
from pybrain.structure import SigmoidLayer 

INPUTS = 4 
HIDDEN = 10 
OUTPUTS = 4 

net = buildNetwork(INPUTS, HIDDEN, OUTPUTS, hiddenclass=LSTMLayer, outclass=SigmoidLayer, recurrent=True) 

ds = SequentialDataSet(INPUTS, OUTPUTS) 

# your_sequences is a list of lists of tuples which each are a bitmask 
# indicating the event (so 1.0 at position i if event i happens, 0.0 otherwise) 

for sequence in your_sequences: 
    for (inpt, target) in zip(sequence, sequence[1:]): 
     ds.newSequence() 
     ds.appendLinked(inpt, target) 

net.randomize() 

trainer = BackpropTrainer(net, ds, learningrate=0.05, momentum=0.99) 
for _ in range(1000): 
    print trainer.train() 

này sẽ đào tạo mạng lưới tái phát cho 1000 kỷ nguyên và in ra các lỗi sau mỗi thời đại. Sau đó, bạn có thể kiểm tra các dự đoán chính xác như sau:

net.reset() 
for i in sequence: 
    next_item = net.activate(i) > 0.5 
    print next_item 

Điều này sẽ in một loạt các phép toán cho mọi sự kiện.

Answer 4

Thay vì giữ một lịch sử đầy đủ, người ta có thể giữ thông tin tổng hợp về quá khứ (cùng với một lịch sử tương đối ngắn trượt, được sử dụng như đầu vào logic Predictor).

Một thực hiện dự kiến ​​có thể đi như thế này:
Tóm lại: Quản lý một tập hợp các chuỗi Markov của thứ tự tăng dần, và chấm điểm và trung bình dự đoán của họ

• giữ một bảng số lượng sự kiện riêng lẻ, mục đích là tính toán xác suất của bất kỳ sự kiện nào trong số 4 sự kiện khác nhau, mà không liên quan đến bất kỳ chuỗi nào.
• giữ một bảng bigram đếm, tức là tổng số sự kiện được quan sát [cho đến nay]
  Bảng bắt đầu trống, khi sự kiện thứ hai quan sát được, chúng tôi có thể lưu trữ bigram đầu tiên, với tổng số là 1.upond sự kiện thứ ba, bigram được thực hiện của các sự kiện thứ 2 và thứ 3 là "thêm" vào bảng: hoặc tăng số lượng của một bigram hiện có hoặc thêm với số lượng ban đầu 1, như là một mới (không bao giờ nhìn thấy-đến-xa) bigram . v.v.
  Song song, giữ tổng số các ký tự lớn trong bảng.
  Bảng này và tổng kiểm đếm cho phép tính xác suất của một sự kiện cụ thể, dựa trên sự kiện trước đó.
• Theo cách tương tự, hãy giữ một bảng số lượng trigram, và tổng số trigram được xem (lưu ý rằng số này sẽ bằng số lượng các ký tự lớn, trừ một số, kể từ trigram đầu tiên được thêm một sự kiện sau bigram đầu tiên và sau đó một trong số đó được thêm vào mỗi sự kiện mới). Bảng ba chiều này cho phép tính toán xác suất của một sự kiện cụ thể dựa trên hai sự kiện trước đó.
• tương tự như vậy, giữ bảng cho N-Gram, lên đến, nói, 10-gram (thuật toán sẽ cho biết nếu chúng ta cần phải tăng hoặc giảm này).
• giữ cửa sổ trượt vào 10 sự kiện cuối cùng.
• Các bảng trên cung cấp cơ sở để dự đoán; ý tưởng chung là:
  • sử dụng công thức thể hiện xác suất của sự kiện tiếp theo dưới dạng trung bình được cân nhắc của xác suất riêng lẻ dựa trên các N-gam khác nhau.
  • thưởng cho độ dài N-gram cá nhân tốt hơn bằng cách tăng trọng lượng tương ứng trong công thức; trừng phạt độ dài tồi tệ hơn theo kiểu ngược lại. (Hãy coi chừng xác suất cận biên của các sự kiện riêng lẻ cần được tính đến khi chúng tôi ưu tiên N-grams xảy ra để dự đoán các sự kiện thường xuyên nhất, bất kể giá trị dự đoán tương đối nghèo liên quan đến chúng)
  • Khi hệ thống đã "nhìn thấy "đủ sự kiện, hãy xem các giá trị hiện tại cho trọng số liên quan đến N-Gram dài và nếu chúng tương đối cao, hãy cân nhắc thêm bảng để giữ thông tin tổng hợp về N-Gram lớn hơn. (Điều này không may làm tổn thương algorightm cả về không gian và thời gian)

Có thể có vài biến thể trên logic chung mô tả ở trên. Đặc biệt trong việc lựa chọn các số liệu cụ thể được sử dụng để "cấp" chất lượng dự đoán của các độ dài N-Gram riêng lẻ.
Các cân nhắc khác nên được đặt liên quan đến phát hiện và thích ứng với các thay đổi có thể có trong phân phối sự kiện (ở trên giả định nguồn sự kiện chung ergodic). Một cách tiếp cận có thể là sử dụng hai bộ bảng (kết hợp các xác suất tương ứng), và định kỳ thả nội dung của tất cả các bảng của một trong các bộ. Chọn đúng thời điểm cho các reset là một doanh nghiệp khó khăn, về cơ bản cân bằng sự cần thiết cho khối lượng đáng kể thống kê của lịch sử và sự cần thiết cho thời gian đủ ngắn vì sợ tôi bỏ lỡ các điều chế ngắn hơn ...

Answer 5

Bộ vi xử lý sử dụng một vài thủ thuật thực sự nhẹ để dự đoán liệu một câu lệnh chi nhánh có phân nhánh hay không. Điều này giúp chúng với lớp lót ống hiệu quả. Họ có thể không được như chung như mô hình Markov ví dụ, nhưng họ là thú vị vì sự đơn giản của họ. Here is the Wikipedia article on branch prediction. Xem bão hòa Counter và Hai cấp thích ứng Predictor