Flashcard ứng dụng thuật toán SuperMemo (Phần 1 + 2)

1.1. Flashcard

Flashcard hoặc Flash Card là loại thẻ mang thông tin (từ, số hoặc cả hai), được sử dụng cho việc học bài trên lớp hoặc trong nghiên cứu cá nhân. người dùng sẽ viết một câu hỏi ở mặt trước thẻ và một câu trả lời ở trang sau. Người ta thường dùng flashcard học từ vựng tiếng Anh rất hiệu quả. Ngoài ra có thể dùng flashcard để học ngày tháng năm lịch sử, công thức hoặc bất kỳ vấn đề gì có thể được học thông qua định dạng một câu hỏi và câu trả lời. Fl ashcard được sử dụng rộng rãi như một cách rèn luyện để hỗ trợ ghi nhớ bằng cách lặp đi lặp lại cách nhau.

Flashcard là một công cụ ôn tập rất hiệu quả. Theo khoa học nghiên cứu, với một lượng kiến thức cần nhớ, thì sau 1 ngày tiếp thu, người học chỉ còn nhớ 35.7% lượng kiến thức và sau 1 tháng, lượng kiến thức chỉ còn khoảng 21% trong não bộ. Vì thế, việc ôn tập lại kiến thức đóng vai trò rất quan trọng trong quá trình ghi nhớ.

Không dừng lại ở tính hiệu quả cao, flashcard còn là một phương pháp học năng động. Với thiết kế nhỏ gọn, người học có thể đem flashcard theo bên mình và sử dụng mọi lúc mọi nơi.

(theo Wiki)

Ngày nay với sự phát triển của smart phone, có rất nhiều chương trình flashcard, chủ yếu dùng để học ngoại ngữ. Phần lớn các chương trình để nâng cao tính hiệu quả của việc học đều dùng một thuật toán gọi là Spaced Repetition.

1.2. Spaced Repetition

Spaced Repetition (SR) là một kỹ năng học tập dựa trên việc tính toán các khoảng thời gian giữa các lần ôn lại bài học tuỳ theo độ khó của bài học và trí nhớ của người học.

SR thích hợp trong nhiều hoàn cảnh, đặc biệt trong trường hợp người học cần phải ghi nhớ một lượng lớn nội dung, ví dụ như học từ mới ngoại ngữ.

Hình vẽ dưới đây mô tả quá trình học flashcard dựa trên SR: các thẻ trả lời đúng được đưa lên các hộp tiếp theo (hộp có số thứ tự càng lớn thì càng ít lặp lại thường xuyên) và các thẻ trả lời sai bị trả về hộp đầu tiên (lặp lại thường xuyên hơn)

1.3. Thuật toán SuperMemo

SuperMemo (Super Memory - SM) là một phương pháp học tập và phần mềm được phát triển bởi SuperMemo World và SuperMemo R&D, tác giả là Piotr Woźniak người Phần Lan từ năm 1985 tới nay. Thuật toán này dựa trên nghiên cứu về trí nhớ dài hạn và ứng dụng phương pháp SR được đề xuất bởi một số nhà tâm lý học vào đầu những năm 1930.

Các thuật toán SM gồm:

• SM-0: Thuật toán gốc (không dựa trên máy tính)
• SM-2: Dựa trên máy tính (1987), các phiên bản tiếp theo tối ưu hoá ưu điểm của thuật toán này.
• SM-15: hiện tại đang được SuperMemo sử dụng

Trong đó, SM-2 được sử dụng rộng rãi trong nhiều ứng dụng miễn phí phổ biến như Anki, Mnemosyne, Emacs Org-mode's Org-drill…

1.4. Thuật toán SM-2

Công thức:

I(1):=1
I(2):=6
for n>2 I(n):=I(n-1)*EF

Trong đó:

• I(n) (interval): trả về khoảng thời gian đối tượng sẽ lặp lại (tính bằng ngày) sau n lần thử
• EF (E-Factor): hệ số độ dễ, phản ánh độ dễ hay khó của đối tượng trong việc ghi nhớ.

EF: biến thiên từ 1.1 (khó nhất) và 2.5 (dễ nhất), mặc định khi một đối tượng được lưu vào database sẽ có Ef = 2.5. Trong quá trình học, giá trị này sẽ tăng hoặc giảm tuỳ thuộc vào sự ghi nhớ của người học.

Giá trị EF mới được tính toán dựa trên chất lượng câu trả lời của người học, lựa chọn 1 trong 6 tuỳ chọn:

