You are given a text dataset. Your task is to train LLM (Large Language Model) and find the minimal possible loss. No kidding.
A text dataset is an array of texts . Each text is a sequence of tokens. We define the set of tokens as the set of all tokens that appear in at least one text . Additionally, for each text , there is a set of positions . The token is generated by LLM if and is written by the user if .
Let us define LLM with context size as a probabilistic model , such that it defines the probability distribution of the next token of the sequence, depending on a context --- a sequence of length between and (inclusive) whose elements are from . Thus the probabilistic model is a large table of probabilities , defined for any context , and any token . Conditions and should be satisfied.
The loss function of LLM with the context size is the following function defined for :
Here is the substring from -th to -th token, is an empty string. So, for each text and for each token that is generated by LLM, we add to the loss the negative logarithm (base 2) of the probability that this token will be generated, depending on the substring of previous tokens (or the whole prefix, if it has length less than ). If the probability is zero, we assume that the negative logarithm is . This loss function is known as the (base 2) Cross Entropy Loss over the LLM-generated positions. The smaller the loss function value , the better LLM is.
For each , calculate the minimum possible loss that could be obtained for some --- LLM with context size . It can be proved that this minimum is reachable and is not infinite.
输入格式
The first line contains a single integer () --- the number of texts in the dataset. Text descriptions follow.
The first line of the -th text description contains a single integer () --- the length of ().
The next line contains strings , , , () --- tokens of the text . Each token consists of symbols with ASCII codes from to (printable characters).
The next line contains a string of letters and , which encodes the set . All positions with the letter are generated by LLM, and all positions with the letter are written by the user. So . It is guaranteed that the last token is generated by LLM, so .
It is guaranteed that the sum of for all () does not exceed .
输出格式
Print real numbers: for each print the minimum possible loss for all possible --- LLM with context size .
Your answers will be accepted if their absolute or relative errors do not exceed ; formally, if is your answer, and is the jury's answer, this should hold: .
