fair_submodular_matroid：基于 Matroid 约束的公平流式子模最大化实验复现指南

fair_submodular_matroid基于 Matroid 约束的公平流式子模最大化实验复现指南【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research本指南以 Google Research 仓库 fair_submodular_matroid 目录为对象系统讲解论文Fairness in Streaming Submodular Maximization over a Matroid Constraint的配套实现如何编译 C17 代码、如何下载并预处理三个实验数据集Pokec 最大覆盖、Bank Marketing 聚类、MovieLens 电影推荐、如何配置并运行实验、如何解读结果文件。读完本文你将掌握该仓库从数据准备、算法接入到结果输出的完整复现流程并理解其子模函数 Matroid 公平约束三层可扩展架构的底层原理。实验背景与整体架构该目录实现的是流式streaming场景下、在 Matroid 约束之上再加入公平性约束fairness constraint的子模最大化问题。与经典流式子模最大化只要求解满足 Matroid 可行性的设定不同本仓库要求解集同时满足Matroid 约束保证解的组合结构合法例如每个分组的数量上限公平性约束保证解中每个颜色类color class的元素数量落在给定的下界/上界区间内。每个实验都由三要素构成且三者都通过**预言机oracle**交互要素职责对应基类子模函数submodular function给出集合的目标值 f(S) 与边际增量 Δ(e)submodular_function.h 中的SubmodularFunctionMatroid判定集合的可行性与交换操作matroid.h 中的Matroid公平约束按颜色统计元素数量并校验上下界fairness_constraint.h 中的FairnessConstraint通过继承扩展新功能README 明确指出要实现新的子模函数继承SubmodularFunction类要实现新的 Matroid继承Matroid类。这也是把三个实验最大覆盖、聚类、电影推荐统一在同一套算法框架下的关键设计。从源码看SubmodularFunction基类submodular_function.h要求子类实现的核心接口包括Objective(elements)计算任意集合的目标值 f(S)不依赖对象当前状态Delta(element)计算加入元素 e 的边际增量 f(S∪{e}) − f(S)RemovalDelta(element)计算移除元素 e 的边际损失 f(S) − f(S−e)Add/Remove/Swap维护内部当前解集 SGetUniverse()返回全集元素Clone()克隆对象算法内部会为每个颜色类维护函数副本。同时基类内置了带 oracle 计数的便捷方法DeltaAndIncreaseOracleCall、AddAndIncreaseOracleCall、ObjectiveAndIncreaseOracleCall等并通过静态变量oracle_calls_累计预言机调用次数用于实验中的查询复杂度统计。Matroid基类matroid.h的核心接口包括CanAdd加入是否可行、CanSwap交换是否可行、Add、Remove、IsFeasible、GetCurrent、Clone等。仓库已实现以下 Matroiduniform_matroid.h均匀拟阵仅限大小 kpartition_matroid.h划分拟阵每个分组有独立上限由groups_map元素→分组与ks各组上限构造laminar_matroid.h层状laminar拟阵支持嵌套分组conditioned_matroid.h条件拟阵conditioned matroid两遍算法的关键组件matroid_intersection.h拟阵交用于构造满足公平下界的可行解。编译代码仓库所有实验文件均为 C17 或更高标准编译除输入预处理相关文件见preprocessors/目录外其余文件可直接编译。README 给出了一个开箱即用的 Makefile 模板SRC_FILES : $(wildcard *.cc) H_FILES : $(wildcard *.h) CXXFLAGS : -O3 -W -Wall -Wshadow -Wno-unused-parameter -Wno-sign-compare -stdc17 BIN : fair-submodular.exe $(BIN): $(SRC_FILES) $(H_FILES) g $(CXXFLAGS) -o $ $(SRC_FILES) all: $(BIN)在该目录下执行make即可构建出可执行文件fair-submodular.exe。其中-O3开启最高优化流式实验通常数据量大-stdc17明确指定标准-Wno-unused-parameter等抑制了实验代码中常见的宽松警告。也可以手动执行g -O3 -W -Wall -Wshadow -Wno-unused-parameter -Wno-sign-compare -stdc17 -o fair-submodular.exe *.cc下载与预处理数据集三个实验分别需要不同的公开数据集预处理脚本全部位于 preprocessors 目录。1. 最大覆盖实验Pokec 社交网络该实验使用斯坦福 SNAP 的 Pokec 数据集soc-pokec-relationships.txt与soc-pokec-profiles.txt下载后将两个文件放入存放预处理脚本的同一目录即preprocessors/然后按顺序执行运行 extract-attributes.cpp从用户档案中抽取属性生成filtered-attributes.txt运行 color-vertices.cpp生成color_age_1.txt按年龄分色运行 statistics_bmi.cpp生成color-BMI.txt按 BMI 分色运行 clean_graph_for_bmi.cpp生成BMI-soc-pokec-relationships.txt清洗后的关系边表。随后在 graph.cc 的name_to_filename映射表中将路径更新为上述三个文件的真实位置。从 main.cc 的CoverageExperiment可以看出该实验以图顶点为全集GraphUtility作为覆盖函数顶点按分组GetGroupsMap构造PartitionMatroid按颜色GetColorsMap构造FairnessConstraint颜色上下界由lower_coeff 0.9、upper_coeff 1.5乘以比例得到。2. 基于样本的聚类实验Bank Marketing下载 UCI 的 Bank Marketing 数据集运行预处理程序 bank_input_converter_main.cc 将原始bank数据转换为预言机期望的输入格式然后在主文件的ClusteringExperiment函数中更新input_path指向转换后的特征文件。在 main.cc 中可以看到ClusteringExperiment通过BankData读取数据ClusteringFunction作为聚类目标函数f(S) 为选中样本集对全体数据的覆盖质量按余额分组balance_map_构造PartitionMatroid按年龄段age_grpcards_构造公平约束秩 rank 从 15 递增到 60rank 5 * ii 从 3 到 12。3. 电影推荐实验MovieLens-1M使用 prepare_movies.py 中更新该目录路径。从源码看MoviesDatamovies_data.h是单例类稀疏的用户-电影评分矩阵被近似为两个低秩矩阵 U × V 的乘积见其注释说明由此可以快速计算任意用户对电影的打分GetUserMovieScore与电影间相似度GetMovieMovieSimilarity。电影按类型genre作为公平约束的颜色、按上映年代区间year band作为 Matroid 分组。实验还支持两种 Matroid 变体普通PartitionMatroid与LaminarMatroid后者把每 3 个相邻年代区间合并为一个大组大组上限为大组内各小组上限之和的 0.8 倍详见 main.cc 的MovieExperiment。运行实验与配置要点主程序为 main.cc。默认的main()只启用了ClusteringExperiment(1, 1)其余实验需要自行取消注释int main() { ClusteringExperiment(1, 1); // CoverageExperiment(1,10); // MovieExperiment(false); // MovieExperiment(true); }运行前必须注意两处路径配置输入路径按上一节说明分别在 graph.cc 的name_to_filename、ClusteringExperiment的input_pathmain.cc、movies_data.cc 中更新输出路径BaseExperiment中的exp_base_pathmain.cc决定结果文件前缀。每次运行会为每个算法生成三份文件exp_base_path_算法名.txt主结果表首行为列头rank f error ratio OCexp_base_path_sols_算法名.txt每个 rank 下的具体解集元素编号从 1 开始对应论文中的索引exp_base_path_general.txt一般日志含求解向量与随机算法的方差百分比。结果字段含义README 对结果文件中的关键字段给出了明确定义f子模目标函数值submodular objective valuerankMatroid 的秩 kerror公平约束的违反量 err(S)即解集中各颜色数量超出[下界, 上界]区间的总量。其计算方式见 main.cc对每个颜色统计出现次数occurance[i]误差为max(0, occurance[i] - upper)与max(0, lower - occurance[i])之和ratio最坏下界满足比min(occurance[i] / (lower[i]/2))反映解在各颜色上的最差覆盖程度OC该次实验的子模函数 oracle 调用总数f.oracle_calls_用于评估算法的查询复杂度。算法的统一调用约定所有算法都继承自 algorithm.h 中的Algorithm基类其使用流程被严格约定为Init(f, fairness, matroid)初始化默认实现只是克隆并保存三个参数将SubmodularFunction::oracle_calls_置 0对全集每个元素依次调用Insert(element)共 n 次若是两遍算法先调用BeginNextPass()再对全集元素再次调用 n 次Insert调用GetSolutionValue()必须调用算法可能在此才计算最终解可选调用GetSolutionVector()获取解集读取SubmodularFunction::oracle_calls_得到预言机调用数。仓库中的Algorithm实现包括算法类趟数说明Better Greedybetter_greedy_algorithm.h1在每个颜色类上维护独立的子模函数副本先构造满足下界的可行解再贪心补足minimal参数控制是否只求满足ell_c个元素的最小可行解两遍算法two_pass_algorithm_with_conditioned_matroid.h2第一遍贪心收集权重第二遍在条件 Matroid 上求解GetNumberOfPasses()返回 2拟阵交算法matroid_intersection_algorithm.h1利用拟阵交求解主要供可行性判定与理论对照使用在SingleKBaseExperimentmain.cc中可以看到实验循环的细节为了公平比较每个算法在运行前都会执行RandomHandler::generator_.seed(1)重置随机种子对于随机算法Totally random algorithm 与 Fair random algorithm每个 rank 重复 20 次并输出均值与标准差方差以百分比形式记入 general 日志。每个 rank 开始前还会用MaxIntersection判定是否存在满足公平约束与 Matroid 的可行解不存在则跳过该 rank 并输出No feasible solution for ...提示main.cc。常见问题与排查建议编译报错确认使用 C17 及以上标准若手动指定了过旧的-std会导致类模板与智能指针相关语法不兼容。找不到输入文件Pokec 与 MovieLens 实验均需要先完成预处理步骤并同步修改graph.cc、movies_data.cc与main.cc中的路径路径务必使用绝对路径或相对可执行文件所在目录的正确路径。结果全为不可行解检查公平约束上下界是否与数据分布匹配参考main.cc中基于比例如rank * card / n计算上下界的做法调整参数。想要复用框架继承SubmodularFunction与Matroid实现自己的函数与约束再按上述七步调用约定接入任意Algorithm即可无需改动算法本体。总结fair_submodular_matroid是一个结构清晰、可直接复现的实验仓库它用统一的子模函数预言机 Matroid 预言机 公平约束抽象覆盖了最大覆盖、聚类、电影推荐三类典型场景内置了单遍贪心、两遍条件 Matroid 算法与拟阵交算法等对照实现。通过本文的编译、数据预处理与运行步骤你可以在本地完整复现论文中的实验流程并借助f、rank、error、ratio、OC五项指标量化评估不同算法在公平约束下的表现若需扩展新的应用场景只需按照基类接口实现新的SubmodularFunction与Matroid子类即可无缝接入现有算法框架。【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考