• 5 - Hoàn hảo
• 4 - Trả lời chính xác nhưng còn phải đắn đo
• 3 - Trả lời chính xác nhưng gặp nhiều khó khăn
• 2 - Trả lời không chính xác, đáp án đúng dễ dàng nhớ ra
• 1 - Trả lời sai, nhớ được đáp án
• 0 - Hoàn toàn không nhớ

Công thức:

EF’:=EF+(0.1-(5-q)*(0.08+(5-q)*0.02))

Trong đó:

• EF’ - giá trị mới của E-Factor
• EF - giá trị cũ của E-Factor
• q - giá trị của câu trả lời (0~5)

Khi EF < 1.3, gán EF = 1.3 (Đối tượng có EF < 1.3 sẽ lặp lại thường xuyên gây khó chịu)

Khi giá trị câu trả lời nhỏ hơn 3, ta tiến hành lập lại đối tượng từ đầu mà không thay đổi EF (VD: I(1), I(2) coi như đối tượng được học mới)

Sau mỗi lần học của 1 ngày, lặp lại tất cả các đối tượng có giá trị trả lời (q) nhỏ hơn 4. Tiếp tục lặp lại cho đến khi toàn bộ các đối tượng có giá trị trả lời ít nhất là 4.

Trong khuôn khổ bài viết này, tôi sẽ hướng dẫn các bạn tạo 1 ứng dụng iOS Flashcard áp dụng thuật toán SM.

2.1. Tạo ứng dụng

Mở Xcode, tạo mới 1 ứng dụng iOS theo template Tabbed Application, ngôn ngữ Swift như hình dưới:

2.2. Xây dựng class áp dụng thuật toán SM-2

2.2.1. SchedulingAlgorithm

SchedulingAlgorithm là 1 abstract class, base class của các class ứng dụng thuật toán SM.

class SchedulingAlgorithm: NSObject {
    var eFactor: Double = 0

    private var _qualityResponse: Int = 0

    var qualityResponse: Int {
        get {
            return _qualityResponse
        }
        set {
            _qualityResponse = newValue
            if _qualityResponse < 3 {
                eFactor = defaultEFactor
            }
        }
    }

    var defaultEFactor: Double = 2.5

    func getNextInterval(n: Int) -> Int {
        return 0 // Abstract class
    }

    func getNewEFactor() -> Double {
        return 0 // Abstract class
    }
}

2.2.2. SM2

class SM2: SchedulingAlgorithm {
    override init() {
        super.init()
        eFactor = 2.5
        qualityResponse = 0
    }

    init(eFactor: Double, qualityResponse: Int) {
        super.init()
        self.eFactor = eFactor
        self.qualityResponse = qualityResponse
    }

    override func getNextInterval(n: Int) -> Int {
        if (n==1) {
            return 1
        }
        else if (n==2) {
            return 6
        }
        else if (n>2) {
            return Int(Double(n-1)*eFactor)
        }
        else {
            return 0
        }
    }

    override func getNewEFactor() -> Double {
        var newEFactor: Double = eFactor + (0.1-Double(5-qualityResponse)*(0.08+Double(5-qualityResponse)*0.02))

        if (newEFactor < 1.3) {
            newEFactor = 1.3
        }
        return newEFactor
    }
}

2.2.3. TestSM2

class TestSM2: NSObject {
    func testIntervals() {
        var grades = [0, 3, 4, 5, 5, 1, 4, 5, 5, 5, 4, 3, 4, 5]
        var efs = [ Double(2.5) ]
        var intervals = [1]

        for (index, grade) in enumerate(grades) {
            let sm2 = SM2(eFactor: efs[index], qualityResponse: grades[index])
            let newEF = sm2.getNewEFactor()
            let newInterval = sm2.getNextInterval(index)
            efs.append(newEF)
            intervals.append(newInterval)
        }

        for interval in intervals {
            println(interval)
        }

        for ef in efs {
            println(ef)
        }
    }
}

Hàm testIntervals trả về thời gian lặp lại tiếp theo của đối tượng (tính theo ngày) sau khi chọn câu trả lời, trong đó:

• grades: mô phỏng sự lựa chọn câu trả lời của người học
• efs: lưu lại các sự thay đổi eFactor của đối tượng sau mỗi lần người học chọn câu trả lời
• intervals: lưu lại các thời gian lặp lại

