<jupyter_start><jupyter_text>About dataset- each line contains: ID, Word, Base, POS, POS2, ?, Head, Type- Tab-separated columns, sentences separated by space<jupyter_code>train_file_path = "../data/mstparser-en-train.dep"
test_file_path = "../data/mstparser-en-test.dep"

def load_dataset(path, encoding="utf-8"):
    with open(path, encoding=encoding) as f:
        dataset = f.readlines()
    return dataset<jupyter_output><empty_output><jupyter_text>- How to create features for graph-based dependency parsers?    - I employ the features which appear frequenctly in training dataset.<jupyter_code>class Dataset:
    def __init__(self, dataset):
        """
        The format of dataset should be CoNLL.
        Tab-separated columns, sentences separated by space.
        each line contains: ID, Word, Base, POS, POS2, ?, Head, Type.
        """
        self.data = self._format(dataset)
    
    def __len__(self):
        return len(self.data)
    
    def __getitem__(self, key):
        if isinstance(key, slice):
            return [self.data[i] for i in range(*key.indices(len(self.data)))]
        elif isinstance(key, int):
            if key < 0:
                key += len(self.data)
            if key < 0 or key >= len(self.data):
                raise IndexError
            return self.data[key]
        else:
            raise TypeError
    
    def _format(self, dataset):
        batch = []
        for i in range(len(dataset)):
            if dataset[i] == "\n":
                first = i - int(dataset[i-1].split("\t")[0])
                batch.append([line.split("\n")[0].split("\t") for line in dataset[first:i]])
        return batch
        