Chạy hàm test trên (có thể đặt trong viewDidLoad của ViewController) ta được kết quả như sau:

override func viewDidLoad() {
        super.viewDidLoad()

        let testSM2 = TestSM2()
        testSM2.testIntervals()
    }

Interval

1
0
1
6
3
4
10
9
11
14
17
20
22
23
25

eFactor

2.5
1.7
1.56
1.56
1.66
1.76
1.96
1.96
2.06
2.16
2.26
2.26
2.12
2.12
2.22

2.3. Tạo database CoreData

Card Entity:

#import <Foundation/Foundation.h>
#import <CoreData/CoreData.h>

@interface Card : NSManagedObject

@property (nonatomic, retain) NSString * back;
@property (nonatomic, retain) NSDate * creationTime;
@property (nonatomic, retain) NSNumber * due;
@property (nonatomic, retain) NSNumber * factor;
@property (nonatomic, retain) NSString * front;
@property (nonatomic, retain) NSString * id;
@property (nonatomic, retain) NSNumber * interval;
@property (nonatomic, retain) NSNumber * lapses;
@property (nonatomic, retain) NSDate * modificationTime;
@property (nonatomic, retain) NSNumber * queue;
@property (nonatomic, retain) NSNumber * reviews;
@property (nonatomic, retain) NSNumber * type;

@end

2.4. MagicalRecord

Sử dụng thư viện MagicalRecord để giúp đơn giản hoá việc tương tác với CoreData.

Ta sẽ dùng CocoaPod để thêm thư viện MagicalRecord.

pod 'MagicalRecord', '~> 2.3’

Cách cài đặt và sử dụng CocoaPod bạn có thể tham khảo ở trang https://cocoapods.org

2.5. Services

Ta sẽ viết các service class để tương tác với database

2.5.1. CardDto

import UIKit

enum CardType: Int {
    case New                     = 0
    case Learning                = 1
    case Due                     = 2
}

enum CardQueue: Int {
    case ScheduleBuried          = -3
    case UserBuried              = -2
    case Suspended               = -1
    case New                     = 0
    case Learning                = 1
    case Due                     = 2
}

class CardDto: NSObject {
    var id: String               = ""
    var creationTime: NSDate     = NSDate()
    var modificationTime: NSDate = NSDate()

    var type                     = CardType.New
    var queue                    = CardQueue.New
    var due                      = 0
    var interval                 = 0
    var factor: Double           = 2.5
    var reviews                  = 0
    var lapses                   = 0

    var front                    = ""
    var back                     = ""

    var qualityResponse          = -1

}

CardDto sẽ map dữ liệu với Card Entitiy.

2.5.2. Mapper

class Mapper: NSObject {

    class func mapCardDto(cardDto: CardDto, toCard card: Card) {
        card.id = cardDto.id
        card.creationTime = cardDto.creationTime
        card.modificationTime = cardDto.modificationTime
        card.type = cardDto.type.rawValue
        card.queue = cardDto.queue.rawValue
        card.due = cardDto.due
        card.interval = cardDto.interval
        card.factor = cardDto.factor
        card.reviews = cardDto.reviews
        card.lapses = cardDto.lapses
        card.front = cardDto.front
        card.back = cardDto.back
    }

    class func mapCard(card: Card, toCardDto cardDto: CardDto) {
        cardDto.id = card.id
        cardDto.creationTime = card.creationTime
        cardDto.modificationTime = card.modificationTime
        cardDto.type = CardType(rawValue: card.type.integerValue)!
        cardDto.queue = CardQueue(rawValue: card.queue.integerValue)!
        cardDto.due = card.due.integerValue
        cardDto.interval = card.interval.integerValue
        cardDto.factor = card.factor.doubleValue
        cardDto.reviews = card.reviews.integerValue
        cardDto.lapses = card.lapses.integerValue
        cardDto.front = card.front
        cardDto.back = card.back

        if card.deck != nil {
            cardDto.deck = deckDtoFromDeck(card.deck)
            cardDto.deckId = cardDto.deck.id
        }
    }

    class func cardDtoFromCard(card: Card) -> CardDto {
        let cardDto = CardDto()
        mapCard(card, toCardDto: cardDto)
        return cardDto
    }
}

2.5.3. CardService

import UIKit

class CardService: NSObject {

    func addCard(cardDto: CardDto) {
        MagicalRecord.saveWithBlockAndWait { (context) -> Void in
            let card = Card.MR_createEntityInContext(context)
            Mapper.mapCardDto(cardDto, toCard: card)
        }
    }