class FeatureExtractor:
    def __init__(self, dataset, lr=0.01, topn=30, init_func=None):
        self.dataset = dataset
        self.lr = lr
        self.topn = topn
        self.init_func = init_func
        self.features = None
        self.weight = None
    
    def get_weights(self):
        self.features = self._get_features()
        self.weights = self._update_weights()
        return self.weights
    
    def _count_features(self):
        cnt = defaultdict(lambda: defaultdict(int))
        for batch in self.dataset:
            for i, data_i in enumerate(batch):
                cnt["word"][data_i[1]] += 1
                cnt["pos"][data_i[3]] += 1
                cnt["dep"][data_i[-1]] += 1
                if data_i[-1] == "ROOT":
                    cnt["pos_pos"][f"{data_i[3]}_ROOT"] += 1
                    cnt["word_pos"][f"{data_i[1]}_ROOT"] += 1
                    cnt["dep"][f"{data_i[-1]}_ROOT"] += 1
                else:
                    head_idx = i - int(data_i[0]) + int(data_i[6])    
                    head = batch[head_idx]
                    cnt["word_word"][f"{data_i[1]}_{head[1]}"] += 1
                    cnt["pos_pos"][f"{data_i[3]}_{head[3]}"] += 1
                    cnt["word_pos"][f"{data_i[1]}_{head[3]}"] += 1
                    cnt["pos_word"][f"{data_i[3]}_{head[1]}"] += 1
                    cnt["dep_word"][f"{data_i[-1]}_{head[1]}"] += 1
                    cnt["dep_pos"][f"{data_i[-1]}_{head[3]}"] += 1
        return cnt
    
    def _get_features(self):
        """
        This function extract features for graph-based parser.
        Features include word form, pos, combination of pos and word form.
        """
        cnt = self._count_features()
        features = []
        for feat_type in cnt.keys():
            if feat_type == "pos_pos":
                for feat, v in cnt[feat_type].items():
                    if v >= 5:
                        features.append(feat)
            else:
                for feat, v in sorted(cnt[feat_type].items(), key=lambda i: i[1], reverse=True)[:self.topn]:
                    features.append(feat)
        return features
        
    def _init_weights(self):
        weights = defaultdict(int)
        for feat in self.features:
            if self.init_func:
                weights[feat] = self.init_func()
            else:
                weights[feat] = random.random()
        return weights
    
    def _update_weights(self):
        w = self._init_weights()
        for batch in self.dataset:
            score = defaultdict(int)
            for i, data_i in enumerate(batch):
                for j, data_j in enumerate(batch):
                    if i == j:
                        continue
                    score[j] += w[data_i[1]]
                    score[j] += w[data_i[3]]
                    score[j] += w[data_i[-1]]
                    score[j] += w[f"{data_i[1]}_{data_j[1]}"]
                    score[j] += w[f"{data_i[1]}_{data_j[3]}"]
                    score[j] += w[f"{data_i[3]}_{data_j[1]}"]
                    score[j] += w[f"{data_i[3]}_{data_j[3]}"]
                    score[j] += w[f"{data_i[-1]}_{data_j[1]}"]
                    score[j] += w[f"{data_i[-1]}_{data_j[3]}"]
                score["ROOT"] += w[f"{data_i[1]}_ROOT"]
                score["ROOT"] += w[f"{data_i[3]}_ROOT"]
                score["ROOT"] += w[f"{data_i[-1]}_ROOT"]
                if len(score) == 0:
                    continue
                head_pred = sorted(score.items(), key=lambda i: i[1], reverse=True)[0][0]
                head_true = data_i[6]
                if head_pred == "ROOT":
                    if data_i[-1] != "ROOT":
                        w[data_i[1]] -= self.lr
                        w[data_i[3]] -= self.lr
                        w[f"{data_i[1]}_ROOT"] -= self.lr
                        w[f"{data_i[3]}_ROOT"] -= self.lr
                        w[f"{data_i[-1]}_ROOT"] -= self.lr
                elif head_pred != head_true:
                    data_j = batch[head_pred]
                    w[data_i[1]] -= self.lr
                    w[data_i[3]] -= self.lr
                    w[data_i[-1]] -= self.lr
                    w[f"{data_i[1]}_{data_j[1]}"] -= self.lr
                    w[f"{data_i[1]}_{data_j[3]}"] -= self.lr
                    w[f"{data_i[3]}_{data_j[1]}"] -= self.lr
                    w[f"{data_i[3]}_{data_j[3]}"] -= self.lr
                    w[f"{data_i[-1]}_{data_j[1]}"] -= self.lr
                    w[f"{data_i[-1]}_{data_j[3]}"] -= self.lr
        return w
train_dataset = Dataset(load_dataset(train_file_path))
test_dataset = Dataset(load_dataset(test_file_path))
class MSTParser:
    def __init__(self, extractor):
        self.w = extractor.get_weights()
    
    def __call__(self, batch):
        return self.parse(batch)
    
    def parse(self, batch):
        scores = self._score(batch)
        best_edges = self._get_best_edges(scores)
        scores = self._subtract(scores, best_edges)
        best_edges = self._get_best_edges(scores)
        status, cycles = self._involveCycle([edge for edge, score in best_edges])
        if status:
            best_edges = self._remove_cycles(scores, cycles, best_edges)
        return [edge for edge, score in best_edges[1:]]
    
    def evaluate(self, dataset):
        UAS_SUM = 0
        for batch in dataset:
            # Parse a sentence
            scores = self._score(batch)
            best_edges = self._get_best_edges(scores)
            scores = self._subtract(scores, best_edges)
            best_edges = self._get_best_edges(scores)
            status, cycles = self._involveCycle([edge for edge, score in best_edges])
            if status:
                best_edges = self._remove_cycles(scores, cycles, best_edges)
            y_test = self._extract_test(batch)
            y_pred = [edge for edge, score in best_edges[1:]]
            UAS_SUM += self._get_UAS(y_test, y_pred)
        return UAS_SUM / len(dataset)
            
    
    def _score(self, batch):
        N = len(batch)
        scores  = np.ones([N+1, N+1]) * -1e3
        for i in range(1, N+1):
            for j in range(N+1):
                if i == j:
                    continue
                score = 0
                score += self.w[batch[i-1][1]] #word
                score += self.w[batch[i-1][3]] # pos
                score += self.w[batch[i-1][-1]]
                if j == 0:
                    score += self.w[f"{batch[i-1][1]}_ROOT"] + 1 
                    score += self.w[f"{batch[i-1][3]}_ROOT"] + 1
                    score += self.w[f"{batch[i-1][-1]}_ROOT"] + 1
                else:
                    score += self.w[f"{batch[i-1][1]}_{batch[j-1][1]}"]
                    score += self.w[f"{batch[i-1][1]}_{batch[j-1][3]}"]
                    score += self.w[f"{batch[i-1][3]}_{batch[j-1][1]}"]
                    score += self.w[f"{batch[i-1][3]}_{batch[j-1][3]}"]
                    score += self.w[f"{batch[i-1][-1]}_{batch[j-1][1]}"]
                    score += self.w[f"{batch[i-1][-1]}_{batch[j-1][3]}"]
                scores[i, j] = score
        return scores
    
    def _get_best_edges(self, scores):
#         ignore 0-th row because it would contain scores between ROOT as dependent and words as head
        return [(np.argmax(scores[i, :]),
                 np.max(scores[i, :]))
                if i != 0 else (-1, -1e3)
                for i in range(scores.shape[0])
                ]
    
#         best_edges = []
#         root_child_idx = np.argmax(scores[:, 0])
#         for i in range(scores.shape[0]):
#             if i == root_child_idx:
#                 best_edges.append((0, scores[root_child_idx, 0]))
#             elif i == 0:
#                 best_edges.append((-1, -1e3))
#             else:
#                 head_idx = np.argmax(scores[i, 1:])
#                 best_edges.append((head_idx, scores[i, head_idx]))
#         return best_edges
        
    def _subtract(self, scores, best_edges):
        N = scores.shape[0]
        for i in range(N):
            for j in range(N):
                if i == 0 or i == j:
                    continue
                scores[i, j] -= best_edges[i][1]
        return scores
        
    def _involveCycle(self, edges):
        memory = []
        for dep, head in enumerate(edges):
            dep_ = edges[head]
            if dep == dep_ and (sorted([dep, head]) not in memory):
                memory.append(sorted([dep, head]))
        if memory:
            return (True, memory)
        else:
            return (False, [])
    
    def _remove_cycles(self, scores, cycles, best_edges):
        N = scores.shape[0]
        for cycle in cycles:
            scores_ = scores.copy()
            scores_[cycle[0], cycle[1]] = -1e3
            scores_[cycle[1], cycle[0]] = -1e3
            node, j = divmod(np.argmax(scores_[cycle, :]), N)
            if node == 0:
                c_head = cycle[0]
            else:
                c_head = cycle[1]
            best_edges[c_head] = (j, scores[c_head, j])
        return best_edges
    
    def _extract_test(self, batch):
        return [int(data[6]) for data in batch]
    
    def _get_UAS(self, y_test, y_pred):
        assert len(y_test) == len(y_pred)
        match_num = 0
        for test, pred in zip(y_test, y_pred):
            if test == pred:
                match_num += 1
        return match_num / len(y_test)
extractor = FeatureExtractor(train_dataset, topn=100, lr=0.1, init_func=None)
parser = MSTParser(extractor)
parser.evaluate(test_dataset)
random.choice(train_dataset)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14358974358974358, 'fraction_numerical': 0.016003536693191867, 'mean_word_length': 1.6483259189885273, 'pattern_counts': {'":': 5, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '148403', 'license': 'MIT', 'n_tokens_mistral': 3733, 'n_tokens_neox': 3568, 'n_words': 741, 'path': 'notebooks/Dependency parsing.ipynb', 'repo_name': 'hirobf10/sl_parsing_slp', 'size': '11310'}