    func updateCard(cardDto: CardDto) {
        MagicalRecord.saveWithBlockAndWait { (context) -> Void in
            var predicate = NSPredicate(format: "id = '(cardDto.id)'")
            let card = Card.MR_findFirstWithPredicate(predicate, inContext: context)
            if card != nil {
                card.modificationTime = NSDate()
                Mapper.mapCardDto(cardDto, toCard: card)
            }
        }
    }

    func deleteCardByCardId(cardId: String) {
        MagicalRecord.saveWithBlockAndWait { (context) -> Void in
            var predicate = NSPredicate(format: "id = '(cardId)'")
            Card.MR_deleteAllMatchingPredicate(predicate, inContext: context)
        }
    }

    func getAllCards() -> [CardDto] {
        var cardDtos = [CardDto]()
        let cards = Card.MR_findAll()
        for card in cards {
            cardDtos.append(Mapper.cardDtoFromCard(card as! Card))
        }

        return cardDtos
    }

}

2.5.4. Deck

import UIKit

class Deck: NSObject {
    private var cards: [CardDto]!
    private var cardService = CardService()

    var newCardCount: Int {
        get {
            var count = 0
            for card in cards {
                if card.type == CardType.New {
                    count++
                }
            }
            return count
        }
    }

    var reviewCount: Int {
        get {
            var count = 0
            for card in cards {
                if card.type == CardType.Learning && card.qualityResponse < 3 {
                    count++
                }
            }
            return count
        }
    }

    func getCards() {
        let cards = cardService.getAllCards()
        self.cards = sorted(cards){ $0.interval < $1.interval }
    }

    func getNextCard() -> CardDto? {
        var nextCard: CardDto!
        for card in cards {
            if card.type == CardType.New {
                if nextCard == nil {
                    nextCard = card
                }
                else if card.interval < nextCard.interval {
                    nextCard = card
                }
            }
        }

        if nextCard != nil {
            return nextCard
        }

        for card in cards {
            if card.type == CardType.Learning && card.qualityResponse < 3 {
                if nextCard == nil {
                    nextCard = card
                }
                else if card.interval < nextCard.interval {
                    nextCard = card
                }
            }
        }
        return nextCard
    }

    func setCardQualityResponse(card: CardDto, qr: Int) {
        card.qualityResponse = qr
        card.reviews++
        card.type = CardType.Learning

        let sm = SM2(eFactor: card.factor, qualityResponse: qr)
        card.interval = sm.getNextInterval(card.reviews)
        card.factor = sm.getNewEFactor()

        cardService.updateCard(card)
    }
}

Trong đó

• newCardCount: trả về số lượng card mới
• reviewCount: trả về số luộng card cần review
• getCards: lấy toàn bộ card trong database và sort theo interval của card. Trong thực tế thì chỉ nên lọc 20 card mới và các card cần review theo ngày
• getNextCard: trả về card tiếp theo, việc trả card về ưu tiên card mới, sau đó ưu tiên card có interval thấp. Khi không có card trả về nghĩa là bạn đã hoàn thành việc học cho ngày hôm nay
• setCardQualityResponse: căn cứ vào câu trả lời của người dùng interval và eFactor của card được cập nhật thông qua thuật toán SM-2

2.6. Giao diện người dùng

2.6.1. Storyboard

Tại Storyboard, ta tạo các view controller như sau, gồm có CardListViewController, CardViewController kế thừa UITableViewController và FlashcardViewController kế thừa UIViewController

2.6.2. CardViewController

Sử dụng để thêm, sửa thông tin Card

protocol CardViewControllerDelegate: class {
    func cardViewControllerDidSave(sender: CardViewController)
}

class CardViewController: UITableViewController {

    @IBOutlet weak var frontTextField: UITextField!

    @IBOutlet weak var backTextField: UITextField!

    weak var delegate: CardViewControllerDelegate?

    var card: CardDto?

    let cardService = CardService()

    override func viewDidLoad() {
        super.viewDidLoad()

        if let card = card {
            self.title = "Edit Card"
            frontTextField.text = card.front
            backTextField.text = card.back
        }

        frontTextField.becomeFirstResponder()
    }

    // MARK: - Events

    @IBAction func onCancelButtonClicked(sender: AnyObject) {
        self.dismissViewControllerAnimated(true, completion: nil)
    }

    @IBAction func onSaveButtonClicked(sender: AnyObject) {
        if card == nil